ecm

Elliptic Curve factorization - code and slides
git clone https://git.tronto.net/ecm
Download | Log | Files | Refs | README

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>