常用语法

from gmpy2 import *

mpz(n)	#初始化一个大整数
mpfr(x)	# 初始化一个高精度浮点数x
d = invert(e,n) 	# 求逆元，de = 1 mod n
c = powmod(m,e,n)	# 幂取模，结果是 c = m^e mod n
is_prime(n)	 #素性检测
gcd(a,b)  	#欧几里得算法，最大公约数
gcdext(a,b)  	#扩展欧几里得算法
iroot(x,n) 	#x开n次根

sympy

from sympy import *

prime(n)  #第n个素数
isprime(n)  #素性检测
primepi(n)  #小于n的素数的总数
nextprime(n)  #下一个素数
prevprime(n)  #上一个素数
nthroot_mod(c,e,p,all_roots=True)  #有限域开方

Sagemath

环境与导入

# sage shell 里直接写，无需导入
# 普通 python 环境调用 sage 功能：
from sage.all import *

# 也可以按需导入，加快启动速度
from sage.all import GF, ZZ, QQ, Matrix, Zmod, block_matrix, vector
from sage.groups.generic import discrete_log
from sage.modules.free_module_integer import IntegerLattice

sage 对象可以序列化保存/加载（比如题目把矩阵存成 data.sobj 发给你）：

1 2	`save(data, "data.sobj") # 题目侧导出 data = load("data.sobj") # 解题侧读回`

在线环境：sagecell.sagemath.org 可以免装跑小段代码。Jupyter 里的效率技巧：%display latex 开 LaTeX 渲染、%timeit 测耗时、函数名后按 Tab 补全。

帮助与调试：

1
2
3

discrete_log?      # 查看文档
EllipticCurve??    # 查看源代码
type(sqrt(2))      # 查看对象类型

符号计算基础

Sage 的理念是符号计算——先保持精确形式，需要数值时再算：

sqrt(2)          # 保持 sqrt(2)，不急着算数值
sqrt(2).n()      # 需要数值时 .n()，默认 53 位
pi.n(digits=100) # 自定义精度
RealField(200)(pi)   # 200 位精度实数

10/4             # 5/2 —— 自动有理数，不丢精度！
10//4            # 2 —— 整数除法
10/4.0           # 2.50000000000000 —— 浮点数

2^100            # sage 里 ^ 就是幂（等价 Python 的 **），抄 Python 代码时注意别混！

符号变量必须先声明（新手第一大坑）：

1
2
3

expand((x + 1)^2)      # ❌ NameError: name 'x' is not defined
x = var('x')           # ✅ 先声明
y, z = var('y z')      # ✅ 一次声明多个

数值求根（区间法）：

1	`find_root(x^2 - 2, 0, 2) # 在 [0,2] 区间找数值根`

环（Ring）与域（Field）

Sage 一切运算都发生在指定的代数结构里，先选环/域再算：

ZZ    # 整数环
QQ    # 有理数域（精确分数，不会丢精度）
RR    # 实数环
CC    # 复数环
GF(p)         # 有限域（p 为素数），等价于 Integers(p) 的域版本
Zmod(n)       # 模 n 整数环（n 可为合数，有零因子）
Integers(n)   # 同上，写法不同
IntegerModRing(P)  # 同上，又一种写法
Zp(p, prec=2) # p-adic 环，prec 指定精度，可处理模 p^k 的问题
Qp(p)         # p-adic 域

扩域 GF(p^n)（MOV 攻击、AES 域运算都要用）：

F.<a> = GF(2^8)              # 用生成元 a 表示所有元素
a^255                        # 乘法群阶 255，a^255 == 1

# 指定不可约多项式（AES 用 x^8+x^4+x^3+x+1）
R.<x> = PolynomialRing(GF(2))
F.<b> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)
F.primitive_element()        # 找原根

选错环结果完全不同：做 RSA 相关的多项式运算必须用 PolynomialRing(Zmod(n))；如果错误地用 PolynomialRing(GF(p))，相当于把模换成了素数 p，和 n 完全不符（合数环有零因子，多项式根数可以超过次数）。

二次域与商环：

K.<i> = QuadraticField(-1)   # Q(i)，i 即虚数单位（高斯整数问题用它）
K.<a> = NumberField(x^2 - 2) # 一般代数数域

# 商环：多项式环模理想
R.<x> = PolynomialRing(QQ)
I = R.ideal(x^2 + 1)
Q = R.quo(I)
Q(x)^2                       # x² ≡ -1，得 -1

生成元语法 `R.<x> = ...`

Sage 特有的预解析器写法，<x> 同时声明变量名和环的生成元：

R.<X> = PolynomialRing(Zmod(n))
'''
1. Zmod(n): 指定模，定义界限为 n 的环，有效数字只有 0～n
2. ZZ: 整数环; QQ: 有理数环; RR: 实数环; CC: 复数环
3. R: 只是一个指针，指向 PolynomialRing 建立的那个环（可用任意字符）
4. PolynomialRing: 建立多项式环
5. <X>: 指定一个变量（可用任意字符）
'''

# 矩阵也可以做环的元素
R.<M> = PolynomialRing(MatrixSpace(Zmod(n),3,3))  # 模 n 的 3x3 矩阵环

# 双变量（多未知量建模用）
P.<x, y> = PolynomialRing(Zmod(N))

等价的函数式写法（纯 Python 环境也能用）：

