1 files changed, 283 insertions, 0 deletions

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:
+
+```
+<!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 :)