+ +

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 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

+ +

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(n) + 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.