入门

简单基本概念

基本数学运算符

  • ** ^ 指数
  • %取余
  • / 约分
  • //取整

附：算数二元运算符优先级

括号>指数>乘法除法>加法、 减法

常见数学函数

内置pi, e

  • 向上取整 floor 向下取整 ceil

  • sqrt 求平方根

  • gcd 求最大公约数,lcm 求最小公倍数

  • sin cos tan …（sagemath完全处理pi，不是数的计算值）

  • divmod()同时获得商和余数

  • factor()计算整数的素因数分解

  • max ,min ,abs(绝对值),log(),ln(),log(x,b)

  • factor()求阶乘

    …

基于密码使用sage

基本数论函数

求逆元

inverse_mod(x,y):在模y下x的逆元

拓展欧几里得

xgcd(x,y): 返回值（a,b,c) —>a=bx+cy

欧拉函数

euler_phi(n)

中国剩余定理

crt([x1,x2,x3,x4],[x11,x22,x33,x44])

即求{x≡x1(modx11)x≡x1(modx11)x≡x1(modx11)x≡x1(modx11)即求 \left\{ \begin{aligned} x\equiv x1(mod\quad x11)\\ x\equiv x1(mod\quad x11)\\ x\equiv x1(mod\quad x11)\\ x\equiv x1(mod\quad x11)\\ \end{aligned} \right.

生成随机素数

random_prime(a,b) (a>b,b可缺省)

素数

is_prime() ----->返回true,false

nth_prime(x)----->返回第x个素数

next_prime(n)------>输出大于n 的素数

previous_prime(n)----->输出小于n的素数

list(primes(a,b))------>a,b区间内的素数

计算x^y mod n

power_mod(x,y,n)

求自身的n次方根

FR（n).nth_root(m,all=‘Truue’)

整数分解

  • [x] 分解整数 factor()

  • [ ] 椭圆曲线分解寻找素因子 ecm()

  • [ ] 二次筛法分解 qsieve()

  • [x] 仅求出素因子 prime_divisor()

求多项式的 根

判断二次剩余

R = IntegerModRing(m)
x=R(y)
b.is_square()判断b是不是在模m下的二次剩余

代数

基本的数域与环

域：设P是由一些复数组成的集合(包括0,1),若P中任意两个数(可以相同)的和差积商(除数不为0)仍是P中的数,则称P为一个数域.

  • 实数域 ：RR

  • 复数域：CC

环：数环是一种特殊的数集，由数组成的环，是环的最基本的例子和模型.设P是复数集的非空子集，如果P中任意两个数的和、差、积仍属于P，则称P是一个数环。

  • 整数环: ZZ
  • 有理数环: QQ
  • 多项式环:PolynomialRing()
  • 伽罗瓦域(N必须是某个素数或者某个素数的k次方)：GF(N)、GF(2^8,modulus=[1,0,0,1,1,1,0,0,1])
  • 一般有限环：Zmod(N)

****Sagemath在ctf密码学中的使用 - _Mind - 博客园 (cnblogs.com)

#整数域
ZZ()
#有理数域
QQ()
#实数域
RR(2^0.5)
#复数域
CC(1,2)

#sage: CC(1,2)
#1.00000000000000 + 2.00000000000000*I

#声明生成虚数单位i
i=ComplexField().gen();
#eg:
#sage: i=ComplexField().gen()
#sage: (2+i)*(4+3*i)
#5.00000000000000 + 10.0000000000000*I

#构造多项式环,返回具有给定属性和变量名的全局唯一的单变量或多元多项式环
#定义在整数域上的多项式环R，变量为w;ZZ也可换成其他数域
R.<w>=PolynomialRing(ZZ);
#sage
R.<w>=PolynomialRing(ZZ)
sage: (1+w)^3
w^3 + 3*w^2 + 3*w + 1

#有限环
RN=IntegerModRing(63)
FR=Integers(17);
#自身的代数扩展;exR=FR[w]/(w^2+3)
exR=FR.extension(w^2+3)
#以python整数的形式返回所有可逆元素的列表
FR.list_of_elements_of_multiplicative_group()
#假设环的乘法群是循环的，返回这个环的乘法群的生成元
FR.multiplicative_generator()
#返回这个环的一个随机元素
FR.random_element()
#上述几种方法对如下的域同样支持

#有限域
#素数域
G1=GF(37);G1
#伽罗瓦域
G2=GF(3^5);G2

线性代数

#定义矩阵，默认定义在实数域
A = matrix([[1,2,3,5],[3,2,1,2],[1,1,1,0],[3,7,2,2]])
A^-1
#定义在其他域上的矩阵，如有限域
A = matrix(GF(13),[[1,2,3,5],[3,2,1,2],[1,1,1,0],[3,7,2,2]])
A^-1
#可以看到两个逆矩阵不一样

#定义向量，定义在有限域，默认定义在实数域
w = vector(GF(13),[1,1,4,3])
Y=A*w;Y
Z=w*A;Z

#解线性方程组AX=Y
X = A.solve_right(Y);X
#也可以使用符号\
A\Y
#解线性方程组XA=Y
X = A.solve_left(Z);X

#格基约减
A = matrix([[1,2,3,5],[3,2,1,2],[1,1,1,0],[3,7,2,2]])
#LLL算法
A.LLL()
#BKZ算法
A.BKZ()

离散椭圆曲线

p=ZZ('FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF',16)
a=ZZ('FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC',16)
b=ZZ('28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93',16)
#有限域GF(p)上的椭圆曲线y^2 = x^3 + a*x + b mod p
E=EllipticCurve(GF(p),[0,0,0,a,b])
#基点
g=E([ZZ('32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7',16),ZZ('bc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0',16)])
#基点的阶
n=ZZ('FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',16)
#生成密钥
sk=random_prime(2*n//3,n//3)
#生成公钥
G=sk*g

离散对数

求解以base为底，a的对数；ord为base的阶，可以缺省，operation可以是’+‘与’’，默认为’’；bounds是一个区间(ld,ud)，需要保证所计算的对数在此区间内

#通用的求离散对数的方法
x=discrete_log(a,base,ord,operation)

#求离散对数的Pollard-Rho算法
x=discrete_log_rho(a,base,ord,operation)

#求离散对数的Pollard-kangaroo算法(也称为lambda算法)
x=discrete_log_lambda(a,base,bounds,operation)

#小步大步法
x=bsgs(base,a,bounds,operation)

coppersmith算法

参考：https://blog.csdn.net/qq_39642801/article/details/104158699

​ https://blog.csdn.net/weixin_44338712/article/details/105320810