介绍

SageMath 是一个基于 GPL 协议的开源数学软件。它使用 Python 作为通用接口,将现有的许多开源软件包整合在一起,构建一个统一的计算平台。

Sage 基于并使用 Python，Python 程序可以在 Sage 中直接运行，也可以在 Sage 中使用 Python 的各种库，就像是提供一个包含各种数学功能的 Python 环境。

在 CTF 密码学中，经常要用到 SageMath。

安装

官网：https://www.sagemath.org/zh/

blog教程：https://www.lainme.com/doku.php/topic/sage/start

本人是放在 windows 上运行的。windows 的 SageMath 是在虚拟机环境下运行的，一般使用时打开 SageMath Shell 运行。

有一个在线运行sage脚本的网站：https://sagecell.sagemath.org/

建议 Ubuntu18.04 安装 sagemath（命令行安装，超方便）

1
2
3
4
sudo -i
apt update
apt-get update
apt install sagemath

windows下使用

打开 SageMath Shell 。输入 sage 即可进入 Sage 会话。

如果使用脚本，shell 进入相关路径，用命令 sage xxx.sage 运行脚本。

linux下使用就不用那么麻烦了：)

常用命令

基本运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
a = 5	#  赋值
2 == 2	#  比较
2**3	#  **代表幂
2^3     #  ^是**的别名（和Python不一样）
10 % 3  #  对于整型参数，%代表mod运算，也就是取余数
10//4   #  对于整型参数，//返回整数商

abs(-10)    #  求绝对值
sqrt(3.4)   #  开方
isqrt(15)   #  开方取整
sin(5.135)  #  求正弦值
exp(2)      #  求e的2次方
10.bits()   #  将整数转化为二进制列表
10.hex()    #  转换成16进制

基本代数

解方程

solve 函数用于解方程。要使用它，先要指定变量，然后将方程（或方程组）以及要求解的变量作为参数 传给 solve。

1
2
x = var('x')
solve(x^2 + 3*x + 2, x)

可以求解方程，解出用其他变量表示的一个变量

1
2
x, b, c = var('x b c')
solve([x^2 + b*x + c == 0],x)

也可以求解多个变量：

1
2
x, y = var('x, y')
solve([x+y==6, x-y==4], x, y)

求解方程的数值解

用 find_root 在区间 0 < ϕ < π/2 上寻找上述方程的解。

1
2
phi = var('phi') 
find_root(cos(phi)==sin(phi),0,pi/2)

基本的环

• 整数环 {…,−1,0,1,2,…}, Sage 中叫 ZZ;

• 有理数环 ，即整数构成的分数，Sage 中叫 QQ;

• 实数环，Sage 中叫 RR;

• 复数环，Sage 中叫 CC；

sage: ratpoly. = PolynomialRing(QQ)

ratpoly是集合的名字，自己定义

.是变量的名字，自己定义

PolynomialRing()是环

QQ是有理数环

有限域还有，GF(2)、GF(2^8,modulus=[1,0,0,1,1,1,0,0,1]) ……

线性代数

使用方法 solve right. 执行 A.solve right(Y) 返回一个矩阵（或向量）X 满 足 AX = Y:

1
2
3
4
5
A = Matrix([[1,2,3],[3,2,1],[1,1,1]]) 
Y = vector([0, -4, -1]) 
X = A.solve_right(Y) 
#反斜杠 \ 可以代替 solve_right; 用 A \ Y 代替 A.solve right(Y).
A \ Y

类似的，使用 A.solve left(Y) 求解满足 XA = Y 的 X.

矩阵所在的环影响它的性质。

matrix 命令中的第一个参数告诉 Sage 这个矩阵 是整数环 (ZZ) 上的，有理数环 (QQ) 上的，还是实数环 (RR) 上的:

1
2
3
AZ = matrix(ZZ, [[2,0], [0,1]]) 
AQ = matrix(QQ, [[2,0], [0,1]]) 
AR = matrix(RR, [[2,0], [0,1]])
1
2
3
4
5
A = Matrix(3,range(9))	#  新建一个3*3的矩阵A
A.echelon_form()		#  A的阶梯形式
A.T == A.transpose()	#  A的转置矩阵
A.rows()				#  A的行向量
A.columns()				#  A的列向量

多项式

一元多项式

三种方式创建多项式环

1
2
3
4
5
R = PolynomialRing(QQ, ‘t’)

R = QQ[‘t’]

R.<t> = PolynomialRing(QQ) or sage: R.<t> = QQ[‘t’] or R.<t> = QQ[]

eg:

1
2
3
4
5
sage: R.<t> = QQ[]
sage: f = 2*t^7 +3*t^2 -15/19
sage: f^2

4*t^14 + 12*t^9 - 60/19*t^7 + 9*t^4 - 90/19*t^2 + 225/361

生成随机多项式

1
2
R.<y> = PolynomialRing(GF(p))
S = R.random_element(degree)

检测多项式是否不可约：

1
S.is_irreduceible()

(把多项式每一项的模数由p转变为S对应项的系数)

1
Rs = R.quotient(S)

将整数列表转为多项式对应项的系数，

1
RS([111,111])
1
2
3
F.<x> = GF(2^8,modulus=[1,0,0,1,1,1,0,0,1])	 #感觉那个PolymonialRing都不用写了
F.fetch_int(21) == F(21.bits())
F(21.bits()).integer_representation()	#逆过程

多元多项式

跟定义一元多项式一样，定义多元多项式也有多种方法：

1
2
3
4
5
GF(5)[‘z0, z1, z2’]

R.<z0,z1,z2> = GF(5)[];

PolynomialRing(GF(5), 3, ‘xyz’)

eg:

1
2
3
4
5
6
7
sage: R.<x,y> = RationalField()[]
sage: f = (x^3 +2*y^2*x)^2
sage: g = x^2*y^2
sage: f.gcd(g)
x^2
sage: gcd(f,g)
x^2

数论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
R = IntegerModRing(97) or R = Zmod(97)	#  定义模数为97的环
a = R(2) / R(3) 						#  环上的除法
a.is_square() 							#  是否为二次剩余
gcd(3,2) 								#  最大公因数
factorial(5) 							#  阶乘
next_prime() 							#  后一个素数
previous_prime() 						#  前一个素数
divisors() 								#  所有因子
sigma(n,k)								#  n的所有因子的k次幂之和
inverse_mod(a,n) 						#  求逆
euler_phi(n) 							#  求n的欧拉函数 phi = n*prod([1 - 1/p for p in prime divisors(n)]);
crt(m1,m2,n1,n2) 						#  中国剩余定理 【x % n1 = m1; x % n2 = m3】
d,u,v=xgcd(20,30)						#  扩展欧几里得算法

#两种因式分解
factor(1024) -> 2^10
prime_divisors(1024) -> [2]

#有限域下开根
R.<X> = PolynomialRing(Zmod(p))
f = x^256 - c
f.monic().roots()

#求模取根
x=mod(5,41)
r=x.nth_root(22)

#求离散对数
x=discrete_log(mod(13,23),mod(2,23))	#  或discrete_log(13,mod(2,23))

#素数分布（Pi(x)）
result=prime_pi(1000)/(1000/log(1000))
result.numerical_approx() #1.16050288686900

椭圆曲线

1
EllipticCurve(R, [a1, a2, a3, a4, a6])

eg1:

1
2
3
sage: ecc = EllipticCurve(GF(q), [a,b]) #初始化一条线
sage: G = ecc(x,y) #选定其上的一个点
sage: G.order() #G点的阶

eg2：

1
2
3
4
a4=2;a6=3;F=GF(7);
E=EllipticCurve(F,[0,0,0,a4,a6])
print(E.cardinality()) #6
print(E.points()) #[(0 : 1 : 0), (2 : 1 : 1), (2 : 6 : 1), (3 : 1 : 1), (3 : 6 : 1), (6 : 0 : 1)]