Factorization: Lenstra Elliptic-Curve Factorization

17 Dec 2021

Notes Cryptography Factorization: Lenstra Elliptic-Curve Factorization

§ Motivation

We can use some properties of groups formed over elliptic curves to use in a factorization problem.

§ Lenstra's Factorization

The asymptotic complexity of Lenstra's method is $\mathcal{O}\left(e^{\sqrt{2\log p \log\log p}}\right)$ . If $n = pq$ where $p, q$ prime, and $p \ll q$ Lenstra's becomes faster than the quadratic sieve.

Lenstra's Elliptic Curve Factorization Algorithm

Suppose we know that $n$ is a composite number.

Choose a random $A, a, b \pmod{n}$
Set P = $(a, b)$ and $B \equiv_n b^2 - a^3 - A\cdot a$ , let $E: y^2 = x^3 + Ax + B$ .
Let $j=2$ $j = 2$ , compute $Q \equiv_n jP$ $Q \equiv_{n} j P$ and set $P = Q$ $P = Q$
- If this step fails, then there is a non-invertible element modulo $n$ . Let $d$ be the GCD between $n$ and this non-invertible element, if $1 \lt d \lt n$ , then $d$ is a non-trivial divisor of $n$ . Stop and return $d$ .
- If $d = n$ , restart algorithm with different random parameters.
- Otherwise, increment $j$ and repeat.

Lenstra Factorization

Suppose we want to factor $n = 6887$ with $P = (1512, 3166)$ and $A = 14$ and $B \equiv 19$ .

Then, our elliptic curve is $E : y^2 = x^3 + 14x + 19$ . We can repeat step $3$ from $j = 2$ to $j = 6$ , thusly computing $6!\cdot P$ without issue. However, on $j = 7$ we encounter a non-invertible element

7Q = (Q + 2Q) + 4Q = (984, 589) + (203, 2038) \pmod{6887}.

To compute this point addition, we must compute the multiplicative inverse of $(203 - 984)$ modulo $6887$ , which does not exist. Therefore, $d = \gcd(-781, 6887) = 71$ is a non-trivial factor of $6887$ .