Elliptic curves and the ECM algorithm

Sebastiano Tronto

ALTEN Scientific Software Evening

The integers

Operations: sum \(+\), difference \(-\) and multiplication \(\times\)
Various properties: associativity, commutativity, etc...
What about division (without remainder)?
If \(\frac ab\) 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\pmod{12}\] \[7-11\equiv-4\equiv 8\pmod{12}\] \[3\times 4\equiv 12\equiv 0\pmod{12}\]

The integers modulo N - Division

What about division?

Sometimes it works \[ \frac 37\equiv 9 \pmod{12} \qquad \text{because} \qquad 9\times 7 \equiv 63 \equiv 3 \pmod{12} \]
Sometimes it does not \[ \frac 32\equiv \; ? \pmod{4} \qquad {\color{red}\text{Impossible!}} \]

Integers modulo N - Division

Sometimes it's... weird? \[ \frac 62 \equiv \; ? \pmod{8} \quad \begin{array}{l} \rightarrow {\color{red}3} \times 2 \equiv 6\pmod{8}\\ \rightarrow {\color{red}7} \times 2 \equiv 14 \equiv 6 \pmod{8} \end{array} \]

Integers modulo N - Division

Can divide by \(a\) when \[\operatorname{GCD}(a, N)=1\]
With the extended GCD algorithm find \(x\) and \(y\) such that \[ ax+Ny=1 \]
This means \(\frac{1}{a}\equiv x\pmod{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+Ax+B \] Where \(A\) and \(B\) are numbers with \[4A^3+27B^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\qquad 0+P=0\qquad 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+Ax+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+\cdots+P\quad\) (\(m\) times) with coordinates modulo \(n\)
If you attempt an impossible division by some number \(d\), return \(\operatorname{GCD}(n,d)\)
Go back to 1.

Find Factor - Elliptic Curve Method - Example

Take \(n = 91\)
Take \(E: y^2 = x^3 + 51x -371\) and \(P = (11, 39)\) and \(M = 2\)
Try to compute \(M\cdot P=P+P\pmod n\): \[ k = \frac{3x_p^2+51}{2y_p} \pmod n\] Is \(2y_p=78\) invertible modulo \(91\)? \[ \operatorname{GCD}(78, 91) = 13 \neq 1 \quad \implies \quad \text{NO!} \]
Found factor: \(13\)

Demo time!

git.tronto.net/ecm

Elliptic Curve Method - Questions

Q: Aren't we just computing the \(\operatorname{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.