From 5a41e71c95fe879f9fb93aa0472a8f1b3fbd028c Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Wed, 26 Feb 2025 17:49:50 +0100 Subject: Added talk and blog post --- src/talks/ecm/images/beer.jpg | Bin 0 -> 508889 bytes src/talks/ecm/images/clock.png | Bin 0 -> 14805 bytes src/talks/ecm/images/clock2.png | Bin 0 -> 30188 bytes src/talks/ecm/images/demo.jpg | Bin 0 -> 24404 bytes src/talks/ecm/images/ec1.png | Bin 0 -> 17744 bytes src/talks/ecm/images/ec2.png | Bin 0 -> 18917 bytes src/talks/ecm/images/ec3.png | Bin 0 -> 14559 bytes src/talks/ecm/images/euclid.png | Bin 0 -> 1054492 bytes src/talks/ecm/images/factorization.webp | Bin 0 -> 14496 bytes src/talks/ecm/images/number-line.png | Bin 0 -> 36204 bytes src/talks/ecm/images/numbers.jpg | Bin 0 -> 164839 bytes src/talks/ecm/images/questions.png | Bin 0 -> 125274 bytes src/talks/ecm/images/sum-1a.png | Bin 0 -> 18339 bytes src/talks/ecm/images/sum-1b.png | Bin 0 -> 19456 bytes src/talks/ecm/images/sum-1c.png | Bin 0 -> 20134 bytes src/talks/ecm/images/sum-2a.png | Bin 0 -> 18120 bytes src/talks/ecm/images/sum-2b.png | Bin 0 -> 24334 bytes src/talks/ecm/images/sum-2c.png | Bin 0 -> 25172 bytes src/talks/ecm/images/sum-3a.png | Bin 0 -> 17859 bytes src/talks/ecm/images/sum-3b.png | Bin 0 -> 24262 bytes src/talks/ecm/images/sum-3c.png | Bin 0 -> 25047 bytes src/talks/ecm/images/sum-4a.png | Bin 0 -> 17644 bytes src/talks/ecm/images/sum-4b.png | Bin 0 -> 21832 bytes src/talks/ecm/images/sum-4c.png | Bin 0 -> 22574 bytes src/talks/ecm/index.html.raw | 622 ++++++++++++++++++++++++++++++++ src/talks/talks.md | 4 + 26 files changed, 626 insertions(+) create mode 100644 src/talks/ecm/images/beer.jpg create mode 100644 src/talks/ecm/images/clock.png create mode 100644 src/talks/ecm/images/clock2.png create mode 100644 src/talks/ecm/images/demo.jpg create mode 100644 src/talks/ecm/images/ec1.png create mode 100644 src/talks/ecm/images/ec2.png create mode 100644 src/talks/ecm/images/ec3.png create mode 100644 src/talks/ecm/images/euclid.png create mode 100644 src/talks/ecm/images/factorization.webp create mode 100644 src/talks/ecm/images/number-line.png create mode 100644 src/talks/ecm/images/numbers.jpg create mode 100644 src/talks/ecm/images/questions.png create mode 100644 src/talks/ecm/images/sum-1a.png create mode 100644 src/talks/ecm/images/sum-1b.png create mode 100644 src/talks/ecm/images/sum-1c.png create mode 100644 src/talks/ecm/images/sum-2a.png create mode 100644 src/talks/ecm/images/sum-2b.png create mode 100644 src/talks/ecm/images/sum-2c.png create mode 100644 src/talks/ecm/images/sum-3a.png create mode 100644 src/talks/ecm/images/sum-3b.png create mode 100644 src/talks/ecm/images/sum-3c.png create mode 100644 src/talks/ecm/images/sum-4a.png create mode 100644 src/talks/ecm/images/sum-4b.png create mode 100644 src/talks/ecm/images/sum-4c.png create mode 100644 src/talks/ecm/index.html.raw (limited to 'src/talks') diff --git a/src/talks/ecm/images/beer.jpg b/src/talks/ecm/images/beer.jpg new file mode 100644 index 0000000..5a67225 Binary files /dev/null and b/src/talks/ecm/images/beer.jpg differ diff --git a/src/talks/ecm/images/clock.png b/src/talks/ecm/images/clock.png new file mode 100644 index 0000000..631ee42 Binary files /dev/null and b/src/talks/ecm/images/clock.png differ diff --git a/src/talks/ecm/images/clock2.png b/src/talks/ecm/images/clock2.png new file mode 100644 index 0000000..bc2706b Binary files /dev/null and b/src/talks/ecm/images/clock2.png differ diff --git a/src/talks/ecm/images/demo.jpg b/src/talks/ecm/images/demo.jpg new file mode 100644 index 0000000..eaf2cd9 Binary files /dev/null and b/src/talks/ecm/images/demo.jpg differ diff --git a/src/talks/ecm/images/ec1.png b/src/talks/ecm/images/ec1.png new file mode 100644 index 0000000..1c31a1e Binary files /dev/null and b/src/talks/ecm/images/ec1.png differ diff --git a/src/talks/ecm/images/ec2.png b/src/talks/ecm/images/ec2.png new file mode 100644 index 0000000..c44f3c0 Binary files /dev/null and b/src/talks/ecm/images/ec2.png differ diff --git a/src/talks/ecm/images/ec3.png b/src/talks/ecm/images/ec3.png new file mode 100644 index 0000000..6db47e4 Binary files /dev/null and b/src/talks/ecm/images/ec3.png differ diff --git a/src/talks/ecm/images/euclid.png b/src/talks/ecm/images/euclid.png new file mode 100644 index 0000000..ccfec81 Binary files /dev/null and b/src/talks/ecm/images/euclid.png differ diff --git a/src/talks/ecm/images/factorization.webp b/src/talks/ecm/images/factorization.webp new file mode 100644 index 0000000..892a53d Binary files /dev/null and b/src/talks/ecm/images/factorization.webp differ diff --git a/src/talks/ecm/images/number-line.png b/src/talks/ecm/images/number-line.png new file mode 100644 index 0000000..27531cb Binary files /dev/null and b/src/talks/ecm/images/number-line.png differ diff --git a/src/talks/ecm/images/numbers.jpg b/src/talks/ecm/images/numbers.jpg new file mode 100644 index 0000000..9b0f835 Binary files /dev/null and b/src/talks/ecm/images/numbers.jpg differ diff --git a/src/talks/ecm/images/questions.png b/src/talks/ecm/images/questions.png new file mode 100644 index 0000000..eee3df2 Binary files /dev/null and b/src/talks/ecm/images/questions.png differ diff --git a/src/talks/ecm/images/sum-1a.png b/src/talks/ecm/images/sum-1a.png new file mode 100644 index 0000000..61fb531 Binary files /dev/null and b/src/talks/ecm/images/sum-1a.png differ diff --git a/src/talks/ecm/images/sum-1b.png b/src/talks/ecm/images/sum-1b.png new file mode 100644 index 0000000..f3a7972 Binary files /dev/null and b/src/talks/ecm/images/sum-1b.png differ diff --git a/src/talks/ecm/images/sum-1c.png b/src/talks/ecm/images/sum-1c.png new file mode 100644 index 0000000..c534cce Binary files /dev/null and b/src/talks/ecm/images/sum-1c.png differ diff --git a/src/talks/ecm/images/sum-2a.png b/src/talks/ecm/images/sum-2a.png new file mode 100644 index 0000000..d925e7a Binary files /dev/null and b/src/talks/ecm/images/sum-2a.png differ diff --git a/src/talks/ecm/images/sum-2b.png b/src/talks/ecm/images/sum-2b.png new file mode 100644 index 0000000..dbd6f03 Binary files /dev/null and b/src/talks/ecm/images/sum-2b.png differ diff --git a/src/talks/ecm/images/sum-2c.png b/src/talks/ecm/images/sum-2c.png new file mode 100644 index 0000000..4637bb8 Binary files /dev/null and b/src/talks/ecm/images/sum-2c.png differ diff --git a/src/talks/ecm/images/sum-3a.png b/src/talks/ecm/images/sum-3a.png new file mode 100644 index 0000000..f85d7ff Binary files /dev/null and b/src/talks/ecm/images/sum-3a.png differ diff --git a/src/talks/ecm/images/sum-3b.png b/src/talks/ecm/images/sum-3b.png new file mode 100644 index 0000000..537c5b2 Binary files /dev/null and b/src/talks/ecm/images/sum-3b.png differ diff --git a/src/talks/ecm/images/sum-3c.png b/src/talks/ecm/images/sum-3c.png new file mode 100644 index 0000000..ca093dc Binary files /dev/null and b/src/talks/ecm/images/sum-3c.png differ diff --git a/src/talks/ecm/images/sum-4a.png b/src/talks/ecm/images/sum-4a.png new file mode 100644 index 0000000..82eee13 Binary files /dev/null and b/src/talks/ecm/images/sum-4a.png differ diff --git a/src/talks/ecm/images/sum-4b.png b/src/talks/ecm/images/sum-4b.png new file mode 100644 index 0000000..827c0c2 Binary files /dev/null and b/src/talks/ecm/images/sum-4b.png differ diff --git a/src/talks/ecm/images/sum-4c.png b/src/talks/ecm/images/sum-4c.png new file mode 100644 index 0000000..bf323fd Binary files /dev/null and b/src/talks/ecm/images/sum-4c.png differ diff --git a/src/talks/ecm/index.html.raw b/src/talks/ecm/index.html.raw new file mode 100644 index 0000000..cf168b7 --- /dev/null +++ b/src/talks/ecm/index.html.raw @@ -0,0 +1,622 @@ + + + + Elliptic Curves and the ECM algorithm + + + + + + + + + + + + + + + + +
+ +

