Elliptic Curve - Divide by 2

问题引入

对于一条椭圆曲线 $E:y^2=x^3+ax+b$ ，如果我们知道其中的一个点 $Q=2P$ 要如何求 $P$ 呢？

如果 $E$ 的阶是奇数，那么通过求2的逆元可以很快算出 $P$，但阶是偶数情况要如何处理？

解决方法

通过查阅相关资料 finite field - Elliptic Curve - Divide by 2 - Cryptography Stack Exchange 、 1605.09279.pdf (arxiv.org)

有一套计算公式可以快速算出。

代码：

from Crypto.Util.number import *
q = 37474009785980474658135106783131904659818035950984079581009709986840194575036321428945132957079423328996508289872067
a = 138681122158674534796479818810828100269024674330030901179877002756402543027343312824423418859769980312713625658733
b = 4989541340743108588577899263469059346332852532421276369038720203527706762720292559751463880310075002363945271507040
F = GF(q)
E = EllipticCurve(F,[a, b])
P = E.gens()[0]
print(P.order())  # 6245668297663412443022517797188650776636339325164013263502088991281378002278537965565236170652485316181515543825266
Q = 2 * P


R.<x> = PolynomialRing(GF(q))
x = R.gen()
px = x^3 + a * x + b
roots = px.roots()
r1 = roots[0][0]
r2 = roots[1][0]
r3 = roots[2][0]

Qxq = F(Q[0])
Qyq = F(Q[1])
s1 = -(Qxq - r1).sqrt()  # two solution, change positivity for the other solution.
s2 = (Qxq - r2).sqrt()  # two solution

s3 = -Qyq*(s1*s2)^-1

u = s1+s2+s3
v = s1*s2 + s2*s3 + s1*s3

Mq = E(Qxq+v, -Qyq-u*v)
Mq == P  # True