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 --- .../2025-02-27-elliptic-curves-javascript/ecm.md | 283 ++++++++++ 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 + 27 files changed, 909 insertions(+) create mode 100644 src/blog/2025-02-27-elliptic-curves-javascript/ecm.md 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') diff --git a/src/blog/2025-02-27-elliptic-curves-javascript/ecm.md b/src/blog/2025-02-27-elliptic-curves-javascript/ecm.md new file mode 100644 index 0000000..56b876c --- /dev/null +++ b/src/blog/2025-02-27-elliptic-curves-javascript/ecm.md @@ -0,0 +1,283 @@ +# Elliptic curves and JavaScript + +At my company we regularly have talks and other knowledge events. +After attending many of these events, I decided to give a talk +about [elliptic curves](https://en.wikipedia.org/wiki/Elliptic_curve), +which I worked with during my PhD. + +The intended audience consists of software developers, but their +background is mixed: some have studied Maths in university, but many did +not. Most are not familiar with abstract algebra other than polynomials +and matrices, let alone algebraic geometry. Considering all of this, +I decided to give a presentation about +[Lenstra elliptic curve factorization](https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization), +so I could also show some code and do a practical demo. + +Since I gave a presentation on this topic to a different audience a +couple of years ago, I could have simply adapted the slides and used the +same code. Instead, I took this as an opportunity to experiment with +new tools and languages. This post is a summary of what I have learned +while preparing this talk. + +All the code I talk about in this post, including the source for the +slides, can be found in [this git repository](https://git.tronto.net/ecm). + +## The code + +For the practical part of the talk I had to write some code to demonstrate +the factorization algorithm. It's not much, maybe 200 lines or so, and +I already had a working Python version. It was a rather straightforward +implementation, and it used exceptions to handle the "a factor was found" +part of the algorithm; although this is not amazing coding style, it +was faithful to how the algorithm was originally explained - or to how +I wanted to explain it, anyway. + +It was not bad code, but I wanted to experiment with something new. + +### Adventures in C++ + +Recently I have been learning C++, and I wanted to experiment with some +of its more advanced features. So I decided to rewrite the whole thing. + +I had a clear idea of where I wanted to start: a small +[library for modular arithmetic](https://git.tronto.net/zmodn/file/README.md.html), +with compile-time fixed +[modulus](https://en.wikipedia.org/wiki/Modular_arithmetic) via templates +and heavy use of +[type inference](https://en.wikipedia.org/wiki/Type_inference) +for seamless operations between regular integers and integers modulo N. +This endeavor was quite successful, and it taught me how to use +templates and concepts, which I have talked about in +[my previous blog post](../2025-01-21-taming-cpp-templates). + +When working on the previous part, I made sure that any kind of integer +could be used as a base type for the modular integers, so I could use +some custom big integer types to show off the power of the factorization +algorithm with very large numbers. Unfortunately, I did not take into +account that with my setup I needed a big integer class that supported +*compile-time constants* - for example in the form of `constexpr` +constructors. I could not find any, so I decided to write +[my own big integer class](https://git.tronto.net/zmodn/file/bigint.h.html). +This was less successful: implementing an *efficient* big integer library +was not as straightforward as the modular integers library. I decided +not to care about efficiency for the time being, but that would come +back to bite me very soon. + +Finally, I put these two libraries together and implemented the elliptic +curve factorization algorithm. This was not hard. The only problem was +that it was excruciatingly slow when I used large numbers, undoubtedly +due to my half-assed big integer implementation. I could restrict +myself to using regular 64-bit integers, but then I would have to use +to relatively small numbers, making the demo less interesting. I looked +online for other big integer libraries that I could use and I found +[ctbignum](https://github.com/niekbouman/ctbignum), but I could not make +it work together with my modular arithmetic class. The day of the +presentation was approaching quickly, so I decided to go back to +my original Python implementation instead. + +### Back to Python + +When I looked back at my old Python implementation, I found it nicer +and cleaner than how I remembered it. I did not have to do much +cleanup, it was pretty much ready to go, and much more readable than +the C++ verion for anyone who is not a C++ expert - and probably for C++ +experts too. Moreover, Python's seamless use of large integers was +exactly what I was missing from the C++ version. + +One of the few changes I made to this code was reworking a little bit +the "elliptic curve point" class I used. If anything, this was a good +excuse to learn about +[dataclasses](https://docs.python.org/3/library/dataclasses.html). I also +decided to add +[type hints](https://docs.python.org/3/library/typing.html), which I +have recently found out about. + +And with little work, the old code was ready to go! + +## The slides + +Compared to the code, the slides needed a few more adjustments. +When I gave this talk the first time, it was for an audience of +Math students at the end of their Bachelor program. I could freely +use all that Math jargon that we Mathematicians like, such as +"let K be a +[field](https://en.wikipedia.org/wiki/Field_(mathematics))" +and "E is a +[projective](https://en.wikipedia.org/wiki/Projective_space) curve". +But this time I had to phrase things differently. The content itself +didn't need much change, but I had to use a more approachable language, +at the cost of being a little less rigorous. For example, I could +get rid of all the projective plane business by just saying "let's +pretend that there is a point *at infinity*; trust me, the Math +works out". + +The problem with changing the old slides is that I did not want to touch +[LaTeX](https://nl.wikipedia.org/wiki/LaTeX) +anymore. As a Mathematician I like it because it can do pretty much everything +you need (did you know you can +[draw diagrams programmatically](https://www.youtube.com/watch?v=mWqhB6qOIk0)?), +but as a computer scientist I'd rather not deal with the mess that is a +LaTeX installation. +So what did I decide to use instead? HTML, CSS and a bit of JavaScript! + +### Math formulas with MathJax + +Even without LaTeX, I still needed a way to write Math formulas in my +slides. One way to achieve this is using [MathJax](https://www.mathjax.org), +which allows you to write LaTeX or +[MathML](https://en.wikipedia.org/wiki/MathML) formulas direclty in +your HTML, and have them rendered dynamically. A minimal example +looks like this: + +``` + + + + + + +