+ +

Elliptic curves and the ECM algorithm

+

Sebastiano Tronto

+

ALTEN Scientific Software Evening

+ +
+ +
+

+

Part I: Numbers

+

+
+ +
+

The integers

+ +The number line + + +
+ +
+

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 number clock + +
+ +
+ +
+

The integers modulo N - Division

+ +

What about division?

+ + +
+ +
+

Integers modulo N - Division

+ +
+ +
+

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
    • +
+The number line +
+
+ +
+

+

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\] +

+ +
+
\(y^2=x^3-x+1\)
\((A=-1, B=1\))
+An elliptic curve +
+ +
+
+ +
+

Elliptic curves

+ +
+ +
+
\(y^2=x^3+13x-34\)
\((A=13, B=-34\))
+An elliptic curve +
+ +
+
\(y^2=x^3-x\)
\((A=-1, B=0\))
+An elliptic curve +
+ +
+
+ +
+

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 curve sum + +
+
+ +
+

Elliptic curves - sum operation - example 1

+Elliptic curve sum +
+
+

Elliptic curves - sum operation - example 1

+Elliptic curve sum +
+
+

Elliptic curves - sum operation - example 1

+Elliptic curve sum +
+ +
+

Elliptic curves - sum operation - example 2

+Elliptic curve sum +
+
+

