Elliptic Curves¶
https://doc.sagemath.org/html/en/tutorial/tour_advanced.html#elliptic-curves
get Elliptic Curve¶
The command EllipticCurve for creating an elliptic curve has many forms:
- EllipticCurve([a1, a2, a3, a4, a6]): Returns the elliptic curve: $y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$
- EllipticCurve(R, [a4, a6]): Same as above, but a1=a2=a3=0 => $y^2=x^3+a_4x+a_6$ , which is known as Weierstrass form on the ring R.
In [3]:
Copied!
p, a, b = 97, 2, 3
E = EllipticCurve(GF(p), [a, b])
E
p, a, b = 97, 2, 3
E = EllipticCurve(GF(p), [a, b])
E
Out[3]:
Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Finite Field of size 97
add node on curve¶
In [ ]:
Copied!
(3, 6)# (3 : 6 : 1) # n 齐次坐标表示法 https://devv.ai/search?threadId=e30z23yx28e8
(3, 6)# (3 : 6 : 1) # n 齐次坐标表示法 https://devv.ai/search?threadId=e30z23yx28e8
Out[ ]:
((3 : 6 : 1), (3, 6))
In [ ]:
Copied!
# 也可以依据横坐标取一个点（y为正）
E.lift_x(3)
# 也可以依据横坐标取一个点（y 为正）
E.lift_x(3)
Out[ ]:
(3 : 6 : 1)
In [4]:
Copied!
for i in range(1, 10):
print(i, i * P)
for i in range(1, 10):
print(i, i * P)
1 (3 : 6 : 1) 2 (80 : 10 : 1) 3 (80 : 87 : 1) 4 (3 : 91 : 1) 5 (0 : 1 : 0) 6 (3 : 6 : 1) 7 (80 : 10 : 1) 8 (80 : 87 : 1) 9 (3 : 91 : 1)
In [ ]:
Copied!
E.random_point(), E.gens() # 生成一组生成元
E.random_point(), E.gens() # 生成一组生成元
Out[ ]:
((56 : 8 : 1), ((86 : 28 : 1), (10 : 76 : 1)))
other¶
E.order()获得 E 椭圆曲线阶Q.log(P)获得 Q 在 P 下的离散对数，即求解 Q = n*P
In [ ]:
Copied!
def ECC_Pohlig_Hellman(E, P, Q):
print(E.order())
factors = list(factor(E.order()))[:-1]
primes = [i**j for i,j in factors]
dlogs = []
print(primes)
for fac in primes:
t = int(int(P.order()) // int(fac))
dlog = discrete_log(t*Q,t*P,operation="+")
dlogs += [dlog]
print("factor: "+str(fac)+", Discrete Log: "+str(dlog))
return crt(dlogs,primes)
def ECC_Pohlig_Hellman(E, P, Q):
print(E.order())
factors = list(factor(E.order()))[:-1]
primes = [i**j for i,j in factors]
dlogs = []
print(primes)
for fac in primes:
t = int(int(P.order()) // int(fac))
dlog = discrete_log(t*Q,t*P,operation="+")
dlogs += [dlog]
print("factor: "+str(fac)+", Discrete Log: "+str(dlog))
return crt(dlogs,primes)