from sage.all import PolynomialRing, GF
P_ring = PolynomialRing(GF(m), 'x')
x = P_ring.gen()
f = sum(coeffs[j] * (x**j) for j in range(r))

数论

d = inverse_mod(e, fn)      # 求逆元（模 fn）
c = power_mod(m, e, n)      # 幂取模 m^e mod n
factor(n)                   # 整数/多项式分解，返回 [(素因子, 次数), ...]
ecm.factor(N)               # ECM 分解（p-1/p+1 光滑或中小因子时比 factor 快）
euler_phi(n)                # 欧拉函数
prime_pi(n)                 # 小于等于 n 的素数个数
divisors(n)                 # n 的全部因子
number_of_divisors(n)       # 因子个数
two_squares(n)              # n = a²+b²（构造高斯素数常用）
three_squares(n)            # n = a²+b²+c²
four_squares(n)             # n = a²+b²+c²+d²
crt([r1,r2,..],[m1,m2,..])  # 中国剩余定理（列表形式，也支持非互质模数的扩展 CRT）
prod(N_list)                # 列表求乘积（广播攻击 CRT 后开方用）

next_prime(n)               # 下一个素数
random_prime(2^512)         # 随机素数
random_prime(2^bits - 1, lbound=2^(bits-1))  # 指定位数区间的随机素数
is_prime(n)                 # 素性检测
primitive_root(p)           # 原根
is_primitive_root(g, p)     # 判断原根
legendre_symbol(a, p)       # Legendre 符号（二次剩余判定）
jacobi_symbol(a, n)         # Jacobi 符号
binomial(e, i)              # 二项式系数（手搓 Coppersmith 展开用）
isqrt(N)                    # 整数平方根（判完全平方：isqrt(d)^2 == d）
N.nbits()                   # 比特长度（等价 bit_length）
floor(log(N, 2) / 2)        # log 直接对大整数算，估算位数

扩展欧几里得与开方：

d,u,v = xgcd(20,30)   # d=10 u=-1 v=1，即 20u+30v=10

Integer(c).nth_root(e, truncate_mode=True)
# 开 e 次方，不精确时返回 (整数部分, False) 而不抛异常
# 配合 power_mod(m, e, N) 验证，适合"先试开方、失败再上 Coppersmith"的分支

mod(x,p).nth_root(n)               # 有限域内开 n 次方

# 有限域开 n 次方（e 很大时用 pari）
def mod_nth_root(x, e, n):
    r, z = pari(f"r = sqrtn(Mod({x}, {n}), {e}, &z); [lift(r), lift(z)]")
    r, z = int(r), int(z)
    roots = [r]
    t = r
    while (t := (t*z) % n) != r:
        roots.append(t)
    return roots

模运算元素的语法糖：mod(a, P) 生成 Z/PZ 元素，/ 自动乘逆元，ZZ(...) 提升回 Python 整数：

1 2	`A = mod(dy[1] - dx[0], P) / mod(dy[0], P) # 除法 = 乘逆元 X = ZZ(mod(dx[0]/a, p)) # 提升回整数`

多项式

f.subs({x: x1})                       # 把 x1 代入 x
f.sub(x, x-1)                         # 将 x-1 代入 x
f.univariate_polynomial()             # 多元映射为单变量多项式
f.univariate_polynomial().roots()     # 单变量多项式求根，返回 [(根, 重数), ...]
f.coefficients()                      # 系数列表
f.padded_list(n)                      # 系数转为长度 n 的列表（缺位补 0）
f.list()                              # 多项式系数
f.monic()                             # 首一化
f.factor()                            # 分解因式
f.gcd(g)                              # 最大公因式
f.roots(multiplicities=False)         # 只要根不要重数
f[i]                                  # 取第 i 次项系数
f.degree()                            # 次数
p.quo_rem(q)                          # 带余除法，返回 (商, 余数)
f.resultant(g)                        # 结式（两多项式有公共根 ⟺ 结式为 0）

因式分解与 GCD：

# 一元
x = PolynomialRing(RationalField(), 'x').gen()
f = (x^3 - 1)^2 - (x^2 - 1)^2
f.factor()

# 二元
x, y = PolynomialRing(RationalField(), 2, ['x','y']).gens()
f = (9*y^6 - 9*x^2*y^5 - 18*x^3*y^4 - 9*x^5*y^4 + 9*x^6*y^2 + 9*x^7*y^3 + 18*x^8*y^2 - 9*x^11)
f.factor()

# 多元 GCD（order='lex' 指定单项序）
R.<x,y,z> = PolynomialRing(RationalField(), order='lex')
f = 3*x^2*(x+y)
g = 9*x*(y^2 - x^2)
f.gcd(g)

结式恢复未知模数（两条关系多项式在模 p 下有公共根 ⟹ p 整除结式；多个结式取 gcd、factor()[-1][0] 取最大素因子消杂）：

R.<x> = PolynomialRing(ZZ)
f0, f1, f2 = [sum(rkm[j,i]*x^i for i in range(11)) for j in range(3)]
p = gcd(f0.resultant(f1), f1.resultant(f2)).factor()[-1][0]

# 换环后求公共根
F = GF(p)
a = gcd(f0.change_ring(F), f1.change_ring(F)).roots()[0][0]

同类技巧：未知模数 LCG，t_i·t_{i+2} − t_{i+1}² 都是 m 的倍数，多个取 gcd(g0, g1).factor()[-1][0] 得 m。

Groebner 基——多元多项式方程组的强力解法：

