Schoof_Algorithm.md

Schoof's Algorithm - Finding the order of an elliptic curve

Definition:

$\mathbb{F}_p$	Prime field with $p > 3$
$\mathop{\text{char}}(\mathbb{F}_p) = p$	Characteristic of the field
$E(\mathbb{F}_p): y^2 = x^3 + ax + b$	Elliptic curve given by a short Weierstrass equation over the field
$＃E(\mathbb{F}_p)$	Order of the elliptic curve
$\phi: (x, y) \mapsto (x^p, y^p)$	Frobenius map

Let:

$t = p + 1 - ＃E(\mathbb{F}_p)$

This can be transformed to:

$＃E(\mathbb{F}_p) = p + 1 - t$

Hasse's bound states:

$-2\sqrt{p} \leq t \leq 2\sqrt{p}$

We already know $p$ but we still need to calculate $t$. Turns out $t$ can be found using the Frobenius Endomorphism, where $t$ is the Trace of the Frobenius Endomorphism.

Finding the Trace of the Frobenius Endomorphism

1. Choose a set $S = {l_1, l_2, \dots, l_k}$ of the smallest distinct primes $l \neq p$, such that the product $L$ is larger than $4\sqrt{p}$
2. Compute $t \bmod{l}$ for each prime $l \in S$:
   • For $l = 2$:
     • if $\deg(\gcd(x^3 + ax + b, (x^p - x) \bmod (x^3 + ax + b))) = 0$ (i.e. if $y^2$ has no roots):
       • $t \equiv 1 \pmod{2}$
     • else:
       • $t \equiv 0 \pmod{2}$
   • For each other $l$:
     • Compute the $l$-division polynomial $\psi_l(x)$ of $E(\mathbb{F}_p)$
     • Following computations happen in the polynomial quotient ring $\mathbb{F}_p[x,y]/(\psi_l(x), y^2 - x^3 - ax - b)$
     • Define the symbolic point $P = (x, y)$ on $E(\mathbb{F}_p)$
     • Define the Frobenius endomorphism $\phi(P) = (x^p, y^p)$
     • Define the square of the Frobenius endomorphism $\phi^2(P) = (x^{p^2}, y^{p^2})$
     • For each $\tau \in {0, \dots, l-1}$:
       • If $\phi^2(P) + [p \bmod l]P = [\tau]\phi(P)$
         • $t \equiv \tau \pmod{l}$
         • Break from for loop
3. Recover $t$:
   • Use the Chinese Remainder Theorem on the computed congruences ($t \bmod{l}$)
   • This gives a unique solution $t \bmod L$
   • Find the specific value of $t$ in the interval $[-2\sqrt{p}, 2\sqrt{p}]$ that matches this solution.