常用工具
古典密码
维吉尼亚密码(Vigenere):
gmpy2
1
2
3
4
5
6
7
8
9import gmpy2
gmpy2.mpz(n) #初始化一个大整数
gmpy2.mpfr(x) # 初始化一个高精度浮点数x
d = gmpy2.invert(e,n) # 求逆元,de = 1 mod n
c = gmpy2.powmod(m,e,n) # 幂取模,结果是 c = m^e mod n
gmpy2.is_prime(n) #素性检测
gmpy2.gcd(a,b) #欧几里得算法,最大公约数
gmpy2.gcdext(a,b) #扩展欧几里得算法
gmpy2.iroot(x,n) #x开n次根
Sage
定义
1
2
3
4
5
6R.<X> = PolynomialRing(Zmod(n))
#Zmod(n):指定模,定义界限为n的环;Z表示整数;指定模是划定这个环的界限,就是有效的数字只有从0到n,其他的都通过与n取模来保证在0~n这个范围内;Zmod代表这是一个整数域中的n模环
#ZZ:整数环;QQ:有理数环;RR:实数环;CC:复数环
#R:只是一个指针,指向用polynomialring指定的那个环(可以使用任意字符)
#PolynomialRing:这个就是说建立多项式环
#.<X>:指定一个变量的意思(可以用任意字符)解方程
$\begin{cases} x+y=10\\xy=21 \end{cases} $
1
2var('x y')
solve([x+y==10,x*y==21],[x,y])解线性方程组
$AX=B$
1
2
3
4
5
6A = Matrix([[1,2,3],[3,2,1],[1,1,1]])
Y = vector([0,-4,-1])
X = A.solve_right(Y)
#或
A \ Y
#反斜杠 \ 可以代替 solve_right; 用 A \ Y 代替 A.solve right(Y).求逆元
$ed=1\pmod {\varphi(n)}$
1
d = inverse_mod(e,fn) # sage求逆元
扩展欧几里得算法
1
2d,u,v=xgcd(20,30)
print("d:{0} u:{1} v:{2}".format(d,u,v)) #d:10 u:-1 v:1CRT(中国剩余定理)
$\begin{cases} x\equiv2\pmod3\\x\equiv3\pmod5\\x\equiv2\pmod7 \end{cases} $
1
crt([2,3,2],[3,5,7])
1
2
3
4
5
6
7
8
9#仅适用模两两互素
def chinese_remainder(modulus, remainders):
Sum = 0
prod = reduce(lambda a, b: a*b, modulus)
for m_i, r_i in zip(modulus, remainders):
p = prod // m_i
Sum += r_i * (inverse_mod(p,m_i)*p)
return Sum % prod
chinese_remainder([3,5,7],[2,3,2]) #23离散对数
$2^x \equiv 13 \pmod {23}$
1
2x = discrete_log(mod(13,23),mod(2,23))
print(x)欧拉函数
$\varphi(x)=x\prod\limits_{i=1}^n(1-\frac{1}{p_i})$
1
print(euler_phi(71)) #70
创建整数域中的椭圆曲线
$y^2=x^3+a_4x+a_6$
输出所有整数点
1
2
3
4
5
6
7
8
9
10
11
12
13
14#素数域
F = GF(7)
#素数域的阶
print(F.order())
#椭圆曲线E7(2,3)
E = EllipticCurve(F,[0,0,0,2,3])
#基点坐标
G = E.gens()[0]
#阶
q = E.order()
#所有的点
allPoints = E.points()
#创建点
P = E(2,1)参考:
https://jayxv.github.io/2020/05/20/sage%E5%B8%B8%E7%94%A8%E5%91%BD%E4%BB%A4/
WolframAlpha