1
2
3

R.<x, y> = PolynomialRing(QQ)
I = R.ideal([x^2 + y^2 - 1, x - y])
I.groebner_basis()            # [x - y, 2*y^2 - 1]，三角化后逐个解

GF(2) 上多项式与整数互转：

PR = PolynomialRing(GF(2),'x')
R.<x> = GF(2^2049)
pc = R.fetch_int(xx)                          # 整数 -> 多项式
xx = R(PR(pc)).integer_representation()       # 多项式 -> 整数

拉格朗日插值与极小多项式：

PR = PolynomialRing(Zmod(p), 'x')
f = PR.lagrange_polynomial(points)   # 插值恢复多项式（Shamir 秘密分享等）

f = algdep(alpha, k)                 # 用 α 的近似值找可能的 k 次整系数极小多项式

连分数（Wiener 攻击标配）

cf = continued_fraction(e / n)     # 连分数展开
convergents = cf.convergents()     # 渐近分数列表

for kd in convergents:
    k = kd.numerator()             # 渐近分数的分子 → k
    d = kd.denominator()           # 分母 → d
    if k == 0 or (e * d - 1) % k != 0:
        continue
    phi = (e * d - 1) // k
    s = n - phi + 1                # s = p + q
    delta = s^2 - 4 * n
    if delta < 0:
        continue
    sqrt_delta = isqrt(delta)
    if sqrt_delta^2 != delta:      # 判别式是完全平方才分解成功
        continue
    p = (s + sqrt_delta) // 2
    q = (s - sqrt_delta) // 2

也可以不解判别式，直接用多项式环按韦达定理解 x² - (n-phi+1)x + n = 0：

x = PolynomialRing(RationalField(), "x").gen()
f = x**2 - (n - phi + 1) * x + n
roots = f.roots()
if len(roots) == 2:
    p, q = int(roots[0][0]), int(roots[1][0])

矩阵与线性代数

A = matrix(ZZ, [[1,1],[0,4]])          # 也可以 Matrix(ZZ, ...)
A.nrows() / A.ncols()                  # 行数 / 列数
A.transpose()                          # 转置
A.inverse() 或 A^(-1)                  # 逆矩阵
A.rank()                               # 秩
A.det()                                # 行列式
A.trace()                              # 迹
A.eigenvalues()                        # 特征值
A.eigenvectors_right()                 # 右特征向量
A.stack(v)                             # 底部添加一行（也可 stack(matrix(...)) 循环堆行）
A.augment(B)                           # 右侧拼接一列/一个矩阵（横向拼接）
A.insert_row(1, vector([1,2]))         # 插入行
A.change_ring(QQ)                      # 更换元素所在环（ZZ -> QQ 等）
A.solve_left(B)  或 A/B                # 解 XA = B；B=向量时返回 v 在行基下的坐标
A.solve_right(B) 或 A\B                # 解 AX = B（QQ 上是精确高斯消元）
A.left_kernel()  / A.right_kernel()    # 左/右零空间（核）
A.left_kernel_matrix()                 # 左核的基矩阵
A.right_kernel_matrix()                # 右核的基矩阵：饱和整数核格的基！
A.LLL()                                # LLL 格基规约
A.LLL(delta=0.99)                      # delta 调高（默认 0.75）约化更彻底但更慢
A.BKZ(block_size=20)                   # BKZ 规约，效果更好但更慢
A.multiplicative_order()               # 乘法阶
L.rows()                               # 遍历矩阵的行（LLL 后逐行筛解常用）
L[0]                                   # 取第一行
v.norm()                               # 向量范数

matrix.zero(2,3) / zero_matrix(2,3)            # 零矩阵
matrix.identity(2) / identity_matrix(ZZ, 2)    # 单位阵
block_matrix(ZZ, [[A, zero_matrix(n,1)], [matrix(b), matrix([1])]])  # 分块拼接

MatrixSpace(GF(p), n, n)               # 矩阵空间，可对普通矩阵做换域 Mat_p(A)

构造矩阵的两种轻量手法（不想用 block_matrix 时）：

# 手法一：建零矩阵后逐元素赋值
L = Matrix(ZZ, 8, 8)
L[0,0] = n
L[6,2] = c1r * X
...

# 手法二：分块切片赋值（高斯整数 2x2 块展开用）
out = Matrix(ZZ, 2*len(mat), 2*len(mat[0]))
for r in range(len(mat)):
    for c in range(len(mat[0])):
        out[2*r:2*r+2, 2*c:2*c+2] = block(mat[r][c])   # 2x2 子块直接赋值

解线性方程组 AX = B：

A = Matrix([[1,2,3],[3,2,1],[1,1,1]])
Y = vector([0,-4,-1])
X = A.solve_right(Y)
# 反斜杠 \ 是 solve_right 的简写：X = A \ Y

核向量的重要细节：right_kernel_matrix() 给的是饱和整数核格的基，直接 LLL 是安全的；而 sympy 的 Matrix.nullspace() 只给有理零空间基，通分后可能只是有限指数子格，在其上 LLL 会丢向量。

lift_centered——把模 p 系数提升到 (−p/2, p/2] 的中心化整数，控制组合结果的大小：

1	`vector(N.left_kernel_matrix()[0, 2::-1]).lift_centered()`

解符号方程组：

1
2
3

var('x y')
solve([x+y==10, x*y==21], [x,y])
solve(x^2 == 2, x, solution_dict=True)   # 用 dict 形式取解