Hello! \[ e^{\pi i} + 1 = 0 \]

+ +``` + +In the example above I am including the MathJax library directly from a +URL. This means every time you load that page, a request is sent from +your browser to the MathJax server to get the code for rendering the +formulas. Among other things, this implies that my slides are going +to be dependent on this external website, and that they won't work +offline. The horror! + +In theory I could install MathJax locally (or on my server) and get rid +of this dependency, and maybe at some point I'll do it. But for now +it is just easier and faster to include the script like this. And while +I was at it, I doubled down on the remote library thing and included +also [highlight.js](https://highlightjs.org), +a package for rendering code blocks with syntax highlighting. + +### Scrolling with JavaScript + +The other big feature I wanted for the slides was for them to look and +behave like actual slides. So the whole HTML page should be divided into +single frames, and I wanted to be able to move back and forth between +frames by clicking or pressing a key. + +In order to do this, I had to write my first piece of JavaScript. +The main part looks more or less like this: + +``` +const slides = document.querySelectorAll(".slide"); + +const keysNext = ["ArrowRight", "ArrowDown", " "]; +const keysPrev = ["ArrowLeft", "ArrowUp"]; + +// Disable default action of the navigation keys (e.g. scrolling). +document.addEventListener("keydown", function(e) { + if (keysNext.includes(e.key) || keysPrev.includes(e.key)) { + e.preventDefault(); + } +}); + +function goto(slide) { + slide.focus(); + slide.scrollIntoView({ + behavior: "instant", + block: "start" + }); +} + +function onkeydown(i, e) { + if (keysNext.includes(e.key) && i+1 < slides.length) { + goto(slides[i+1]); + } + if (keysPrev.includes(e.key) && i > 0) { + goto(slides[i-1]); + } +} + +function onclick(i, e) { + const w = slides[i].offsetWidth; + const x = e.clientX; + + if (x > w/2 && i+1 < slides.length) { + goto(slides[i+1]); + } + if (x < w/2 && i > 0) { + goto(slides[i-1]); + } +} + +for (let i = 0; i < slides.length; i++) { + slides[i].addEventListener("keydown", e => onkeydown(i, e)); + slides[i].addEventListener("click", e => onclick(i, e)); +} + +goto(slides[0]); // Go to the first slide when the presentation starts +``` + +First of all, every slide is a `div` with `class="slide"`. This allows +me to select all the slides with `document.querySelectorAll(".slide")`. +Then, after disabling any default handling of the arrows and space keys, +I add a new event listeners to every slide. These listeners uses the +`scrollIntoView()` function to scroll to the next or previous slide. +The `onclick()` function similarly handles clicks, where a click on the +left half of the screen goes to the previous slide and a click on the +right half goes to the next one. + +And by the way, highjacking the default scrolling behavior is another +trend of modern web development that I hate. By I am fine with using +it here, because these slides are not meant to be a regular web page. + +I also a function to add a footer to every slide: + +``` +function slideFooter() { + const start = "
"; + const title = "Elliptic Curves and the ECM algorithm" + const link = "tronto.net/talks/ecm"; + const end = "
"; + const content = + "" + title + "" + + "" + link + ""; + + return start + content + end; +} + +// In the main loop: +// slides[i].innerHTML += slideFooter() +``` + +In an older version I also had a small slide counter in the footer, +but I decided not to use it in the end. + +Of course there was also some CSS work to +do. A new thing I learned in this regard is the +[flex](https://developer.mozilla.org/en-US/docs/Web/CSS/flex) +layout property, with which I was able to easily arrange +pieces of text and pictures in the slides - shoutout to +my friend [Jared](https://guissmo.com) for telling me about +it. Apart from this I don't have anything interesting to comment +about the CSS part of the slides. You can check the full code +[here](https://git.tronto.net/ecm/file/index.html.html) if you want; +everything is in a single HTML file. + +The result looks fine, but it does not work perfectly will every screen +resolution. It's fine in 4:3 or 16:9, but with wider screens your +mileage may vary. I could improve it and always use the device height +(or width, but not both) as a reference. But this is quite some work +for very little gain, and in the end all I care about is that I can +show these slides from my laptop. I am sorry if you are viewing this +presentation from a smartphone. + +You can view the slides +[on this page](https://sebastiano.tronto.net/talks/ecm). + +## Conclusion + +I didn't need to do all this work for this presentation, but it was fun to +learn new stuff - not only for the C++ part, that I did not end up using +anyway, but also for the slides. It's good to know a bit of JavaScript, +even if I don't plan to use it much in the future. + +I scheduled this post to go online on the same day as my presentation - +wish me good luck :) 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