commit 5a41e71c95fe879f9fb93aa0472a8f1b3fbd028c parent 7c168659d729f21755ce71f99230051491b62244 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Wed, 26 Feb 2025 17:49:50 +0100 Added talk and blog post Diffstat:
28 files changed, 913 insertions(+), 0 deletions(-)
diff --git a/build.sh b/build.sh @@ -29,6 +29,10 @@ copyfile() { t="$(htmltitle "$file")" cat top.html "$file" bottom.html | sed "s/TITLE/$t/" > "$ind" ;; + raw) + namenoraw="$(basename "$file" | sed 's/\.raw$//')" + cp "$file" "$dest/$namenoraw" + ;; *) cp "$file" "$dest/$(basename "$file")" esac diff --git a/src/blog/2025-02-27-elliptic-curves-javascript/ecm.md 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: + +``` +<!doctype html> +<head> + <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"> + </script> +</head> + +<body> + <p>Hello! \[ e^{\pi i} + 1 = 0 \]</p> +</body> +``` + +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 = "<div class=\"footer\"><table class=\"footer-table\"><tr>"; + const title = "Elliptic Curves and the ECM algorithm" + const link = "<a href=https://tronto.net/talks/ecm>tronto.net/talks/ecm</a>"; + const end = "</tr></table></div>"; + const content = + "<td class=\"footer-title\">" + title + "</td>" + + "<td class=\"footer-link\">" + link + "</td>"; + + 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 Binary files differ. diff --git a/src/talks/ecm/images/clock.png b/src/talks/ecm/images/clock.png Binary files differ. diff --git a/src/talks/ecm/images/clock2.png b/src/talks/ecm/images/clock2.png Binary files differ. diff --git a/src/talks/ecm/images/demo.jpg b/src/talks/ecm/images/demo.jpg Binary files differ. diff --git a/src/talks/ecm/images/ec1.png b/src/talks/ecm/images/ec1.png Binary files differ. diff --git a/src/talks/ecm/images/ec2.png b/src/talks/ecm/images/ec2.png Binary files differ. diff --git a/src/talks/ecm/images/ec3.png b/src/talks/ecm/images/ec3.png Binary files differ. diff --git a/src/talks/ecm/images/euclid.png b/src/talks/ecm/images/euclid.png Binary files differ. diff --git a/src/talks/ecm/images/factorization.webp b/src/talks/ecm/images/factorization.webp Binary files differ. diff --git a/src/talks/ecm/images/number-line.png b/src/talks/ecm/images/number-line.png Binary files differ. diff --git a/src/talks/ecm/images/numbers.jpg b/src/talks/ecm/images/numbers.jpg Binary files differ. diff --git a/src/talks/ecm/images/questions.png b/src/talks/ecm/images/questions.png Binary files differ. diff --git a/src/talks/ecm/images/sum-1a.png b/src/talks/ecm/images/sum-1a.png Binary files differ. diff --git a/src/talks/ecm/images/sum-1b.png b/src/talks/ecm/images/sum-1b.png Binary files differ. diff --git a/src/talks/ecm/images/sum-1c.png b/src/talks/ecm/images/sum-1c.png Binary files differ. diff --git a/src/talks/ecm/images/sum-2a.png b/src/talks/ecm/images/sum-2a.png Binary files differ. diff --git a/src/talks/ecm/images/sum-2b.png b/src/talks/ecm/images/sum-2b.png Binary files differ. diff --git a/src/talks/ecm/images/sum-2c.png b/src/talks/ecm/images/sum-2c.png Binary files differ. diff --git a/src/talks/ecm/images/sum-3a.png b/src/talks/ecm/images/sum-3a.png Binary files differ. diff --git a/src/talks/ecm/images/sum-3b.png b/src/talks/ecm/images/sum-3b.png Binary files differ. diff --git a/src/talks/ecm/images/sum-3c.png b/src/talks/ecm/images/sum-3c.png Binary files differ. diff --git a/src/talks/ecm/images/sum-4a.png b/src/talks/ecm/images/sum-4a.png Binary files differ. diff --git a/src/talks/ecm/images/sum-4b.png b/src/talks/ecm/images/sum-4b.png Binary files differ. diff --git a/src/talks/ecm/images/sum-4c.png b/src/talks/ecm/images/sum-4c.png Binary files differ. diff --git a/src/talks/ecm/index.html.raw b/src/talks/ecm/index.html.raw @@ -0,0 +1,622 @@ +<!doctype html> +<html lang="en"> +<head> + <title>Elliptic Curves and the ECM algorithm</title> + <meta name="viewport" content="width=device-width" /> + + <!-- Import MathJax script --> + <script id="MathJax-script" async src= + "https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js" + ></script> + + <!-- Import highlight.js script and style sheet --> + <script id="highlight.js" src=" + https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.9.0/highlight.min.js" + ></script> + <link rel="stylesheet" href=" + https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.9.0/styles/vs.css" + > + + <!-- Custom style --> + <style> + html { height: 100vh; width: 98vw; margin: auto; font-family: sans-serif; } + h1 { font-size: 3.5vw; background-color: #eeeeee; margin: 0; } + body { font-size: 2.2vw; height: 100%; width: 100%; } + a, a:visited { color: #0f2899; text-decoration: none; } + a:hover { text-decoration: underline; } + figcaption { text-align: center; font-size: 1.5vw; } + em { font-style: normal; color: blue; } + + .slide { outline: none; height: 100vh; width: 100%; } + .slide { + display: flex; + flex-direction: column; + justify-content: space-between; + } + .slide ul { margin-left: 1.5vw; } + .slide ol { margin-left: 1.5vw; } + .slide p { margin-left: 1.5vw; } + + .slide.titlepage p, a { text-align: center; } + .slide.titlepage span.title { font-size: 3.6vw; font-weight: bold; } + .slide.titlepage span.author { } + + .slide.ecsum img { width: 50%; display: block; margin: auto; } + + .slide div.centertext { text-align: center; margin: auto; width: 60%; } + + .columns { + display: flex; + flex-direction: row; + justify-content: space-between; + align-items: center; + } + + .footer { font-size: 1.8vw; background-color: #eeeeee; } + .footer table { width: 100%; } + .footer-title { font-weight: bold; } + .footer-link { text-align: right; } + </style> + <meta charset="utf-8"> +</head> + +<body> + +<div class="slide titlepage" tabindex="-1" +style="background-image: url('images/sum-2c.png'); +background-position: center; +background-repeat: no-repeat; +background-size: 70%; +background-color: rgba(255, 255, 255, 0.85); +background-blend-mode: overlay;"> + +<p></p> + +<p><span class="title">Elliptic curves and the ECM algorithm<span></p> +<p><span class="author">Sebastiano Tronto<span></p> +<p><span class="event">ALTEN Scientific Software Evening<span></p> + +</div> + +<div class="slide titlepage" tabindex="-1" +style="background-image: url('images/numbers.jpg'); +background-position: center; +background-repeat: no-repeat; +background-size: 100%; +background-color: rgba(255, 255, 255, 0.75); +background-blend-mode: overlay;"> +<p></p> +<p><span class="title">Part I: Numbers<span></p> +<p></p> +</div> + +<div class="slide" tabindex="-1"> +<h1>The integers</h1> + +<img alt="The number line" src="images/number-line.png" + style="width: 70%; margin-left: 15%; margin-right: 15%;"/> + +<ul> +<li>Operations: sum \(+\), difference \(-\) and multiplication \(\times\)</li> +<li>Various properties: associativity, commutativity, etc...</li> +<li>What about division (without remainder)?<br> +If <tt>\(\frac ab\)</tt> is an integer we say that +<tt>\(a\)</tt><em> divides </em><tt>\(b\)</tt> (in code: +<tt>a % b == 0</tt>)</li> +</ul> +</div> + +<div class="slide" tabindex="-1"> +<h1>The integers modulo N</h1> + +<div class="columns"> + +<ul> +<!-- li>Integers modulo <tt>N</tt>: the possible remainders of +division by <tt>N</tt><br--> +<li>Two numbers are the same if they give the <em>same remainder</em> +when divided by <tt>N</tt></li> +<li>Think of <tt>int</tt>, but with <tt>% N</tt> +after every operation</li> +<li>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}\] +</li> +</ul> + +<img alt="The number clock" src="images/clock.png" + style="width: 35%;"/> + +</div> + +</div> + +<div class="slide" tabindex="-1"> +<h1>The integers modulo N - Division</h1> + +<p style="text-align: center;"><strong>What about division?</strong></p> + +<ul> +<li> +Sometimes it works +\[ +\frac 37\equiv 9 \pmod{12} \qquad +\text{because} \qquad 9\times 7 \equiv 63 \equiv 3 \pmod{12} +\] +</li> + +<li> +Sometimes it does not +\[ +\frac 32\equiv \; ? \pmod{4} \qquad {\color{red}\text{Impossible!}} +\] +</li> +</ul> +</div> + +<div class="slide" tabindex="-1"> +<h1>Integers modulo N - Division</h1> + +<ul> +<li> +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} +\] +</li> +</div> + +<div class="slide" tabindex="-1"> +<h1>Integers modulo N - Division</h1> +<div class="columns"> +<ul> +<li>Can divide by \(a\) when \[\operatorname{GCD}(a, N)=1\]</li> +<li>With the +<a href="https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"> +extended GCD algorithm</a> find \(x\) and \(y\) such that +\[ +ax+Ny=1 +\] +<li> +This means \(\frac{1}{a}\equiv x\pmod{N}\) +</li> +</ul> +<pre><code class="language-python" +style="border: 0.2vw solid; font-size: 2.2vw;"> +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) +</code></pre> +</div> +<p style="text-align: center;"> +Division always works if \(N\) is a <em>prime</em> number!</p> +</div> + +<div class="slide" tabindex="-1"> +<h1>Modular arithmetic - recap</h1> +<div class="columns"> +<ul> +<li>Integers modulo \(N\) are (almost) like numbers</li> +<li>Normal operations like \(+\), \(-\) and \(\times\) work</li> +<li>Division sometimes works, sometimes not</li> +<li>Division always works if \(N\) is <em>prime</em></li> +</ul> +<img alt="The number line" src="images/clock2.png" style="width: 40%;"/> +</div> +</div> + +<div class="slide titlepage" tabindex="-1" +style="background-image: url('images/sum-2c.png'); +background-position: center; +background-repeat: no-repeat; +background-size: 70%; +background-color: rgba(255, 255, 255, 0.85); +background-blend-mode: overlay;"> +<p></p> +<p><span class="title">Part II: Elliptic Curves<span></p> +<p></p> +</div> + +<div class="slide" tabindex="-1"> +<h1>Elliptic curves</h1> + +<div class="columns"> + +<p> +An <em>elliptic curve</em> is a curve with equation +\[ y^2 = x^3+Ax+B \] +Where \(A\) and \(B\) are numbers with \[4A^3+27B^2\neq 0\] +</p> + +<figure style="width: 45%;"> +<figcaption>\(y^2=x^3-x+1\) <br> \((A=-1, B=1\))</figcaption> +<img alt="An elliptic curve" src="images/ec1.png" style="width: 100%;"/> +</figure> + +</div> +</div> + +<div class="slide" tabindex="-1"> +<h1>Elliptic curves</h1> + +<div class="columns"> + +<figure style="width: 45%;"> +<figcaption>\(y^2=x^3+13x-34\) <br> \((A=13, B=-34\))</figcaption> +<img alt="An elliptic curve" src="images/ec3.png" style="width: 100%;"/> +</figure> + +<figure style="width: 45%;"> +<figcaption>\(y^2=x^3-x\) <br> \((A=-1, B=0\))</figcaption> +<img alt="An elliptic curve" src="images/ec2.png" style="width: 100%;"/> +</figure> + +</div> +</div> + +<div class="slide" tabindex="-1"> +<h1>Elliptic curves</h1> + +<div class="columns"> +<ul> +<li>There is a "sum" operation for points of a curve +(NOT the sum of coordinates)</li> +<li>To make things work out nicely, we pretend the curve has +a <em>point at infinity</em> that acts as \(0\): +\[P+0=0\qquad 0+P=0\qquad P-P=0\]</li> +</ul> + +<img alt="Elliptic curve sum" src="images/sum-2c.png" style="width: 80%;"/> + +</div> +</div> + +<div class="slide ecsum" tabindex="-1"> +<h1>Elliptic curves - sum operation - example 1</h2> +<img alt="Elliptic curve sum" src="images/sum-2a.png"/> +</div> +<div class="slide ecsum" tabindex="-1"> +<h1>Elliptic curves - sum operation - example 1</h2> +<img alt="Elliptic curve sum" src="images/sum-2b.png"/> +</div> +<div class="slide ecsum" tabindex="-1"> +<h1>Elliptic curves - sum operation - example 1</h2> +<img alt="Elliptic curve sum" src="images/sum-2c.png"/> +</div> + +<div class="slide ecsum" tabindex="-1"> +<h1>Elliptic curves - sum operation - example 2</h2> +<img alt="Elliptic curve sum" src="images/sum-3a.png"/> +</div> +<div class="slide ecsum" tabindex="-1"> +<h1>Elliptic curves - sum operation - example 2</h2> +<img alt="Elliptic curve sum" src="images/sum-3b.png"/> +</div> +<div class="slide ecsum" tabindex="-1"> +<h1>Elliptic curves - sum operation - example 2</h2> +<img alt="Elliptic curve sum" src="images/sum-3c.png"/> +</div> + +<div class="slide ecsum" tabindex="-1"> +<h1>Elliptic curves - sum operation - example 3</h2> +<img alt="Elliptic curve sum" src="images/sum-4a.png"/> +</div> +<div class="slide ecsum" tabindex="-1"> +<h1>Elliptic curves - sum operation - example 3</h2> +<img alt="Elliptic curve sum" src="images/sum-4b.png"/> +</div> +<div class="slide ecsum" tabindex="-1"> +<h1>Elliptic curves - sum operation - example 3</h2> +<img alt="Elliptic curve sum" src="images/sum-4c.png"/> +</div> + +<div class="slide" tabindex="-1"> +<h1>Elliptic curves - sum operation - code</h1> + +<div class="columns"> +<pre><code class="language-python" +style="font-size: 2.8vh;"> +# 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) +</code></pre> + +<pre><code class="language-python" +style="border: 0.2vw solid; font-size: 2.8vh;"> +@dataclass +class Point: + x: int = 0 + y: int = 0 + is_zero: bool = False +</code></pre> + +</div> +</div> + +<div class="slide" tabindex="-1"> +<h1>Elliptic curves - recap</h1> +<div class="columns"> +<ul> +<li>Curves of equation \(y^2=x^3+Ax+B\)</li> +<li>Can "sum" points of the same curve</li> +<li>Nice properties: associativity, commutativity...</li> +<li>The sum operation can be easily implemented</li> +</ul> +<img alt="The number line" src="images/sum-2c.png" style="width: 40%;"/> +</div> +</div> + +<div class="slide titlepage" tabindex="-1" +style="background-image: url('images/factorization.webp'); +background-position: center; +background-repeat: no-repeat; +background-size: 50%; +background-color: rgba(255, 255, 255, 0.90); +background-blend-mode: overlay;"> +<p></p> +<p><span class="title">Part III: The Elliptic Curve Factorization Method<span></p> +<p></p> +</div> + +<div class="slide" tabindex="-1"> +<h1>Integer factorization</h1> +<p style="text-align: center;"><strong> +Every positive integer can be written as the product of prime numbers +</strong></p> +<div class="columns"> +<ul> +<li>Example: \(69420 = 2\times 2\times 3\times 5\times 13\times 89\)</li> +<li>Computationally hard</li> +<li>Important for cryptography!</li> +</ul> +<img src="images/euclid.png" style="height: 60vh;"/> +</div> +</div> + +<div class="slide" tabindex="-1"> +<h1>Integer factorization - high-level procedure</h1> + +<div class="columns"> +<pre><code class="language-python" +style="border: 0.2vw solid; font-size: 1.4vw;"> +# 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) +</code></pre> + +<ul> +<li><tt>is_prime(n)</tt> can be implemented +efficiently +(<a href="https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test">Miller-Rabin</a>, +<a href="https://en.wikipedia.org/wiki/AKS_primality_test">AKS</a> +or <a href="https://en.wikipedia.org/wiki/Elliptic_curve_primality">ECPP</a>) +</li> +<li>Naive implementation of <tt>find_factor(n):</tt> +<pre><code class="language-python" style="font-size: 2vw;"> +def find_factor(n: int) -> int: + for i in range(2,floor(sqrt(n))+1): + if n % i == 0: + return i +</code></pre> +</li> +</ul> + +</div> +</div> + +<div class="slide" tabindex="-1"> +<h1>Find Factor - Elliptic Curve Method</h1> +<div> +<p><strong>To find a factor of \(n\):</strong><p> +<ol> +<li>Take a random Elliptic Curve \(E\) +and a random point \(P\) of \(E\)</li> +<li>Take a <em>suitable number \(m\)</em></li> +<li>Try to compute \(m\cdot P = P+P+\cdots+P\quad\) (\(m\) times) +with <em>coordinates modulo \(n\)</em></li> +<li>If you attempt an <em>impossible division</em> by some number \(d\), +<em>return \(\operatorname{GCD}(n,d)\)</em></li> +<li>Go back to 1.</li> +</ol> +</div> +</div> + +<div class="slide" tabindex="-1" style="font-size: 2vw;"> +<h1>Find Factor - Elliptic Curve Method - Example</h1> +<ul> +<li>Take \(n = 91\)</li> +<li>Take \(E: y^2 = x^3 + 51x -371\) and \(P = (11, 39)\) and \(M = 2\)</li> +<li> +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!} \] +</li> +<li>Found factor: \(13\)</li> +</div> + +<div class="slide titlepage" tabindex="-1" +style="background-image: url('images/demo.jpg'); +background-position: center; +background-repeat: no-repeat; +background-size: 100%; +background-color: rgba(255, 255, 255, 0.60); +background-blend-mode: overlay;"> +<p></p> +<p><span class="title">Demo time!<span></p> +<a href="https://git.tronto.net/ecm">git.tronto.net/ecm</a> +<p></p> +</div> + +<div class="slide" tabindex="-1"> +<h1>Elliptic Curve Method - Questions</h1> +<div class="centertext"> +<p><strong> +Q: Aren't we just computing the \(\operatorname{GCD}\) with random numbers? +</strong></p> +<p> +A: Yes, but Elliptic Curve operations produce "good candidates" +for these random numbers. +</p> +</div> +</div> + +<div class="slide" tabindex="-1"> +<h1>Elliptic Curve Method - Questions</h1> +<div class="centertext"> +<p><strong>Q: Can we do the same without elliptic curves?</strong></p> +<p>A: Yes, with +<a href="https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm"> +Pollard's \(p-1\) Algorithm</a>, but ECM is faster.</p> +</div> +</div> + +<div class="slide" tabindex="-1"> +<h1>Elliptic Curve Method - Questions</h1> +<div class="centertext"> +<p><strong> +Q: Are there objects that are more complicated than Elliptic Curves +and can make the method even faster? +</strong></p> +<p>A: Yes, there are higher-dimensional +<a href="https://en.wikipedia.org/wiki/Abelian_variety"> +Abelian Varieties</a> and other +<a href="https://en.wikipedia.org/wiki/Algebraic_group"> +Algebraic Groups</a>, but they are much harder (if not impossible) +to implement efficiently.</p> +</div> +</div> + +<div class="slide titlepage" tabindex="-1" +style="background-image: url('images/questions.png'); +background-position: center; +background-repeat: no-repeat; +background-size: 60%; +background-color: rgba(255, 255, 255, 0.85); +background-blend-mode: overlay;"> +<p></p> +<p><span class="title">More questions?<span></p> +<p></p> +</div> + +<div class="slide titlepage" tabindex="-1" +style="background-image: url('images/beer.jpg'); +background-position: center; +background-repeat: no-repeat; +background-size: 80%; +background-color: rgba(255, 255, 255, 0.65); +background-blend-mode: overlay;"> +<p></p> +<p><span class="title">Drinks!<span></p> +<p></p> +</div> + +<script> + // The list of all slides of the presentation. + const slides = document.querySelectorAll(".slide"); + + // Navigation keys. + const keysNext = ["ArrowRight", "ArrowDown", " "]; + const keysPrev = ["ArrowLeft", "ArrowUp"]; + + // Function to move to a given slide. + // This also focuses the slide, so any key press will be + // handled by the correct slide's event handler. + function goto(slide) { + slide.focus(); + slide.scrollIntoView({ + behavior: "instant", + block: "start" + }); + } + + // Handle key press events. + 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]); + } + } + + // Handle click or tap events. + // Tapping on the right half of the screen scrolls forwards, + // tapping on the left half scrolls backwards. + 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]); + } + } + + // 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 to add a footer to every slide. + function slideFooter() { + const start = "<div class=\"footer\"><table class=\"footer-table\"><tr>"; + const title = "Elliptic Curves and the ECM algorithm" + const link = "<a href=https://tronto.net/talks/ecm>tronto.net/talks/ecm</a>"; + const end = "</tr></table></div>"; + const content = + "<td class=\"footer-title\">" + title + "</td>" + + "<td class=\"footer-link\">" + link + "</td>"; + + return start + content + end; + } + + // Add slide footers and event handlers. + for (let i = 0; i < slides.length; i++) { + slides[i].innerHTML += slideFooter(); + slides[i].addEventListener("keydown", e => onkeydown(i, e)); + slides[i].addEventListener("click", e => onclick(i, e)); + } + + // Focus and scroll into view the first slide. + goto(slides[0]); + + // Call highlight.js + hljs.highlightAll(); +</script> + +</body> +</html> diff --git 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)]