Coppersmith 与 `small_roots`

Zmod(n) 上的首一低次多项式可以求模 n 下的小根。关键三步：建环 → 构造首一多项式 → 调 small_roots：

PR.<x> = PolynomialRing(Zmod(n))
f = p + x                              # 已知 p 高位，未知低位
res = f.small_roots(X=2^100, beta=0.4) # X: 根的上界; beta: p 相对 n 的位宽比例
p = int(res[0]) + p                    # 恢复完整 p

通用模板（含参数调优与爆破）：

def partial_prime_known_highbits(n, known_high, unknown_bits):
    f = known_high * 2^unknown_bits + x
    roots = f.small_roots(X=2^unknown_bits, beta=0.4, epsilon=0.01)
    for r in roots:
        p = int(known_high * 2^unknown_bits + r)
        if p and n % p == 0:
            return p

beta 的语义：根是"n 的 beta 比例大小因子"的根——已知 p 高位分解 n 时 beta=0.5（因子 ≈ √N），实际常用 0.4；beta=1 对应根以 n 本身为模（如明文）。理论上界 X < N^(β²/ε)。题目没给位宽时用 N.nbits() // 2 - bits_known 推 X。

e 很小（如 e=3）且明文有可枚举的已知结构时，直接对 (已知部分 + x)^e - c 求小根。注意：最高次系数可能不等于 1，需要先手动首一化——用环元素求逆：

P.<x> = PolynomialRing(Zmod(n))
f = (x * shift + h_val)^e - c

# 关键：首一化。最高次项系数模 n 求逆后乘上去
coeff = f.coefficients()[-1]
f_monic = f * (coeff^-1)               # sage 环元素可直接用 ^-1 求逆

roots = f_monic.small_roots(X=2^(8*L), beta=1, epsilon=0.05)

镜像方向——已知 p 的低位时，未知的高位放 x、低位乘 2^k 挪到常数侧，同样 beta=0.5：

1 2	`f = x * 2^low_bits + p_low roots = f.small_roots(X=X, beta=0.5)`

e=3 无填充的小指数明文，X 直接取 floor(N^(1/e))。

手搓 Coppersmith（不靠 small_roots，理解原理/自定义格时用）：对 (M·X^i + x_i)^e 二项式展开，X^i 缩放各列，LLL 后除回 X^i 重组多项式求整数根：

X = 2^x_bits
M_matrix = Matrix(ZZ, e + 1, e + 1)
for i in range(e):
    M_matrix[i, i] = X^i
# 第 e 行放二项式展开系数：binomial(e, i) * M^(e-i) mod N，末位 X^e
...
L = M_matrix.LLL()
coeffs = [L[0, i] // (X^i) for i in range(e+1)]    # 除回缩放因子
P.<x> = PolynomialRing(ZZ)
g = sum(coeffs[i] * x^i for i in range(len(coeffs)))
roots = g.roots()                                   # 整数环上求根

高斯整数与复数域 Coppersmith

复数系数问题（Z[i] 上的 RSA/Coppersmith）的核心技巧：把 a+bi 同构映射为 2×2 整数矩阵 [[a,b],[-b,a]]，格维度翻倍后交给 LLL（sage 的 LLL 只吃整数矩阵）：

def block(z):
    a, b = z
    return Matrix(ZZ, 2, 2, [a, b, -b, a])

def expand(mat):
    out = Matrix(ZZ, 2 * len(mat), 2 * len(mat[0]))
    for r in range(len(mat)):
        for c in range(len(mat[0])):
            out[2*r:2*r+2, 2*c:2*c+2] = block(mat[r][c])
    return out

复数域 Coppersmith 的 8×8 格（三次多项式 f(z) 与其共轭 i·f̄(z) 各占一行，维度规律 2(d+1)）：

L = Matrix(ZZ, 8, 8)
L[0,0] = n; L[1,1] = n
L[2,2] = n*X; L[3,3] = n*X
L[4,4] = n*X^2; L[5,5] = n*X^2

L[6,0] = c0r; L[6,1] = c0i
L[6,2] = c1r*X; L[6,3] = c1i*X
L[6,4] = c2r*X^2; L[6,5] = c2i*X^2
L[6,6] = X^3

L[7,0] = -c0i; L[7,1] = c0r
L[7,2] = -c1i*X; L[7,3] = c1r*X
L[7,4] = -c2i*X^2; L[7,5] = c2r*X^2
L[7,7] = X^3

L_red = L.LLL()

LLL 收尾——短向量按 X^j 缩放除回，重组为二次域上的多项式求根，并验证实虚部都是整数：

K.<i> = QuadraticField(-1)
R.<x> = PolynomialRing(K)

for v in L_red.rows():
    Q = (v[0] + v[1]*i) + (v[2]/X + v[3]/X*i)*x \
        + (v[4]/X^2 + v[5]/X^2*i)*x^2 + (v[6]/X^3 + v[7]/X^3*i)*x^3
    for root, _ in Q.roots():
        coeffs = root.list()
        if len(coeffs) == 1:
            coeffs.append(0)
        if coeffs[0] in ZZ and coeffs[1] in ZZ:     # 判高斯整数
            x_val, y_val = ZZ(coeffs[0]), ZZ(coeffs[1])

配套小工具：

def sym_mod(v, mod):
    # 对称代表元：把系数折到 (-mod/2, mod/2]，缩小格范数
    v = ZZ(v) % mod
    if v > mod // 2:
        v -= mod
    return ZZ(v)

# 高斯整数带余除法：最近取整惯用法
q = ZZ(floor(QQ(num) / QQ(den) + QQ(1) / 2))

# 高斯素数生成：p ≡ 1 (mod 4) 的素数写成两平方和，a+bi 即高斯素数
ell = random_prime_1mod4(bits)     # 自己枚举 random_prime 后验 p % 4 == 1
a, b = two_squares(ell)

# 高斯整数 RSA 的私钥：两个范数素数的 lcm 指数
d = inverse_mod(E, lcm(np - 1, nq - 1))    # 用 lcm 而非 φ

调参套路：格里的缩放因子（系数 scale、嵌入 scale）影响 LLL 成功率，失败时按列表网格搜索：

for cs in [4, 2, 8, 1, 16, 32, 64]:
    for es in EMBED_SCALES:
        for v in expand(mat).LLL().rows():
            ...  # 逐行筛目标形状的短向量

离散对数

# 合数模 / 一般情况（内部自动选算法，含 Pohlig-Hellman）
x = discrete_log(mod(b,n), mod(a,n))
x = discrete_log(c, g, ord=order)      # 已知阶可大幅加速；p-1、q-1 光滑时直接梭
x = discrete_log(h, g, mod=p, algorithm='bsgs')   # 指定 Baby-step Giant-step
x = discrete_log(h, g, mod=p, algorithm='rho')    # 指定 Pollard Rho

# 椭圆曲线上：加 operation='+'
key = discrete_log(Q, G, operation='+')
key = discrete_log(Q, G, ord=8, operation='+')    # 小因子子群分别求再 CRT

# 乘法群元素的 log 方法写法（与全局函数等价）
k = beta.log(alpha)        # 在 F_{p^k}* 中解 beta = alpha^k

# 质数或素数幂模（Index Calculus）
R = Integers(99)
a = R(4)
b = a^9
b.log(a)

# pari 备选
x = int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))"))
x = gp.znlog(b, gp.Mod(a, n))

