aboutsummaryrefslogtreecommitdiff
path: root/src/talks/ecm/index.html.raw
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2025-02-26 17:49:50 +0100
committerSebastiano Tronto <sebastiano@tronto.net>2025-02-27 15:25:18 +0100
commit5a41e71c95fe879f9fb93aa0472a8f1b3fbd028c (patch)
treee721ba359014ffc9d82ad9b97f1a134010e67885 /src/talks/ecm/index.html.raw
parent7c168659d729f21755ce71f99230051491b62244 (diff)
downloadsebastiano.tronto.net-5a41e71c95fe879f9fb93aa0472a8f1b3fbd028c.tar.gz
sebastiano.tronto.net-5a41e71c95fe879f9fb93aa0472a8f1b3fbd028c.zip
Added talk and blog post
Diffstat (limited to 'src/talks/ecm/index.html.raw')
-rw-r--r--src/talks/ecm/index.html.raw622
1 files changed, 622 insertions, 0 deletions
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 @@
1<!doctype html>
2<html lang="en">
3<head>
4 <title>Elliptic Curves and the ECM algorithm</title>
5 <meta name="viewport" content="width=device-width" />
6
7 <!-- Import MathJax script -->
8 <script id="MathJax-script" async src=
9 "https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"
10 ></script>
11
12 <!-- Import highlight.js script and style sheet -->
13 <script id="highlight.js" src="
14 https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.9.0/highlight.min.js"
15 ></script>
16 <link rel="stylesheet" href="
17 https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.9.0/styles/vs.css"
18 >
19
20 <!-- Custom style -->
21 <style>
22 html { height: 100vh; width: 98vw; margin: auto; font-family: sans-serif; }
23 h1 { font-size: 3.5vw; background-color: #eeeeee; margin: 0; }
24 body { font-size: 2.2vw; height: 100%; width: 100%; }
25 a, a:visited { color: #0f2899; text-decoration: none; }
26 a:hover { text-decoration: underline; }
27 figcaption { text-align: center; font-size: 1.5vw; }
28 em { font-style: normal; color: blue; }
29
30 .slide { outline: none; height: 100vh; width: 100%; }
31 .slide {
32 display: flex;
33 flex-direction: column;
34 justify-content: space-between;
35 }
36 .slide ul { margin-left: 1.5vw; }
37 .slide ol { margin-left: 1.5vw; }
38 .slide p { margin-left: 1.5vw; }
39
40 .slide.titlepage p, a { text-align: center; }
41 .slide.titlepage span.title { font-size: 3.6vw; font-weight: bold; }
42 .slide.titlepage span.author { }
43
44 .slide.ecsum img { width: 50%; display: block; margin: auto; }
45
46 .slide div.centertext { text-align: center; margin: auto; width: 60%; }
47
48 .columns {
49 display: flex;
50 flex-direction: row;
51 justify-content: space-between;
52 align-items: center;
53 }
54
55 .footer { font-size: 1.8vw; background-color: #eeeeee; }
56 .footer table { width: 100%; }
57 .footer-title { font-weight: bold; }
58 .footer-link { text-align: right; }
59 </style>
60 <meta charset="utf-8">
61</head>
62
63<body>
64
65<div class="slide titlepage" tabindex="-1"
66style="background-image: url('images/sum-2c.png');
67background-position: center;
68background-repeat: no-repeat;
69background-size: 70%;
70background-color: rgba(255, 255, 255, 0.85);
71background-blend-mode: overlay;">
72
73<p></p>
74
75<p><span class="title">Elliptic curves and the ECM algorithm<span></p>
76<p><span class="author">Sebastiano Tronto<span></p>
77<p><span class="event">ALTEN Scientific Software Evening<span></p>
78
79</div>
80
81<div class="slide titlepage" tabindex="-1"
82style="background-image: url('images/numbers.jpg');
83background-position: center;
84background-repeat: no-repeat;
85background-size: 100%;
86background-color: rgba(255, 255, 255, 0.75);
87background-blend-mode: overlay;">
88<p></p>
89<p><span class="title">Part I: Numbers<span></p>
90<p></p>
91</div>
92
93<div class="slide" tabindex="-1">
94<h1>The integers</h1>
95
96<img alt="The number line" src="images/number-line.png"
97 style="width: 70%; margin-left: 15%; margin-right: 15%;"/>
98
99<ul>
100<li>Operations: sum \(+\), difference \(-\) and multiplication \(\times\)</li>
101<li>Various properties: associativity, commutativity, etc...</li>
102<li>What about division (without remainder)?<br>
103If <tt>\(\frac ab\)</tt> is an integer we say that
104<tt>\(a\)</tt><em> divides </em><tt>\(b\)</tt> (in code:
105<tt>a % b == 0</tt>)</li>
106</ul>
107</div>
108
109<div class="slide" tabindex="-1">
110<h1>The integers modulo N</h1>
111
112<div class="columns">
113
114<ul>
115<!-- li>Integers modulo <tt>N</tt>: the possible remainders of
116division by <tt>N</tt><br-->
117<li>Two numbers are the same if they give the <em>same remainder</em>
118when divided by <tt>N</tt></li>
119<li>Think of <tt>int</tt>, but with <tt>% N</tt>
120after every operation</li>
121<li>Examples with \(N=12\):
122\[9+5\equiv 14\equiv 2\pmod{12}\]
123\[7-11\equiv-4\equiv 8\pmod{12}\]
124\[3\times 4\equiv 12\equiv 0\pmod{12}\]
125</li>
126</ul>
127
128<img alt="The number clock" src="images/clock.png"
129 style="width: 35%;"/>
130
131</div>
132
133</div>
134
135<div class="slide" tabindex="-1">
136<h1>The integers modulo N - Division</h1>
137
138<p style="text-align: center;"><strong>What about division?</strong></p>
139
140<ul>
141<li>
142Sometimes it works
143\[
144\frac 37\equiv 9 \pmod{12} \qquad
145\text{because} \qquad 9\times 7 \equiv 63 \equiv 3 \pmod{12}
146\]
147</li>
148
149<li>
150Sometimes it does not
151\[
152\frac 32\equiv \; ? \pmod{4} \qquad {\color{red}\text{Impossible!}}
153\]
154</li>
155</ul>
156</div>
157
158<div class="slide" tabindex="-1">
159<h1>Integers modulo N - Division</h1>
160
161<ul>
162<li>
163Sometimes it's... weird?
164\[
165\frac 62 \equiv \; ? \pmod{8} \quad
166\begin{array}{l}
167\rightarrow {\color{red}3} \times 2 \equiv 6\pmod{8}\\
168\rightarrow {\color{red}7} \times 2 \equiv 14 \equiv 6 \pmod{8}
169\end{array}
170\]
171</li>
172</div>
173
174<div class="slide" tabindex="-1">
175<h1>Integers modulo N - Division</h1>
176<div class="columns">
177<ul>
178<li>Can divide by \(a\) when \[\operatorname{GCD}(a, N)=1\]</li>
179<li>With the
180<a href="https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm">
181extended GCD algorithm</a> find \(x\) and \(y\) such that
182\[
183ax+Ny=1
184\]
185<li>
186This means \(\frac{1}{a}\equiv x\pmod{N}\)
187</li>
188</ul>
189<pre><code class="language-python"
190style="border: 0.2vw solid; font-size: 2.2vw;">
191def extended_gcd(a, b):
192 if b == 0:
193 return a, 1, 0
194 g, x, y = extended_gcd(b, a % b)
195 return g, y, x - y*(a // b)
196</code></pre>
197</div>
198<p style="text-align: center;">
199Division always works if \(N\) is a <em>prime</em> number!</p>
200</div>
201
202<div class="slide" tabindex="-1">
203<h1>Modular arithmetic - recap</h1>
204<div class="columns">
205<ul>
206<li>Integers modulo \(N\) are (almost) like numbers</li>
207<li>Normal operations like \(+\), \(-\) and \(\times\) work</li>
208<li>Division sometimes works, sometimes not</li>
209<li>Division always works if \(N\) is <em>prime</em></li>
210</ul>
211<img alt="The number line" src="images/clock2.png" style="width: 40%;"/>
212</div>
213</div>
214
215<div class="slide titlepage" tabindex="-1"
216style="background-image: url('images/sum-2c.png');
217background-position: center;
218background-repeat: no-repeat;
219background-size: 70%;
220background-color: rgba(255, 255, 255, 0.85);
221background-blend-mode: overlay;">
222<p></p>
223<p><span class="title">Part II: Elliptic Curves<span></p>
224<p></p>
225</div>
226
227<div class="slide" tabindex="-1">
228<h1>Elliptic curves</h1>
229
230<div class="columns">
231
232<p>
233An <em>elliptic curve</em> is a curve with equation
234\[ y^2 = x^3+Ax+B \]
235Where \(A\) and \(B\) are numbers with \[4A^3+27B^2\neq 0\]
236</p>
237
238<figure style="width: 45%;">
239<figcaption>\(y^2=x^3-x+1\) <br> \((A=-1, B=1\))</figcaption>
240<img alt="An elliptic curve" src="images/ec1.png" style="width: 100%;"/>
241</figure>
242
243</div>
244</div>
245
246<div class="slide" tabindex="-1">
247<h1>Elliptic curves</h1>
248
249<div class="columns">
250
251<figure style="width: 45%;">
252<figcaption>\(y^2=x^3+13x-34\) <br> \((A=13, B=-34\))</figcaption>
253<img alt="An elliptic curve" src="images/ec3.png" style="width: 100%;"/>
254</figure>
255
256<figure style="width: 45%;">
257<figcaption>\(y^2=x^3-x\) <br> \((A=-1, B=0\))</figcaption>
258<img alt="An elliptic curve" src="images/ec2.png" style="width: 100%;"/>
259</figure>
260
261</div>
262</div>
263
264<div class="slide" tabindex="-1">
265<h1>Elliptic curves</h1>
266
267<div class="columns">
268<ul>
269<li>There is a "sum" operation for points of a curve
270(NOT the sum of coordinates)</li>
271<li>To make things work out nicely, we pretend the curve has
272a <em>point at infinity</em> that acts as \(0\):
273\[P+0=0\qquad 0+P=0\qquad P-P=0\]</li>
274</ul>
275
276<img alt="Elliptic curve sum" src="images/sum-2c.png" style="width: 80%;"/>
277
278</div>
279</div>
280
281<div class="slide ecsum" tabindex="-1">
282<h1>Elliptic curves - sum operation - example 1</h2>
283<img alt="Elliptic curve sum" src="images/sum-2a.png"/>
284</div>
285<div class="slide ecsum" tabindex="-1">
286<h1>Elliptic curves - sum operation - example 1</h2>
287<img alt="Elliptic curve sum" src="images/sum-2b.png"/>
288</div>
289<div class="slide ecsum" tabindex="-1">
290<h1>Elliptic curves - sum operation - example 1</h2>
291<img alt="Elliptic curve sum" src="images/sum-2c.png"/>
292</div>
293
294<div class="slide ecsum" tabindex="-1">
295<h1>Elliptic curves - sum operation - example 2</h2>
296<img alt="Elliptic curve sum" src="images/sum-3a.png"/>
297</div>
298<div class="slide ecsum" tabindex="-1">
299<h1>Elliptic curves - sum operation - example 2</h2>
300<img alt="Elliptic curve sum" src="images/sum-3b.png"/>
301</div>
302<div class="slide ecsum" tabindex="-1">
303<h1>Elliptic curves - sum operation - example 2</h2>
304<img alt="Elliptic curve sum" src="images/sum-3c.png"/>
305</div>
306
307<div class="slide ecsum" tabindex="-1">
308<h1>Elliptic curves - sum operation - example 3</h2>
309<img alt="Elliptic curve sum" src="images/sum-4a.png"/>
310</div>
311<div class="slide ecsum" tabindex="-1">
312<h1>Elliptic curves - sum operation - example 3</h2>
313<img alt="Elliptic curve sum" src="images/sum-4b.png"/>
314</div>
315<div class="slide ecsum" tabindex="-1">
316<h1>Elliptic curves - sum operation - example 3</h2>
317<img alt="Elliptic curve sum" src="images/sum-4c.png"/>
318</div>
319
320<div class="slide" tabindex="-1">
321<h1>Elliptic curves - sum operation - code</h1>
322
323<div class="columns">
324<pre><code class="language-python"
325style="font-size: 2.8vh;">
326# Computes p+q on the elliptic curve y^2 = x^3 + Ax + B
327def ec_sum(p: Point, q: Point, A: double) -> Point:
328 if p.is_zero:
329 return q
330 if q.is_zero:
331 return p
332 if p.x == q.x and p.y == -q.y:
333 return Point(is_zero = True)
334
335 if p.x != q.x:
336 k = (p.y - q.y) / (p.x - q.x)
337 else:
338 k = (3 * p.x**2 + A) / (p.y + q.y)
339
340 new_x = k**2 - p.x - q.x
341 new_y = k * (p.x - new_x) - p.y
342 return Point(x = new_x, y = new_y)
343</code></pre>
344
345<pre><code class="language-python"
346style="border: 0.2vw solid; font-size: 2.8vh;">
347@dataclass
348class Point:
349 x: int = 0
350 y: int = 0
351 is_zero: bool = False
352</code></pre>
353
354</div>
355</div>
356
357<div class="slide" tabindex="-1">
358<h1>Elliptic curves - recap</h1>
359<div class="columns">
360<ul>
361<li>Curves of equation \(y^2=x^3+Ax+B\)</li>
362<li>Can "sum" points of the same curve</li>
363<li>Nice properties: associativity, commutativity...</li>
364<li>The sum operation can be easily implemented</li>
365</ul>
366<img alt="The number line" src="images/sum-2c.png" style="width: 40%;"/>
367</div>
368</div>
369
370<div class="slide titlepage" tabindex="-1"
371style="background-image: url('images/factorization.webp');
372background-position: center;
373background-repeat: no-repeat;
374background-size: 50%;
375background-color: rgba(255, 255, 255, 0.90);
376background-blend-mode: overlay;">
377<p></p>
378<p><span class="title">Part III: The Elliptic Curve Factorization Method<span></p>
379<p></p>
380</div>
381
382<div class="slide" tabindex="-1">
383<h1>Integer factorization</h1>
384<p style="text-align: center;"><strong>
385Every positive integer can be written as the product of prime numbers
386</strong></p>
387<div class="columns">
388<ul>
389<li>Example: \(69420 = 2\times 2\times 3\times 5\times 13\times 89\)</li>
390<li>Computationally hard</li>
391<li>Important for cryptography!</li>
392</ul>
393<img src="images/euclid.png" style="height: 60vh;"/>
394</div>
395</div>
396
397<div class="slide" tabindex="-1">
398<h1>Integer factorization - high-level procedure</h1>
399
400<div class="columns">
401<pre><code class="language-python"
402style="border: 0.2vw solid; font-size: 1.4vw;">
403# Returns the list of prime factors of n
404def factorize(n: int) -> list:
405 if n == 1:
406 return []
407
408 if is_prime(n):
409 return [n]
410
411 f = find_factor(n)
412
413 return factorize(n) + factorize(n//f)
414</code></pre>
415
416<ul>
417<li><tt>is_prime(n)</tt> can be implemented
418efficiently
419(<a href="https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test">Miller-Rabin</a>,
420<a href="https://en.wikipedia.org/wiki/AKS_primality_test">AKS</a>
421or <a href="https://en.wikipedia.org/wiki/Elliptic_curve_primality">ECPP</a>)
422</li>
423<li>Naive implementation of <tt>find_factor(n):</tt>
424<pre><code class="language-python" style="font-size: 2vw;">
425def find_factor(n: int) -> int:
426 for i in range(2,floor(sqrt(n))+1):
427 if n % i == 0:
428 return i
429</code></pre>
430</li>
431</ul>
432
433</div>
434</div>
435
436<div class="slide" tabindex="-1">
437<h1>Find Factor - Elliptic Curve Method</h1>
438<div>
439<p><strong>To find a factor of \(n\):</strong><p>
440<ol>
441<li>Take a random Elliptic Curve \(E\)
442and a random point \(P\) of \(E\)</li>
443<li>Take a <em>suitable number \(m\)</em></li>
444<li>Try to compute \(m\cdot P = P+P+\cdots+P\quad\) (\(m\) times)
445with <em>coordinates modulo \(n\)</em></li>
446<li>If you attempt an <em>impossible division</em> by some number \(d\),
447<em>return \(\operatorname{GCD}(n,d)\)</em></li>
448<li>Go back to 1.</li>
449</ol>
450</div>
451</div>
452
453<div class="slide" tabindex="-1" style="font-size: 2vw;">
454<h1>Find Factor - Elliptic Curve Method - Example</h1>
455<ul>
456<li>Take \(n = 91\)</li>
457<li>Take \(E: y^2 = x^3 + 51x -371\) and \(P = (11, 39)\) and \(M = 2\)</li>
458<li>
459Try to compute \(M\cdot P=P+P\pmod n\):
460\[ k = \frac{3x_p^2+51}{2y_p} \pmod n\]
461Is \(2y_p=78\) invertible modulo \(91\)?
462\[ \operatorname{GCD}(78, 91) = 13 \neq 1 \quad \implies \quad \text{NO!} \]
463</li>
464<li>Found factor: \(13\)</li>
465</div>
466
467<div class="slide titlepage" tabindex="-1"
468style="background-image: url('images/demo.jpg');
469background-position: center;
470background-repeat: no-repeat;
471background-size: 100%;
472background-color: rgba(255, 255, 255, 0.60);
473background-blend-mode: overlay;">
474<p></p>
475<p><span class="title">Demo time!<span></p>
476<a href="https://git.tronto.net/ecm">git.tronto.net/ecm</a>
477<p></p>
478</div>
479
480<div class="slide" tabindex="-1">
481<h1>Elliptic Curve Method - Questions</h1>
482<div class="centertext">
483<p><strong>
484Q: Aren't we just computing the \(\operatorname{GCD}\) with random numbers?
485</strong></p>
486<p>
487A: Yes, but Elliptic Curve operations produce "good candidates"
488for these random numbers.
489</p>
490</div>
491</div>
492
493<div class="slide" tabindex="-1">
494<h1>Elliptic Curve Method - Questions</h1>
495<div class="centertext">
496<p><strong>Q: Can we do the same without elliptic curves?</strong></p>
497<p>A: Yes, with
498<a href="https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm">
499Pollard's \(p-1\) Algorithm</a>, but ECM is faster.</p>
500</div>
501</div>
502
503<div class="slide" tabindex="-1">
504<h1>Elliptic Curve Method - Questions</h1>
505<div class="centertext">
506<p><strong>
507Q: Are there objects that are more complicated than Elliptic Curves
508and can make the method even faster?
509</strong></p>
510<p>A: Yes, there are higher-dimensional
511<a href="https://en.wikipedia.org/wiki/Abelian_variety">
512Abelian Varieties</a> and other
513<a href="https://en.wikipedia.org/wiki/Algebraic_group">
514Algebraic Groups</a>, but they are much harder (if not impossible)
515to implement efficiently.</p>
516</div>
517</div>
518
519<div class="slide titlepage" tabindex="-1"
520style="background-image: url('images/questions.png');
521background-position: center;
522background-repeat: no-repeat;
523background-size: 60%;
524background-color: rgba(255, 255, 255, 0.85);
525background-blend-mode: overlay;">
526<p></p>
527<p><span class="title">More questions?<span></p>
528<p></p>
529</div>
530
531<div class="slide titlepage" tabindex="-1"
532style="background-image: url('images/beer.jpg');
533background-position: center;
534background-repeat: no-repeat;
535background-size: 80%;
536background-color: rgba(255, 255, 255, 0.65);
537background-blend-mode: overlay;">
538<p></p>
539<p><span class="title">Drinks!<span></p>
540<p></p>
541</div>
542
543<script>
544 // The list of all slides of the presentation.
545 const slides = document.querySelectorAll(".slide");
546
547 // Navigation keys.
548 const keysNext = ["ArrowRight", "ArrowDown", " "];
549 const keysPrev = ["ArrowLeft", "ArrowUp"];
550
551 // Function to move to a given slide.
552 // This also focuses the slide, so any key press will be
553 // handled by the correct slide's event handler.
554 function goto(slide) {
555 slide.focus();
556 slide.scrollIntoView({
557 behavior: "instant",
558 block: "start"
559 });
560 }
561
562 // Handle key press events.
563 function onkeydown(i, e) {
564 if (keysNext.includes(e.key) && i+1 < slides.length) {
565 goto(slides[i+1]);
566 }
567 if (keysPrev.includes(e.key) && i > 0) {
568 goto(slides[i-1]);
569 }
570 }
571
572 // Handle click or tap events.
573 // Tapping on the right half of the screen scrolls forwards,
574 // tapping on the left half scrolls backwards.
575 function onclick(i, e) {
576 const w = slides[i].offsetWidth;
577 const x = e.clientX;
578
579 if (x > w/2 && i+1 < slides.length) {
580 goto(slides[i+1]);
581 }
582 if (x < w/2 && i > 0) {
583 goto(slides[i-1]);
584 }
585 }
586
587 // Disable default action of the navigation keys (e.g. scrolling).
588 document.addEventListener("keydown", function(e) {
589 if (keysNext.includes(e.key) || keysPrev.includes(e.key)) {
590 e.preventDefault();
591 }
592 });
593
594 // Function to add a footer to every slide.
595 function slideFooter() {
596 const start = "<div class=\"footer\"><table class=\"footer-table\"><tr>";
597 const title = "Elliptic Curves and the ECM algorithm"
598 const link = "<a href=https://tronto.net/talks/ecm>tronto.net/talks/ecm</a>";
599 const end = "</tr></table></div>";
600 const content =
601 "<td class=\"footer-title\">" + title + "</td>" +
602 "<td class=\"footer-link\">" + link + "</td>";
603
604 return start + content + end;
605 }
606
607 // Add slide footers and event handlers.
608 for (let i = 0; i < slides.length; i++) {
609 slides[i].innerHTML += slideFooter();
610 slides[i].addEventListener("keydown", e => onkeydown(i, e));
611 slides[i].addEventListener("click", e => onclick(i, e));
612 }
613
614 // Focus and scroll into view the first slide.
615 goto(slides[0]);
616
617 // Call highlight.js
618 hljs.highlightAll();
619</script>
620
621</body>
622</html>

Generated with cgit - Back to sebastiano.tronto.net