根
nth_root() x m = k x^m=k x m = k
1 2 3 #x=k.nth_root(m) x=27.nth_root(3) x = mod(27, 2^120).nth_root(3)
这里也可以构造多项式求解,处理模下的问题时就把ZZ换成Zmod(n)而且要multiplicities=False，就是不需要计算重数。
1 2 3 P.<x>=PolynomialRing(ZZ) f=x^m-k x=f.roots(multiplicities=False)
线性代数
charpoly() M M M
1 x=M.charpoly().roots(multiplicities=False)
和roots()函数结合就可以直接求得特征值。eigenvectors M M M
1 x=M.eigenvectors_right()
返回M M M M v = λ v M v =\lambda v M v = λ v solve_left()/solve_right() A x = b A \pmb{x}=\pmb{b} A x x = b b x A = b \pmb{x} A= \pmb{b} x x A = b b
1 x=M.solve_left(b) #x=M.solve_right(b)
companion_matrix(poly,format)
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 poly = [-2, -3, -4, -5, -6, 1] R = companion_matrix(poly, format='right'); R [0 0 0 0 2] [1 0 0 0 3] [0 1 0 0 4] [0 0 1 0 5] [0 0 0 1 6] L = companion_matrix(poly, format='left'); L [6 1 0 0 0] [5 0 1 0 0] [4 0 0 1 0] [3 0 0 0 1] [2 0 0 0 0] B = companion_matrix(poly, format='bottom'); B [0 1 0 0 0] [0 0 1 0 0] [0 0 0 1 0] [0 0 0 0 1] [2 3 4 5 6] T = companion_matrix(poly, format='top'); T [6 5 4 3 2] [1 0 0 0 0] [0 1 0 0 0] [0 0 1 0 0] [0 0 0 1 0] perm = Permutation([5, 4, 3, 2, 1]) P = perm.to_matrix() L == P*R*P B == R.transpose() T == P*R.transpose()*P
群
阿贝尔群
定义：群运算满足交换律的群。
GF群
一般有两种，一个是加法群，一个是乘法群。对于G F ( p ) GF(p) G F ( p ) p p p
GL群
定义：在一个域 F F F n × n n \times n n × n
G L ( n , F ) = { A ∈ M n ( F ) ∣ det ( A ) ≠ 0 } GL(n,F) = \{ A \in M_n(F) \;\mid\; \det(A) \neq 0 \}
G L ( n , F ) = { A ∈ M n ( F ) ∣ det ( A ) = 0 }
显然GL群是非阿贝尔群。
阶
群的阶
一个群G G G ∣ G ∣ \lvert G \rvert ∣ G ∣ n n n p p p p − 1 p-1 p − 1 ∏ i = 0 n − 1 ( q n − q i ) \prod_{i=0}^{n-1} \bigl(q^n - q^i\bigr) ∏ i = 0 n − 1 ( q n − q i )
元素的阶
对于设群G G G a a a G G G a a a a k = e a^k=e a k = e k k k e e e a × k = e a \times k=e a × k = e
1 2 k=a.multiplicative_order() #乘法群阶 k=a.additive_order() #加法群阶
生成元
生成元是满足元素阶和群阶相同的元素
1 2 g = G.gens() g0 = G.gen()
gens()可以返回群G G G
1 g1 = G.gens()[1] #等价于g1 = gen(1)
特别注意的是阿贝尔群的生成元唯一会返回符号f f f
ECC
在有限域G F ( p ) GF(p) G F ( p ) y 2 = x 3 + a x + b y^2 = x^3 + ax + b y 2 = x 3 + a x + b
1 E = EllipticCurve(GF(p), [a, b])
曲线群的阶(也就是点的个数)
点运算
1 2 3 4 5 6 7 8 P = E(p_x,p_y) #点定义 Q = k*p #点乘法 R = P+Q #点加法 p = p.order() #点的阶 C = E.lift_x(c_x) #同理E.lift_y(c_y) #这里的lift_x()函数默认返回负点，可以C=E.lift_x(c_x,all=True)这样会返回两个点用索引即可。 C0 = E.lift_x(c_x,all=True)[0] C1 = E.lift_x(c_x,all=True)[1]
曲线群的生成元
离散对数问题(P = p ⋅ G P=p \cdot G P = p ⋅ G
1 p = P.log(G) #或者p = discrete_log(P, G, operation="+")
妙妙工具
sage.matrix.berlekamp_massey.berlekamp_massey() { a r } \{a_r\} { a r } g g g g g g { a r } \{a_r\} { a r } a j + k + b j − 1 a j − 1 + k + ⋯ + b 0 a k = 0 ( 对所有 k ≥ 0 ) a_{j+k} + b_{j-1} a_{j-1+k} + \cdots + b_0 a_k = 0 \quad (\text{对所有 } k \geq 0) a j + k + b j − 1 a j − 1 + k + ⋯ + b 0 a k = 0 ( 对所有 k ≥ 0 ) g g g x j + ∑ i = 0 j − 1 b i x i . x^j + \sum_{i=0}^{j-1} b_i x^i. x j + ∑ i = 0 j − 1 b i x i .
1 2 3 F=GF(2) sage.matrix.berlekamp_massey.berlekamp_massey([F(1),F(2),F(1),F(2),F(1),F(2)]) #x^2+1
这个函数和前面线性代数部分提到的companion_matrix(poly,format) 函数配合就可以很方便求解lfsr问题(题目来源cryptohack–“L-WIN”)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 with open("lwin_output.txt") as f: inp = f.read().strip() F = GF(2) # convert all the 1's and 0's to elements of GF(2) l = [F(int(x)) for x in inp] # run the Berlekamp-Massey algorithm. # this function returns the characteristic polynomial for the LFSR. g = sage.matrix.berlekamp_massey.berlekamp_massey(l) # the companion matrix of the characteristic polynomial can be used to advance # the LFSR: multiplying a vector of previous outputs by the matrix will give a # vector whose last component is the next output. M = companion_matrix(g, 'bottom') v0 = vector(l[:384]) # since M is a matrix, we can invert it to run the LFSR in reverse: M^-768 is # equivalent to running the LFSR backwards 768 iterations. flag = M^-768 * v0 # and now just convert the 1's and 0's to ASCII from Crypto.Util.number import long_to_bytes print(long_to_bytes(int(''.join(str(x) for x in flag),2)))
对于左移型lfsrM M M M M M M M M