配套常用：

1
2
3

R = Integers(factor)
order = R(g).multiplicative_order()    # 求阶，配合 discrete_log 的 ord 参数
CRT([k_mod_8, k_mod_3], [8, 3])        # 列表形式 CRT（与 crt 等价）

合数模 DLP 的标准流程：把 n 分解 → 对每个素因子幂单独求 discrete_log → 各部分以对应阶为模 → crt(remainders, moduli) 合并。模 p^k 的部分若 sage 不自动升次，可手写 p-adic 线性提升（Hensel lift）：

def linear_lift(g, c, p, k):
    """求解 g^x = c mod p^k：先求 x0 = dlog(c) mod p，再线性提升"""
    x = discrete_log(GF(p)(c), GF(p)(g))
    for i in range(1, k):
        mod = p**(i+1)
        # 偏差 beta = (c / g^x - 1) / p^i
        curr_val = power_mod(g, x, mod)
        chk = (c * inverse_mod(curr_val, mod)) % mod
        beta = (chk - 1) // p**i
        # 梯度 alpha = (g^((p-1)p^(i-1)) - 1) / p^i
        step_pow = (p-1) * p**(i-1)
        base = power_mod(g, step_pow, mod)
        alpha = (base - 1) // p**i
        d = (beta * inverse_mod(alpha, p)) % p
        x += d * step_pow
    return x

矩阵 DLP（B = A^k mod n）：把矩阵搬到各素因子域上，能对角化就对特征值求 dlog，否则行列式降维 det(A)^k = det(B)，最后 CRT：

Fp = GF(p)
Mat_p = MatrixSpace(Fp, A.nrows(), A.ncols())
A_p, B_p = Mat_p(A), Mat_p(B)

char_poly = A_p.charpoly()             # 特征多项式
roots = char_poly.roots()              # 特征值
if roots_count == A_p.nrows() and A_p.is_diagonalizable():
    eig_A = A_p.eigenvalues()[0]       # A^k 的特征值 = A 特征值的 k 次幂
    k_mod = discrete_log(B_p.eigenvalues()[0], eig_A)
    order = eig_A.multiplicative_order()
else:
    k_mod = discrete_log(B_p.det(), A_p.det())   # 行列式法
    order = A_p.det().multiplicative_order()

k = crt(rems, mods)

n = p² 的版本用 p-adic：Zp(p, prec=2) 上求特征多项式的根，利用 p-adic log 把主体部分化为对数之商 k = log(mu^(p-1)) / log(la^(p-1))，小子群部分普通 discrete_log，再 CRT + 爆破验证 a**k == b：

P = Zp(p, prec=2)
f_A = a.charpoly().change_ring(ZZ).change_ring(P)
la = f_A.roots(multiplicities=False)[0]
mu = f_B.roots(multiplicities=False)[0]
k_ = int(((mu**(p-1)).log() / (la**(p-1)).log()).lift())

椭圆曲线

