SageMath
2026/5/29工具工具SageMath大约 6 分钟
SageMath
链接
是什么
SageMath（简称 Sage）是一款开源的数学软件系统，旨在提供一个替代 Magma、Maple、Mathematica 和 MATLAB 的免费开源方案。它基于 Python 构建，集成了众多数学库，特别适合数论、代数、几何和密码学研究。
核心功能：
- 数论运算：大数运算、素性测试、因式分解
- 代数运算：多项式、矩阵、线性代数
- 椭圆曲线：椭圆曲线运算和离散对数
- 格基约减：LLL 算法及其变种
- 有限域运算：Galois 域运算
- 多项式环：各种多项式运算
- 组合数学：排列组合、图论
- 数值计算：数值分析和优化
在 CTF 密码学题目中，SageMath 是处理复杂数学问题的核心工具，特别适合 RSA、椭圆曲线、格密码等题目。
安装与配置
安装方法
# 方法一：使用系统包管理器（推荐）
# Ubuntu/Debian
sudo apt update
sudo apt install sagemath
# Arch Linux
sudo pacman -S sagemath
# macOS（Homebrew）
brew install sagemath
# 方法二：使用 Conda
conda install -c conda-forge sage
# 方法三：从源码编译
# 下载源码：https://www.sagemath.org/download.html
tar xzf sage-*.tar.gz
cd sage-*
make
# 方法四：使用 Docker
docker run -it sagemath/sagemath:latest
# 验证安装
sage --version环境配置
# 启动 Sage
sage
# 启动 Jupyter Notebook
sage -n jupyter
# 启动 Sage 命令行
sage -python
# 配置文件位置
~/.sage/init.sage配置 init.sage
# 在 ~/.sage/init.sage 中添加常用配置
# 设置默认精度
default_prec = 100
# 导入常用模块
from sage.all import *
# 设置随机种子
set_random_seed(42)基本用法
基本数学运算
# SageMath 使用 Python 语法，但增强了数学运算能力
# 大数运算
n = 2^100
print(n)
# 因式分解
factor(123456789)
# 最大公约数
gcd(123, 456)
# 最小公倍数
lcm(123, 456)
# 模运算
mod(123456789, 1000000007)
# 快速幂
power_mod(2, 100, 1000000007)数论函数
# 素性测试
is_prime(2^31 - 1)
# 下一个素数
next_prime(100)
# 前 N 个素数
primes_first_n(100)
# 素数计数
prime_pi(1000)
# 欧拉函数
euler_phi(100)
# 莫比乌斯函数
moebius(100)
# 整数分解
factorial(100)模运算和逆元
# 模逆元
inverse_mod(3, 7) # 3 在模 7 下的逆元
# 中国剩余定理
crt([2, 3, 2], [3, 5, 7])
# 求解模方程
# x^2 ≡ 1 (mod 7)
Mod(1, 7).sqrt()
# 离散对数
# g^x ≡ h (mod p)
p = 101
g = 2
h = 10
discrete_log(Mod(h, p), Mod(g, p))多项式运算
# 定义多项式环
R.<x> = PolynomialRing(ZZ)
# 定义多项式
f = x^3 + 2*x^2 + 3*x + 4
# 多项式求值
f(2)
# 多项式因式分解
factor(f)
# 多项式 GCD
g = x^2 + 1
gcd(f, g)
# 求根
f.roots()矩阵运算
# 定义矩阵
A = matrix(ZZ, [[1, 2], [3, 4]])
# 矩阵运算
B = matrix(ZZ, [[5, 6], [7, 8]])
A + B
A * B
# 矩阵求逆
A.inverse()
# 行列式
A.det()
# 特征值和特征向量
A.eigenvalues()
A.eigenvectors_right()
# 高斯消元
A.echelon_form()有限域运算
# 定义有限域
F = GF(2^8) # GF(256)
# 有限域元素
a = F(123)
b = F(456)
# 有限域运算
a + b
a * b
a^(-1) # 逆元
# 有限域上的多项式
R.<x> = PolynomialRing(F)
f = x^3 + x + 1CTF常用技巧
RSA 相关计算
# RSA 基本运算
p = random_prime(2^512, lbound=2^511)
q = random_prime(2^512, lbound=2^511)
n = p * q
phi = (p-1) * (q-1)
e = 65537
d = inverse_mod(e, phi)
# RSA 加密
m = int.from_bytes(b"flag{test}", "big")
c = power_mod(m, e, n)
# RSA 解密
m_dec = power_mod(c, d, n)
print(int_to_bytes(m_dec))
# Wiener 攻击（小私钥指数）
def wiener_attack(n, e):
# 连分数展开
cf = continued_fraction(Integer(e)/Integer(n))
convergents = cf.convergents()
for c in convergents:
k = c.numerator()
d = c.denominator()
if k == 0:
continue
phi = (e*d - 1) // k
# 求解二次方程
b = n - phi + 1
discriminant = b^2 - 4*n
if discriminant >= 0:
sqrt_disc = isqrt(discriminant)
if sqrt_disc^2 == discriminant:
p = (b + sqrt_disc) // 2
q = (b - sqrt_disc) // 2
if p * q == n:
return d
return None椭圆曲线运算
# 定义椭圆曲线
# y^2 = x^3 + ax + b (mod p)
p = 17
a = 2
b = 3
E = EllipticCurve(GF(p), [a, b])
# 曲线上的点
P = E(5, 1)
Q = E(10, 6)
# 点加法
R = P + Q
print(R)
# 标量乘法
R = 10 * P
print(R)
# 椭圆曲线阶
order = E.order()
print(f"Curve order: {order}")
# 离散对数（小阶情况）
# 求解 k*P = Q
k = discrete_log(Q, P, operation='+')
print(f"k = {k}")
# MOV 攻击（适用于弱曲线）
# 当曲线的 embedding degree 较小时
def mov_attack(E, P, Q):
k = E.embedding_degree()
if k > 100:
return None
# 将 ECDLP 转换为有限域上的 DLP
# ...格基约减（LLL）
# LLL 算法用于格基约减
# 常用于 RSA 多密钥攻击、背包密码等
# 定义格基矩阵
M = matrix(ZZ, [
[1, 0, 0, 0, 100],
[0, 1, 0, 0, 200],
[0, 0, 1, 0, 300],
[0, 0, 0, 1, 400]
])
# LLL 约减
reduced = M.LLL()
print(reduced)
# BKZ 约减（更强的约减算法）
reduced = M.BKZ()
print(reduced)
# Coppersmith 攻击
# 已知明文的高位或低位
# 使用 small_roots() 方法Coppersmith 攻击
# RSA 小指数攻击
# 已知明文的高位
def coppersmith_high_bits(n, e, c, high_bits, bits_length):
P.<x> = PolynomialRing(Zmod(n))
f = (high_bits + x)^e - c
roots = f.small_roots(X=2^bits_length, beta=1)
if roots:
return high_bits + roots[0]
return None
# 使用示例
# 已知明文的高 200 位
# m = high_bits + low_bits
# low_bits < 2^200离散对数问题
# 小规模离散对数
p = 101
g = Mod(2, p)
h = Mod(10, p)
x = discrete_log(h, g)
print(f"2^x ≡ 10 (mod 101), x = {x}")
# Pohlig-Hellman 算法（当阶是光滑数时）
p = 2^64 + 1 # 费马素数
g = Mod(3, p)
h = Mod(123456789, p)
x = discrete_log(h, g)
print(f"x = {x}")
# Baby-step Giant-step 算法
def bsgs(g, h, p, n):
m = isqrt(n) + 1
table = {}
for j in range(m):
table[power_mod(g, j, p)] = j
g_inv_m = power_mod(g, -m, p)
for i in range(m):
val = (h * power_mod(g_inv_m, i, p)) % p
if val in table:
return i * m + table[val]
return None中国剩余定理应用
# CRT 解决同余方程组
# x ≡ 2 (mod 3)
# x ≡ 3 (mod 5)
# x ≡ 2 (mod 7)
remainders = [2, 3, 2]
moduli = [3, 5, 7]
x = crt(remainders, moduli)
print(f"x = {x}")
# 验证
assert x % 3 == 2
assert x % 5 == 3
assert x % 7 == 2大数分解
# Pollard's rho 算法
def pollard_rho(n):
from random import randint
x = randint(2, n-1)
y = x
c = randint(1, n-1)
d = 1
while d == 1:
x = (x*x + c) % n
y = (y*y + c) % n
y = (y*y + c) % n
d = gcd(abs(x-y), n)
if d != n:
return d
return None
# 使用 Sage 内置分解
n = 123456789012345678901234567890
factor(n)
# ECM 算法（椭圆曲线方法）
ecm.factor(n)二次剩余
# 求解 x^2 ≡ a (mod p)
p = 101
a = Mod(10, p)
# 判断是否为二次剩余
a.is_square()
# 求平方根
x = a.sqrt()
print(f"x = {x}, x^2 = {x^2}")
# Tonelli-Shanks 算法
def tonelli_shanks(n, p):
if pow(n, (p-1)//2, p) != 1:
return None
q = p - 1
s = 0
while q % 2 == 0:
q //= 2
s += 1
z = 2
while pow(z, (p-1)//2, p) != p-1:
z += 1
m = s
c = pow(z, q, p)
t = pow(n, q, p)
r = pow(n, (q+1)//2, p)
while t != 1:
i = 1
while pow(t, 2^i, p) != 1:
i += 1
b = pow(c, 2^(m-i-1), p)
m = i
c = b^2 % p
t = t * c % p
r = r * b % p
return r编码解码辅助
# 整数转字节
def int_to_bytes(n):
return n.to_bytes((n.bit_length() + 7) // 8, 'big')
# 字节转整数
def bytes_to_int(b):
return int.from_bytes(b, 'big')
# 长整数转十六进制
hex(123456789)
# 十六进制转长整数
int("deadbeef", 16)常见问题
SageMath 启动慢
原因：SageMath 需要加载大量数学库。
解决：
- 使用
sage -python只加载核心功能 - 使用 Jupyter Notebook 按需加载
- 预编译 Sage：
sage -b
内存不足
解决：
# 增加内存限制
# 在启动时设置
sage -m 8G # 分配 8GB 内存
# 或使用更高效的算法某些函数找不到
解决：
# 确保导入了正确的模块
from sage.all import *
# 查看函数帮助
help(function_name)
# 搜索函数
search_doc('keyword')与 Python 标准库冲突
解决：
# 使用完整的模块路径
import sage.rings.integer
# 或重命名导入
from sage.all import Integer as SageInteger安装失败
解决：
- 检查系统依赖是否满足
- 使用 Conda 安装（最简单）
- 使用 Docker 镜像
输出格式问题
解决：
# 强制转换为 Python 类型
int(sage_integer)
float(sage_real)
str(sage_symbolic)
# 设置输出精度
n(digits=50)