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(\exp\left(\sqrt{2\log p \log\log p}\right)\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.

  1. Choose a random $A, a, b \pmod{n}$
  2. Set P = $(a, b)$ and $B \equiv_n b^2 - a^3 - A\cdot a$, let $E: y^2 = x^3 + Ax + B$.
  3. Let $j=2$, compute $Q \equiv_n jP$ and set $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$.