E = EllipticCurve(GF(p), [A, B])       # 曲线 y² = x³ + Ax + B
E = EllipticCurve(GF(p), [0, 4])       # y² = x³ + 4（短 Weierstrass，系数缺省为 0）
E = EllipticCurve(Qp(p, 2), [a1,a2,a3,a4,a6])   # p-adic 域上建曲线（Smart's attack）
E = EllipticCurve('11a')               # 命名曲线（有理数域）
E.order()                              # 曲线的点的个数（#E）
E.discriminant()                       # 判别式，0 即奇异（也可手算 4a³+27b²）
E.rank() / E.gens()                    # 有理点群的秩与生成元
G = E.random_point()                   # 随机点
G = E.gens()[0]                        # 取生成元
G = E.lift_x(F(x))                     # 由 x 坐标恢复曲线上的点
G.order()                              # 点的阶
E(0)                                   # 无穷远点（单位元）；也可 P.curve()(0)
P.xy()                                 # 点的仿射坐标 (x, y)
P.curve()                              # 从点反取所在曲线
E.is_on_curve(x, y)                    # 判断点是否在曲线上
Q = key * G                            # 标量乘
P1 + P2                                # 点加法

由曲线上两点反解 A、B（参数未知时）：

A = (y1**2 - y2**2 - x1**3 + x2**3) / (x1 - x2)
B = y1**2 - x1**3 - A*x1
E = EllipticCurve(F, [A, B])
G, Q = E(x1, y1), E(x2, y2)

key = discrete_log(Q, G, operation='+')   # ECDLP

三类弱曲线判定：

# 奇异曲线：判别式为 0
4*a^3 + 27*b^2 == 0
# 异常曲线（Smart's attack）：#E == p
E.order() == p
# 超奇异曲线（MOV attack）：Frobenius 迹 t = p + 1 - #E 满足 t % p == 0
t = p + 1 - E.order()
t % p == 0

Smart’s attack（异常曲线 #E(F_p) = p，用 p-adic lift 直接算私钥）：

def smart_attack(P, Q, p):
    E = P.curve()
    Ep = EllipticCurve(Qp(p, 2), [E.a1(), E.a2(), E.a3(), E.a4(), E.a6()])
    P_Qp = Ep.lift_x(ZZ(P.xy()[0]))
    Q_Qp = Ep.lift_x(ZZ(Q.xy()[0]))
    p_times_P = p * P_Qp
    p_times_Q = p * Q_Qp
    x_P, y_P = p_times_P.xy()
    x_Q, y_Q = p_times_Q.xy()
    phi_P = -(x_P / y_P)
    phi_Q = -(x_Q / y_Q)
    k = phi_Q / phi_P
    return ZZ(k)      # p-adic 商截断为整数

MOV attack（超奇异/嵌入度小，把 ECDLP 归约到扩域乘法群 dlog）：

# 嵌入度：最小的 k 使 n | (q^k - 1)（超奇异曲线 k ≤ 6）
def embedding_degree(q, n):
    k = 1
    while (q^k - 1) % n != 0:
        k += 1
    return k

k = embedding_degree(p, n)
F_ext = GF(p^k)                        # 扩域
E_ext = EllipticCurve(F_ext, [a, b])
G_ext = E_ext(G)                       # 点提升到扩域（自动 coercion）
P_ext = E_ext(P)
# 或直接提升整条曲线：Ek = E.base_extend(GF(p^k))

def find_T(E_ext, G_ext, n):
    # 扩域上找 n 阶辅助点：随机 x → is_square 判 QR → sqrt 得 y
    for _ in range(100):
        x = F_ext.random_element()
        rhs = x^3 + 1
        if rhs.is_square():
            y = rhs.sqrt()
            T = E_ext.point((x, y))
            if n * T == E_ext(0):              # n·T = O 判阶
                pair = E_ext.weil_pairing(G_ext, T, n)
                if pair != 1:                  # 配对为 1 说明与 G 线性相关，跳过！
                    return T

alpha = E_ext.weil_pairing(G_ext, T, n)
beta = E_ext.weil_pairing(P_ext, T, n)
k = beta.log(alpha)                            # 扩域乘法群 dlog
# Tate 配对更快（四参数，多一个嵌入度）
pair = E.tate_pairing(P, Q, n, k)

小阶子群上的 ECDLP（点不在标准曲线上时可对每个候选 c 建曲线）：

curve = EllipticCurve(GF(P), [A, c])
base = curve(x, y)
point = curve(rx, ry)
k = int(discrete_log(point, base, ord=order, operation='+'))

低阶 torsion 点 + CRT 是常见套路：逐 bit 用不同子群的点组合加密时，在每个小子群上分别解 dlog，再 CRT 合并出标量。Invalid curve 攻击则是枚举曲线参数 a,b 找 E_try.order() % 小因子 == 0 的弱曲线。

奇异曲线：三次多项式有重根时曲线退化，用 factor 找出奇异点 r，映射 s = (x-r)/(y+c/2) 把 ECDLP 变成域上除法：

F = GF(p)
R.<x> = PolynomialRing(F)
f = x^3 + F(b)*x^2 + F(d)*x + F(e) + F(c)^2/4
r = f.roots(multiplicities=False)[0]

tg = (F(gx) - r) / (F(gy) + F(c)/2)
tp = (F(px) - r) / (F(py) + F(c)/2)
m = ZZ(tp / tg)          # ZZ() 把域元素转回整数

格与 LLL/BKZ

最简模板（矩阵里藏着一行小值）：

aaa = Matrix(ZZ, output)
L = aaa.LLL()
# 最短向量就是目标行，必要时除以 GCD 归一化
g = GCD(L[0])
lis = list(map(abs, L[0]/g))

解线性方程组 s 满足 c_i·s = rhs_i 且 s 很小——把每条方程扩一行 [c_i | -rhs_i]，目标 (s, 1) 就在右核里，QQ 求核 → 清分母 → LLL：