Elliptic curves - sum operation - example 2

+Elliptic curve sum +
+
+

Elliptic curves - sum operation - example 2

+Elliptic curve sum +
+ +
+

Elliptic curves - sum operation - example 3

+Elliptic curve sum +
+
+

Elliptic curves - sum operation - example 3

+Elliptic curve sum +
+
+

Elliptic curves - sum operation - example 3

+Elliptic curve sum +
+ +
+

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
    • +
+The number line +
+
+ +
+

+

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\):

+

    +
  1. Take a random Elliptic Curve \(E\) +and a random point \(P\) of \(E\)
    2. +
  2. Take a suitable number \(m\)
    3. +
  3. Try to compute \(m\cdot P = P+P+\cdots+P\quad\) (\(m\) times) +with coordinates modulo \(n\)
    4. +
  4. If you attempt an impossible division by some number \(d\), +return \(\operatorname{GCD}(n,d)\)
    5. +
  5. Go back to 1.
    6. +
+
+
+ +
+

Find Factor - Elliptic Curve Method - Example

+
+ +
+

+

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.

+
+
+ +
+

+

More questions?

+

+
+ +
+

+

Drinks!

+

+
+ + + + + diff --git a/src/talks/talks.md b/src/talks/talks.md index b7cea5b..595f49a 100644 --- a/src/talks/talks.md +++ b/src/talks/talks.md @@ -12,6 +12,10 @@ ## Math +* *Elliptic Curves and the ECM algorithm*. + ALTEN Scientific Software Evening, February 2025. + [Slides: [html, 2.4Mb](./ecm)] + * *Kummer theory for elliptic curves*. Short talk for Tarrach Prize 2023, March 2023. [Slides: [pdf, 288Kb](kummer-tarrach.pdf)] -- cgit v1.3