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