sebastiano.tronto.net

ecm.md (11772B)

---

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