M = Matrix(ZZ, [list(row) + [-int(rhs)] for row, rhs in zip(eq_rows, eq_rhs)])

# QQ 上求右核
Kq = M.change_ring(QQ).right_kernel().basis_matrix()

# 逐行清分母转成整数格基
K_rows = []
for r in Kq.rows():
    den = ZZ(1)
    for x in r:
        den = lcm(den, ZZ(x.denominator()))
    K_rows.append([ZZ(x * den) for x in r])
K = Matrix(ZZ, K_rows)

K_red = K.LLL()
# LLL 后的基向量 v 应为 ±k*(s,1)：用 v[-1] 归一化并验证

递推关系挖掘（序列满足的短线性递推）：观测序列排成滑动窗口矩阵，对右核格做 LLL，最短向量即精确递推关系：

Y = matrix(ZZ, 3, 11)
for i in range(3):
    Y[i] = vector(dy[i:i+11])
rkm = Y.right_kernel_matrix().LLL()[:-2]   # 核基 → LLL → 丢掉最长的"坏关系"

“解空间里钓特殊形状成员”：把解空间的基与目标形状向量（如等比向量）堆叠成矩阵取左核，把满足隐藏结构的成员钓出来：

rkm2 = M.right_kernel_matrix().LLL()
k = ZZ(rkm2.solve_left(dy[1:])[2])         # solve_left 求 v 在行基下的坐标（c·B = v）
rkm2 *= k                                  # 用坐标做尺度归一化

N = rkm2[::-1].stack(vector(a^i for i in range(len(dy)-1)))   # [::-1] 倒序切片
dx = vector(N.left_kernel_matrix()[0, 2::-1]).lift_centered() * rkm2

Kannan 嵌入（CVP → SVP）：目标向量作为额外一列，右下角放缩放因子：

M_embed = Matrix(ZZ, m + n + 1, m + n + 1)
for i in range(m + n):
    for j in range(m + n):
        M_embed[i, j] = M[i, j]
    M_embed[i, m + n] = target[i]
for scale in [1, 10, 100, 1000]:           # scale 多值尝试是实用调试技巧
    M_embed[m + n, m + n] = scale
    L_embed = M_embed.LLL()

模数背包格（s = Σ m_i·a_i mod q）：单位阵编码 0/1 未知量，末行放公钥与 −s，末列放 q 处理取模；LLL 后筛「分量全为 0/±1」的行：

M_big = Matrix(ZZ, n + 2, n + 2)
for i in range(n):
    M_big[i, i] = 1
    M_big[n, i] = a_list[i]
M_big[n, n] = -s
M_big[n, n+1] = q
M_big[n+1, n+1] = 1
L = M_big.LLL()

HNP 格（Hidden Number Problem，ECDSA nonce 高位泄露的数学本质）：对角线放 p，一列放 t_i、一列放 u_i，嵌入列放 X = 2^(p.nbits() − bits_leaked)；从 |vec[-1]| == X 的短向量反解 α：

M_ext = Matrix(ZZ, n + 2, n + 2)
for i in range(n):
    M_ext[i, i] = p
    M_ext[i, n] = t_list[i]
    M_ext[i, n+1] = u_list[i]
