Singular Curves

奇异椭圆定义

从代数上来说，如果椭圆曲线方程 $y^2=x^3+Ax+B$ 的判别式 $\Delta=4A^3+27B^2=0$ ，那么该椭圆就是奇异的。从几何图像上来看，就是椭圆曲线关于 $x$ 轴的交点有重根，这是因为 $((r_1-r_2)(r_1-r_3)(r_2-r_3))^2=-\Delta$ ,其中 $r_1,r_2,r_3$ 为交点横坐标。

两种奇异椭圆曲线

接下来研究两种简单的奇异椭圆，本文主要就是对它们与其他域的同态进行讨论。

1.y^2=x^3

针对这种椭圆曲线，是构造同态：

$E(K)\rightarrow K , \quad (x, y) \mapsto \frac{x}{y}$

两边都为域$K$中的加群。

可以证明，如果 $(x_1,y_1)+(x_2,y_2)=(x_3,y_3)$ ，就有 $t_1+t_2=t_3$ ，$t_i=x_i/y_i$ 。

2.y^2=x^2(x+a)

这种情况的同态稍微有点复杂。记 $\alpha ^2=a$ ，考虑同态：

$\psi :(x,y) \mapsto \frac{y+\alpha x}{y-\alpha x}$

1. 如果 $\alpha \in K$，那么 $\psi$ 给出了加法群到乘法群$F_p$的同态。

2. 如果 $\alpha \notin K$，那么就有 $E(K) \simeq \{u+\alpha v|u,v\in K,u^2-av^2=1 \}$ 。同样是加法群到乘法群的同态。后者与$Q[\sqrt2]$很像。

题目

首先题目给出了一种运算，显然和椭圆曲线有关：

p = 193387944202565886198256260591909756041

i = lambda x: pow(x, p-2, p)

def add(A, B):
    (u, v), (w, x) = A, B
    assert u != w or v == x
    if u == w: 
        m = (3*u*w + 4*u + 1) * i(v+x)
        
    else: 
        m = (x-v) * i(w-u)
    y = m*m - u - w - 2
    z = m*(u-y) - v
    return y % p, z % p

def mul(t, A, B=0):
    if not t: return B
    return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)

注意到这里计算斜率的方式有一点不一样，在计算 $2P$ 时，一般情况下，由 $y^2=x^3+Ax+B$ 可知：$\frac{dy}{dx}=\frac{3x^2+A}{2y}$ ，而这里却是 $\frac{dy}{dx}=\frac{3x^2+4x+1}{2y}$ 。分离变量积分可得 $y^2=x^3+2x^2+x+C$ 。

然后题目用了一个随机数$x$，和坐标 $P(4,10)$ ，给出了 $mul(x, P)$ 的结果$Q$，要我们求x。

这里可以将 $P$ 代入我们得到的方程，可得$C=0$。为了能使方程 $y^2=x^3+2x^2+x$变为 $y^2=x^2(x+a)$ 的形式，就让 $x=x-1$ 。同时P,Q也要做相应变换。

最后利用上述同态的方法，先求出 $\alpha$ ，然后将 $P,Q$ 分别映射为$u=\frac{y_P+\alpha x_P}{y_P-\alpha x_P}$ 和 $v=\frac{y_Q+\alpha x_Q}{y_Q-\alpha x_Q}$ ,使用离散对数求解即可。

值得注意的是，离散对数的解不只一个，需要计算 $u$ 的阶随后逐一检验。

p = 193387944202565886198256260591909756041
P.<x> = GF(p)[]
f = x^3 + 2*x^2 + x
P = (4, 10)
Q = (65639504587209705872811542111125696405, 125330437930804525313353306745824609665)

# f_ = f.subs(x=x-1)
# print(f_.factor()) # 193387944202565886198256260591909756040

P_ = (P[0] +1, P[1])
Q_ = (Q[0] +1, Q[1])

t = GF(p)(193387944202565886198256260591909756040).square_root()
u = (P_[1] + t*P_[0])/(P_[1] - t*P_[0]) % p
v = (Q_[1] + t*Q_[0])/(Q_[1] - t*Q_[0]) % p

print(v.log(u))
d = multiplicative_order(u)