Elliptic curves and the ECM algorithm

Sebastiano Tronto

ALTEN Scientific Software Evening

Part I: Numbers

The integers

Operations: sum $+$ , difference $-$ and multiplication $\times$
Various properties: associativity, commutativity, etc...
What about division (without remainder)?
If $\frac{a}{b}$ is an integer we say that $a$ divides $b$ (in code: a % b == 0)

The integers modulo N

Two numbers are the same if they give the same remainder when divided by N
Think of int, but with % N after every operation
Examples with $N = 12$ : $9 + 5 \equiv 14 \equiv 2 (\mod 12)$ $7 - 11 \equiv - 4 \equiv 8 (\mod 12)$ $3 \times 4 \equiv 12 \equiv 0 (\mod 12)$

The integers modulo N - Division

What about division?

Sometimes it works $\frac{3}{7} \equiv 9 (\mod 12) because 9 \times 7 \equiv 63 \equiv 3 (\mod 12)$
Sometimes it does not $\frac{3}{2} \equiv ? (\mod 4) Impossible!$

Integers modulo N - Division

Sometimes it's... weird? $\frac{6}{2} \equiv ? (\mod 8) \begin{array}{l} \to 3 \times 2 \equiv 6 (\mod 8) \\ \to 7 \times 2 \equiv 14 \equiv 6 (\mod 8) \end{array}$

Integers modulo N - Division

Can divide by $a$ when $GCD (a, N) = 1$
With the extended GCD algorithm find $x$ and $y$ such that $a x + N y = 1$
This means $\frac{1}{a} \equiv x (\mod N)$


def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - y*(a // b)

Division always works if $N$ is a prime number!

Modular arithmetic - recap

Integers modulo $N$ are (almost) like numbers
Normal operations like $+$ , $-$ and $\times$ work
Division sometimes works, sometimes not
Division always works if $N$ is prime

Part II: Elliptic Curves

Elliptic curves

An elliptic curve is a curve with equation $y^{2} = x^{3} + A x + B$ Where $A$ and $B$ are numbers with $4 A^{3} + 27 B^{2} \neq 0$

Elliptic curves

There is a "sum" operation for points of a curve (NOT the sum of coordinates)
To make things work out nicely, we pretend the curve has a point at infinity that acts as $0$ : $P + 0 = 0 0 + P = 0 P - P = 0$

Elliptic curves - sum operation - example 1

Elliptic curves - sum operation - example 2

Elliptic curves - sum operation - example 3

Elliptic curves - sum operation - code


# Computes p+q on the elliptic curve y^2 = x^3 + Ax + B
def ec_sum(p: Point, q: Point, A: double) -> Point:
    if p.is_zero:
        return q
    if q.is_zero:
        return p
    if p.x == q.x and p.y == -q.y:
        return Point(is_zero = True)

    if p.x != q.x:
        k = (p.y - q.y) / (p.x - q.x)
    else:
        k = (3 * p.x**2 + A) / (p.y + q.y)

    new_x = k**2 - p.x - q.x
    new_y = k * (p.x - new_x) - p.y
    return Point(x = new_x, y = new_y)


@dataclass
class Point:
    x: int = 0
    y: int = 0
    is_zero: bool = False

Elliptic curves - recap

Curves of equation $y^{2} = x^{3} + A x + B$
Can "sum" points of the same curve
Nice properties: associativity, commutativity...
The sum operation can be easily implemented

Part III: The Elliptic Curve Factorization Method

Integer factorization

Every positive integer can be written as the product of prime numbers

Example: $69420 = 2 \times 2 \times 3 \times 5 \times 13 \times 89$
Computationally hard
Important for cryptography!

Integer factorization - high-level procedure


# Returns the list of prime factors of n
def factorize(n: int) -> list:
    if n == 1:
        return []

    if is_prime(n):
        return [n]

    f = find_factor(n)

    return factorize(f) + factorize(n//f)

is_prime(n) can be implemented efficiently (Miller-Rabin, AKS or ECPP)

Naive implementation of find_factor(n):


def find_factor(n: int) -> int:
    for i in range(2,floor(sqrt(n))+1):
        if n % i == 0:
            return i

Find Factor - Elliptic Curve Method

To find a factor of $n$ :

Take a random elliptic curve $E$ and a random point $P$ of $E$
Take a suitable number $m$
Try to compute $m \cdot P = P + P + \dots + P$ ( $m$ times) with coordinates modulo $n$
If you attempt an impossible division by some number $d$ , return $GCD (n, d)$
Go back to 1.

Find Factor - Elliptic Curve Method - Example

Take $n = 91$
Take $E : y^{2} = x^{3} + 51 x - 371$ and $P = (11, 39)$ and $M = 2$
Try to compute $M \cdot P = P + P (\mod n)$ : $k = \frac{3 x_{p}^{2} + 51}{2 y_{p}} (\mod n)$ Is $2 y_{p} = 78$ invertible modulo $91$ ? $GCD (78, 91) = 13 \neq 1 ⟹ NO!$
Found factor: $13$

Demo time!

git.tronto.net/ecm

Elliptic Curve Method - Questions

Q: Aren't we just computing the $GCD$ with random numbers?

A: Yes, but elliptic curve operations produce "good candidates" for these random numbers.

Elliptic Curve Method - Questions

Q: Can we do the same without elliptic curves?

A: Yes, with Pollard's $p - 1$ Algorithm, but ECM is faster.

Elliptic Curve Method - Questions

Q: Are there objects that are more complicated than elliptic curves and can make the method even faster?

A: Yes, there are higher-dimensional Abelian Varieties and other Algebraic Groups, but they are much harder (if not impossible) to implement efficiently.