M_ext[n, n] = 1
M_ext[n+1, n+1] = X
L = M_ext.LLL()
for vec in L.rows():
    if abs(vec[-1]) == X:
        alpha_candidate = (-vec[n] * inverse_mod(vec[-1] // X, p)) % p

低噪声 LWE / 带泄露的秘密恢复——q-ary 格 + IntegerLattice 的 Babai：

from sage.modules.free_module_integer import IntegerLattice

basis = block_matrix(ZZ, [
    [identity_matrix(ZZ, N), zero_matrix(ZZ, N, extra)],
    [Aprime, q * identity_matrix(ZZ, extra)],
])

lattice = IntegerLattice(basis.transpose(), lll_reduce=True)
closest = vector(ZZ, lattice.babai(b))        # Babai 最近平面算法
# 不行就上 closest_vector（CVP 精确解，慢）
closest = vector(ZZ, lattice.closest_vector(b))
# 或用 sage.crypto.lattice 的现成接口
from sage.crypto.lattice import closest_vector as cv

截断输出类问题（LFSR/带噪方程）常用 BKZ(block_size=20)：造 Matrix(ZZ) 格 → 规约 → 从短向量中提取候选 → PolynomialRing(GF(m)) 上迭代 gcd/monic() 收敛到目标多项式。

常用套路速查

场景	关键 API	套路
已知 p 高/低位分解 n	`PolynomialRing(Zmod(n))`, `small_roots(X=, beta=0.4)`	高位：f = p_high + x；低位：f = x·2^k + p_low
e 小 + 明文结构已知	`small_roots(X=, beta=1)`	先 `coeff^-1` 首一化；X = floor(N^(1/e))
d 过小（Wiener）	`continued_fraction(e/n).convergents()` + `isqrt`	渐近分数恢复 d，判别式分解 n
手搓 Coppersmith	`binomial` 展开 + `X^i` 缩放列 + `PolynomialRing(ZZ).roots()`	不依赖 small_roots
复数域/Z[i] Coppersmith	`block/expand` 2×2 嵌入 + `QuadraticField(-1)`	格维度 ×2 后 LLL，`root.list()` 收根
p-1/p+1 光滑分解	`ecm.factor(N)`	比 factor 快
p-1/q-1 光滑的 RSA/DLP	`discrete_log(c, 2, ord=...)`	直接调，内部 Pohlig-Hellman
合数模 DLP	`Integers`, `multiplicative_order`, `crt`	分因子求 dlog 再 CRT
模 p^k 的 DLP	`linear_lift` / `Zp(p)` + p-adic log	先 mod p 再 Hensel 提升
矩阵 DLP	`MatrixSpace`, `charpoly().roots()`, `det`	特征值或行列式降维
ECDLP	`EllipticCurve(GF(p),[A,B])`, `discrete_log(..., operation='+')`	小域直接解
异常曲线（#E=p）	`EllipticCurve(Qp(p,2),...)` + `lift_x`	Smart’s attack，p-adic 商直接得 k
超奇异/嵌入度小	`weil_pairing` / `tate_pairing` + `GF(p^k)`	MOV 攻击归约到乘法群
奇异曲线 ECDLP	`factor(f)`, `roots`	映射 (x−r)/(y+c/2) 为域上除法
小值藏在格中	`Matrix(ZZ, ...).LLL()`	最短向量即答案
小未知量线性方程组	`right_kernel` + `LLL` / `Matrix(QQ).solve_right`	核向量攻击 / 精确消元
序列短递推关系	`right_kernel_matrix().LLL()`	滑动窗口矩阵；注意它给的是饱和整数核
未知模数	`resultant` 取 gcd 后 `.factor()[-1][0]`	公共根 ⟹ 模数整除结式
CVP（有格基+目标）	Kannan 嵌入 / `IntegerLattice.babai`	嵌入列 scale 多值尝试
模数背包	单位阵 + 公钥行 + q 列	筛 0/±1 行
HNP / nonce 泄露	p 对角 + t_i, u_i 列 + X 嵌入列	`
低噪声 LWE	`IntegerLattice`, `babai`, `closest_vector`	q-ary 格
带泄露（Hamming 重量等）	`Matrix(QQ).rank()` 筛选 + `solve_right`	先转精确方程再消元
截断 LFSR	`BKZ(block_size=20)` + 多项式 `gcd`	格求消去多项式
多元方程组	`ideal([...]).groebner_basis()`	三角化逐个解
插值 / 极小多项式	`PR.lagrange_polynomial(points)`, `algdep(alpha, k)`	—
高次方程求根（大素数模）	`PolynomialRing(GF(P))` / `IntegerModRing(P)` + `f.roots()`	一行解决
sage 对象传输	`save` / `load`	`.sobj` 文件

容易踩的坑

^ 是幂不是异或：sage 里 2^130 等于 Python 的 2**130；把 sage 代码抄进 Python 要把 ^ 全改成 **，反之亦然。
符号变量先声明：var('x') 不声明直接用会 NameError；每次新会话都要重新声明。
环一定要选对：RSA/Coppersmith 用 Zmod(n)，椭圆曲线用 GF(p)，需要精确分数消元时用 QQ（solve_right 在 QQ 上是精确高斯消元，可检查 x.denominator() == 1 确认解为整数）。
small_roots 前先 monic()：最高次系数不是 1 时 Coppersmith 不适用，用 f * (coeff^-1) 手动首一化。
ZZ() / int() 转换：sage 域元素参与 hashlib 等纯 Python 计算前要转回 int；ZZ(tp/tg) 把域上元素精确转整数。另外 sage 的 Integer.to_bytes() 是最小长度，通用场景显式写 to_bytes(32, 'big')。
discrete_log 记得传 ord=：已知阶能避免不必要的阶计算，子群攻击时必须指定。
crt 支持非互质模数：crt(remainders, moduli) 的模数是各部分的阶而不一定是互素的素数，扩展 CRT 会自动处理。
p-adic 处理 p²/p^k 模数：Zmod(p^2) 上多项式求根经常失败，换 Zp(p, prec=2) 再 .lift() 回来。
right_kernel_matrix() ≠ nullspace：sage 给的是饱和整数核格的基（可直接 LLL）；sympy 的 nullspace() 是有理零空间基，通分后可能只是有限指数子格，LLL 会丢向量。
配对不为 1 才线性无关：MOV 里 weil_pairing(G, T, n) == 1 说明 T 是 G 的倍数，要换辅助点。
高斯整数慎用 GaussianIntegers()：该环上部分操作慢/不便，实战常用元组手写运算或 QuadraticField(-1) 替代。
常见报错速查：NameError: name 'x' is not defined → 变量未声明；TypeError: unsupported operand → 类型/环不兼容，检查矩阵与域类型；ValueError: matrix must be square → 非方阵；ZeroDivisionError → 检查分母是否可逆。

常用语法

https://ddanggui.top/2026/03/03/常用语法/

作者

ddanggui

发布于

2026年3月3日

许可协议

hgame部分上一篇

unictf 下一篇

常用语法

常用语法

常用语法

sympy

Sagemath

环境与导入

符号计算基础

环（Ring）与域（Field）

生成元语法 R.<x> = ...

数论

多项式

连分数（Wiener 攻击标配）

矩阵与线性代数

Coppersmith 与 small_roots

高斯整数与复数域 Coppersmith

离散对数

椭圆曲线

格与 LLL/BKZ

常用套路速查

容易踩的坑

生成元语法 `R.<x> = ...`

Coppersmith 与 `small_roots`