commit 7f1b8a358515b45d717c3c4b5baf2fbc0f568170
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 26 Feb 2025 17:12:06 +0100
Initial commit
Diffstat:
33 files changed, 1499 insertions(+), 0 deletions(-)
diff --git a/README.md b/README.md
@@ -0,0 +1,63 @@
+# Elliptic curve factorization method
+
+Slides and code for the a presentation about
+[Lenstra's elliptic-curve factorization](https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization).
+
+See also [this blog post](https://sebastiano.tronto.net/blog/2025-02-27-ecm).
+
+## Abstract
+
+Elliptic curves are mathematical objects that have both a geometric and an
+arithmetic side. They turn out to be useful for real-world applications
+because they sit in a sweet spot: they are complicated enough to have
+interesting and useful arithmetic properties, but simple enough to be
+implemented in software in an efficient way. For example, they are used in
+cryptographic schemes, such as the Elliptic-curve Diffie-Hellman scheme,
+to obtain greater security with smaller keys.
+
+After introducing elliptic curves and modular arithmetic, we will take a
+look at the elliptic curve factorization method (ECM), one of the most
+efficient method to find the prime factors of an integer number. We
+will see in practice how much faster this method is compared to a naive
+algorithm, and we'll see that the implementation of this method is not
+that hard at all.
+
+## Slides
+
+The slides are a single html file, `index.html`. They rely on a couple
+of external JavaScript libraries. They are also hosted
+[here](https://sebastiano.tronto.net/talks/ecm).
+
+## Code
+
+The folder `code/python` contains two files:
+
+* `ecm.py`: an implementation of the ECM algorithm.
+* `naive.py`: an implementation of the simple O(√n) algorithm for finding
+ a factor of a number, for comparison.
+
+To use any of the two, pass the number to factor as a command-line argument,
+for example:
+
+```
+$ ./ecm.py 255000007030000033
+255000007030000033 = 510000011 * 500000003
+```
+
+Some benchmarks (note: the ECM is randomized, the time can vary a lot):
+
+```
+$ time ./ecm.py 255000007030000033
+255000007030000033 = 510000011 * 500000003
+ 0m01.45s real 0m01.43s user 0m00.01s system
+$ time ./naive.py 255000007030000033
+255000007030000033 = 500000003 * 510000011
+ 0m26.62s real 0m26.50s user 0m00.01s system
+```
+
+### C++ code (experimental)
+
+The folder `code/cpp` contains an experimental implementation of the ECM
+algorithm in C++. It works, but it is very slow: it requires suppport
+for compile-time big integers, which I implement in an inefficient way. I
+may optimize this code in the future.
diff --git a/code/cpp/a.out b/code/cpp/a.out
Binary files differ.
diff --git a/code/cpp/bigint.h b/code/cpp/bigint.h
@@ -0,0 +1,266 @@
+#ifndef BIGUNSIGNED_H
+#define BIGUNSIGNED_H
+
+#include <cstdint>
+#include <iostream>
+#include <random>
+#include <string_view>
+
+constexpr uint64_t abs64(int64_t);
+constexpr uint64_t pow10(uint64_t);
+
+// Big integer class for numbers of at most N decimal digits.
+// The number E is used to tune the size of each digit, mostly for
+// testing purposes.
+
+template<uint64_t N = 50, uint64_t E = 9>
+requires (E < 10)
+class BigInt {
+public:
+ // The member variables sign and digits are declared public so that
+ // BigInt becomes a structural type and can be used in templates.
+
+ static constexpr uint64_t M = pow10(E);
+ static constexpr uint64_t D = (N / E) + 1;
+
+ bool sign;
+ uint64_t digits[D];
+
+ constexpr BigInt() : sign{true} {
+ std::fill(digits, digits+D, 0);
+ }
+
+ constexpr BigInt(int64_t n) : sign{n >= 0} {
+ std::fill(digits, digits+D, 0);
+ digits[0] = abs64(n);
+ carryover();
+ }
+
+ constexpr BigInt(const std::string_view s) : sign{true} {
+ std::fill(digits, digits+D, 0);
+ if (s.size() == 0)
+ return;
+ for (int i = s.size()-1, j = 0; i >= 0; i--, j++) {
+ if (s[i] == '\'')
+ continue;
+ if (i == 0 && s[i] == '-') {
+ sign = false;
+ break;
+ }
+ digits[j/E] += (pow10(j % E))
+ * static_cast<uint64_t>(s[i] - '0');
+ }
+ }
+
+ constexpr auto operator<=>(const BigInt& other) const {
+ if (sign != other.sign)
+ return sign <=> other.sign;
+
+ for (int i = D-1; i >= 0; i--)
+ if (digits[i] != other.digits[i])
+ return sign ?
+ digits[i] <=> other.digits[i] :
+ other.digits[i] <=> digits[i];
+
+ return 0 <=> 0;
+ }
+
+ constexpr bool operator==(const BigInt& other) const = default;
+
+ constexpr BigInt abs() const {
+ BigInt ret = *this;
+ ret.sign = true;
+ return ret;
+ }
+
+ constexpr BigInt operator-() const {
+ if (*this == 0)
+ return 0;
+ BigInt ret = *this;
+ ret.sign = !ret.sign;
+ return ret;
+ }
+
+ constexpr BigInt operator+(const BigInt& z) const {
+ if (sign && z.sign)
+ return positive_sum(*this, z);
+ else if (sign && !z.sign)
+ return positive_diff(*this, -z);
+ else if (!sign && z.sign)
+ return positive_diff(z, -*this);
+ else
+ return -positive_sum(-*this, -z);
+ }
+
+ constexpr BigInt operator-(const BigInt& z) const {
+ return *this + (-z);
+ }
+
+ constexpr BigInt operator*(const BigInt& z) const {
+ BigInt ret;
+ ret.sign = !(sign ^ z.sign);
+ for (int i = 0; i < D; i++)
+ for (int j = 0; i+j < D; j++)
+ ret.digits[i+j] += digits[i] * z.digits[j];
+ ret.carryover();
+ return ret;
+ }
+
+ constexpr BigInt operator/(const BigInt& z) const {
+ auto [q, r] = euclidean_division(*this, z);
+ return q;
+ }
+
+ constexpr BigInt operator%(const BigInt& z) const {
+ auto [q, r] = euclidean_division(*this, z);
+ return r;
+ }
+
+ constexpr BigInt operator+=(const BigInt& z) { return *this = *this + z; }
+ constexpr BigInt operator++() { return *this += 1; }
+ constexpr BigInt operator-=(const BigInt& z) { return *this = *this - z; }
+ constexpr BigInt operator--() { return *this -= 1; }
+ constexpr BigInt operator*=(const BigInt& z) { return *this = *this * z; }
+ constexpr BigInt operator/=(const BigInt& z) { return *this = *this / z; }
+ constexpr BigInt operator%=(const BigInt& z) { return *this = *this % z; }
+
+ static BigInt random(BigInt r) {
+ std::random_device rd;
+ std::default_random_engine rng(rd());
+ std::uniform_int_distribution<int> distribution(0, M-1);
+
+ BigInt ret;
+ for (uint64_t i = 0; i < D; i++)
+ ret.digits[i] = distribution(rng);
+
+ return ret % r;
+ }
+
+ friend std::ostream& operator<<(std::ostream& os, const BigInt<N, E>& z) {
+ if (z == 0) {
+ os << "0";
+ return os;
+ }
+
+ if (!z.sign)
+ os << "-";
+
+ int j;
+ for (j = z.D-1; z.digits[j] == 0; j--) ;
+ os << z.digits[j]; // Top digit is not padded
+
+ for (int i = j-1; i >= 0; i--) {
+ std::string num = std::to_string(z.digits[i]);
+ os << std::string(E - num.length(), '0') << num;
+ }
+ return os;
+ }
+
+private:
+ constexpr void carryover() {
+ for (int i = 1; i < D; i++) {
+ auto c = digits[i-1] / M;
+ digits[i-1] -= c * M;
+ digits[i] += c;
+ }
+ }
+
+ constexpr BigInt half() const {
+ BigInt ret;
+ uint64_t carry = 0;
+ for (int i = D-1; i >= 0; i--) {
+ ret.digits[i] += (digits[i] + M * carry) / 2;
+ carry = digits[i] % 2;
+ }
+ return ret;
+ }
+
+ static constexpr BigInt powM(uint64_t e) {
+ BigInt ret;
+ ret.digits[e] = 1;
+ return ret;
+ }
+
+ // Sum of non-negative integers
+ static constexpr BigInt positive_sum(const BigInt& x, const BigInt& y) {
+ BigInt ret;
+ for (int i = 0; i < D; i++)
+ ret.digits[i] = x.digits[i] + y.digits[i];
+ ret.carryover();
+ return ret;
+ }
+
+ // Difference of non-negative integers (result may be negative)
+ static constexpr BigInt positive_diff(const BigInt& x, const BigInt& y) {
+ if (y > x)
+ return -positive_diff(y, x);
+
+ BigInt ret;
+ uint64_t carry = 0;
+ for (int i = 0; i < D; i++) {
+ uint64_t oldcarry = carry;
+ if (x.digits[i] < y.digits[i] + oldcarry) {
+ ret.digits[i] = M;
+ carry = 1;
+ } else {
+ carry = 0;
+ }
+ ret.digits[i] += x.digits[i];
+ ret.digits[i] -= y.digits[i] + oldcarry;
+ }
+ ret.carryover();
+ return ret;
+ }
+
+ // Division with remainder, UB if y == 0
+ static constexpr std::pair<BigInt, BigInt>
+ euclidean_division(const BigInt& x, const BigInt& y) {
+ auto [q, r] = positive_div(x.abs(), y.abs());
+ if (x.sign && y.sign)
+ return std::pair(q, r);
+ else if (x.sign && !y.sign)
+ return r == 0 ? std::pair(-q, 0) : std::pair(-q-1, y+r);
+ else if (!x.sign && y.sign)
+ return r == 0 ? std::pair(-q, r) : std::pair(-q-1, y-r);
+ else
+ return std::pair(q, -r);
+ }
+
+ // Division with remainder of non-negative integers, UB if y == 0
+ // This method is inefficient (O(log(x/y)) BigInt multiplications)
+ static constexpr std::pair<BigInt, BigInt>
+ positive_div(const BigInt& x, const BigInt& y) {
+ BigInt q = 0;
+ BigInt r = x;
+
+ if (y > x)
+ return std::pair(q, r);
+
+ BigInt lb = 0;
+ BigInt ub = x;
+ while (true) {
+ BigInt q = (ub + lb).half();
+ BigInt r = x - y*q;
+
+ if (r < 0)
+ ub = q;
+ else if (r >= y)
+ lb = q+1;
+ else
+ return std::pair(q, r);
+ }
+ }
+};
+
+constexpr uint64_t abs64(int64_t x) {
+ return static_cast<uint64_t>(x > 0 ? x : -x);
+}
+
+constexpr uint64_t pow10(uint64_t e) {
+ if (e == 0)
+ return 1;
+ else
+ return 10 * pow10(e-1);
+}
+
+#endif
diff --git a/code/cpp/ecm.cpp b/code/cpp/ecm.cpp
@@ -0,0 +1,91 @@
+#include "bigint.h"
+#include "zmodn.h"
+
+#include <cstdint>
+#include <iostream>
+#include <variant>
+
+constexpr BigInt N(NUMBER);
+
+class Point {
+public:
+ bool is_infinity;
+ Zmod<N> x;
+ Zmod<N> y;
+
+ Point(Zmod<N> a, Zmod<N> b) : is_infinity{false}, x{a}, y{b} {}
+ Point(bool inf) : is_infinity{inf}, x{0}, y{0} {}
+};
+
+std::variant<Point, BigInt<>>
+sum_or_factor(BigInt<> a, Point p, Point q) {
+ if (p.is_infinity) return q;
+ if (q.is_infinity) return p;
+ if (p.x == q.x && p.y + q.y == Zmod<N>(0)) return Point(true);
+
+ Zmod<N> l(0);
+ if (p.x != q.x)
+ if (auto inv_x = (p.x-q.x).inverse(); inv_x.has_value())
+ l = (p.y-q.y) * inv_x.value();
+ else
+ return std::get<0>(extended_gcd(N, (p.x-q.x).toint()));
+ else
+ if (auto inv_y = (p.y+q.y).inverse(); inv_y.has_value())
+ l = (Zmod<N>(3) * p.x * p.x + a) * inv_y.value();
+ else
+ return std::get<0>(extended_gcd(N, (p.y+q.y).toint()));
+
+ auto x = l*l - p.x - q.x;
+ auto y = l*(p.x-x) - p.y;
+
+ return Point(x, y);
+}
+
+std::variant<Point, BigInt<>>
+product_or_factor(BigInt<> a, std::variant<Point, BigInt<>> pi, BigInt<> m) {
+ if (std::holds_alternative<BigInt<>>(pi))
+ return std::get<BigInt<>>(pi);
+
+ auto p = std::get<Point>(pi);
+
+ if (m == 0)
+ return Point(true); // Anything multiplied by 0 is 0
+
+ // Divide-and-conquer multiplication (power) algorithm
+ if (m % 2 == 0) {
+ return product_or_factor(a, sum_or_factor(a, p, p), m/2);
+ } else {
+ auto pp = product_or_factor(a, p, m-1);
+ if (std::holds_alternative<BigInt<>>(pp))
+ return std::get<BigInt<>>(pp);
+ return sum_or_factor(a, p, std::get<Point>(pp));
+ }
+}
+
+BigInt<> find_factor_ecm() {
+ // Find a factor of the integer N.
+ // If N is prime, this method goes into an infinite loop.
+
+ while (true) {
+ BigInt a = BigInt<>::random(N);
+ Point p(BigInt<>::random(N), BigInt<>::random(N));
+ for (BigInt m = 2;
+ (m < 256 || m*m*m*m*m*m*m*m < N) && !p.is_infinity; m += 1) {
+ auto x = product_or_factor(a, p, m);
+ if (std::holds_alternative<BigInt<>>(x))
+ return std::get<BigInt<>>(x);
+ else
+ p = std::get<Point>(x);
+ }
+ }
+}
+
+int main() {
+ // N is a compile-time constant
+ if (BigInt f = find_factor_ecm(); f > 1 && f < N)
+ std::cout << N << " = " << f << " * " << N/f << std::endl;
+ else
+ std::cout << N << " is prime" << std::endl;
+
+ return 0;
+}
diff --git a/code/cpp/naive.cpp b/code/cpp/naive.cpp
@@ -0,0 +1,23 @@
+#include "bigint.h"
+
+#include <cstdint>
+#include <iostream>
+
+constexpr BigInt N(NUMBER);
+
+BigInt<> find_factor() {
+ for (BigInt i = 2; i*i < N; i += 1)
+ if (N % i == 0)
+ return i;
+ return -1;
+}
+
+int main() {
+ // N is a compile-time constant
+ if (auto f = find_factor(); f > 1 && f < N)
+ std::cout << N << " = " << f << " * " << N/f << std::endl;
+ else
+ std::cout << N << " is prime" << std::endl;
+
+ return 0;
+}
diff --git a/code/cpp/zmodn.h b/code/cpp/zmodn.h
@@ -0,0 +1,79 @@
+#ifndef ZMODN_H
+#define ZMODN_H
+
+#include <cstdint>
+#include <iostream>
+#include <optional>
+#include <tuple>
+#include <type_traits>
+
+template<typename T>
+concept Integer = requires(T a, T b, int i, std::ostream& os) {
+ {T(i)};
+
+ {a + b} -> std::same_as<T>;
+ {a - b} -> std::same_as<T>;
+ {a * b} -> std::same_as<T>;
+ {a / b} -> std::same_as<T>;
+ {a % b} -> std::same_as<T>;
+
+ {a == b} -> std::same_as<bool>;
+ {a != b} -> std::same_as<bool>;
+
+ {os << a} -> std::same_as<std::ostream&>;
+};
+
+template<Integer T>
+std::tuple<T, T, T> extended_gcd(T a, T b) {
+ if (b == 0) return {a, 1, 0};
+ auto [g, x, y] = extended_gcd(b, a%b);
+ return {g, y, x - y*(a/b)};
+}
+
+template<Integer auto N>
+requires(N > 1)
+class Zmod {
+public:
+ Zmod(decltype(N) z) : value{(z%N + N) % N} {}
+ decltype(N) toint() const { return value; }
+
+ Zmod operator+(const Zmod& z) const { return value + z.value; }
+ Zmod operator-(const Zmod& z) const { return value - z.value; }
+ Zmod operator*(const Zmod& z) const { return value * z.value; }
+
+ Zmod operator+=(const Zmod& z) { return (*this) = value + z.value; }
+ Zmod operator-=(const Zmod& z) { return (*this) = value - z.value; }
+ Zmod operator*=(const Zmod& z) { return (*this) = value * z.value; }
+
+ Zmod operator^(decltype(N) z) const {
+ if (z == 0) return 1;
+ if (z % 2 == 0) return (((*this) * (*this)) ^ (z/2));
+ return (*this) * ((*this) ^ (z-1));
+ }
+
+ bool operator==(const Zmod& z) const { return value == z.value; }
+ bool operator!=(const Zmod& z) const { return value != z.value; }
+
+ std::optional<Zmod> inverse() const {
+ auto [g, a, _] = extended_gcd(value, N);
+ return g == 1 ? Zmod(a) : std::optional<Zmod>{};
+ }
+
+ std::optional<Zmod> operator/(const Zmod& d) const {
+ auto i = d.inverse();
+ return i ? (*this) * i.value() : i;
+ }
+
+ std::optional<Zmod> operator/=(const Zmod& d) {
+ auto q = *this / d;
+ return q ? (*this = q.value()) : q;
+ }
+
+ friend std::ostream& operator<<(std::ostream& os, const Zmod<N>& z) {
+ return os << "(" << z.value << " mod " << N << ")";
+ }
+private:
+ decltype(N) value;
+};
+
+#endif
diff --git a/code/python/ecm.py b/code/python/ecm.py
@@ -0,0 +1,75 @@
+#! /bin/env python
+
+from sys import argv
+from random import randint
+from math import sqrt
+from dataclasses import dataclass
+
+@dataclass
+class Point:
+ x: int = 0
+ y: int = 0
+ is_zero: bool = False
+
+@dataclass
+class FactorFound(Exception):
+ factor: int = 0
+
+# Returns gcd(a, b) and x, y such that ax + by = gcd(a,b)
+def extended_gcd(a: int, b: int) -> (int, int, int):
+ if b == 0:
+ return a, 1, 0
+ g, x, y = extended_gcd(b, a % b)
+ return g, y, x - y * (a // b)
+
+def inverse_modulo(a: int, n: int) -> int:
+ g, x, y = extended_gcd(a, n)
+ if g != 1:
+ raise FactorFound(g)
+ return x
+
+def ec_sum(p: Point, q: Point, A: int, n: int) -> Point:
+ if p.is_zero:
+ return q
+ if q.is_zero:
+ return p
+ if (p.x - q.x) % n == 0 and (p.y + q.y) % n == 0:
+ return Point(is_zero = True)
+
+ if (p.x - q.x) % n != 0:
+ k = ((p.y - q.y) * inverse_modulo(p.x - q.x, n)) % n
+ else:
+ k = ((3 * p.x**2 + A) * inverse_modulo(p.y + q.y, n)) % n
+
+ x = (k**2 - p.x - q.x) % n
+ y = (k * (p.x - x) - p.y) % n
+
+ return Point(x = x, y = y)
+
+def ec_mul(M: int, p: Point, A: int, n: int) -> Point:
+ if M == 0:
+ return Point(is_zero = True)
+ if M % 2 == 0:
+ return ec_mul(M // 2, ec_sum(p, p, A, n), A, n)
+ return ec_sum(p, ec_mul(M - 1, p, A, n), A, n)
+
+# Elliptic curve factorization method
+# If n is prime, this method goes into an infinite loop
+def find_factor(n: int) -> int:
+ bound = max(int(sqrt(sqrt(sqrt(n)))), 256)
+
+ while True:
+ A = randint(0,n)
+ p = Point(x = randint(0,n), y = randint(0,n))
+ M = 2
+ while M < bound and not p.is_zero:
+ try:
+ p = ec_mul(M, p, A, n)
+ except FactorFound as ff:
+ #print("Found with A =", A, "M =", M, "and P =", p)
+ return ff.factor
+ M += 1
+
+N = int(argv[-1])
+f = find_factor(N)
+print(N, "=", f, "*", N//f)
diff --git a/code/python/naive.py b/code/python/naive.py
@@ -0,0 +1,18 @@
+#!/bin/env python
+
+from sys import argv
+from math import floor, sqrt
+
+def naive_factor(n: int) -> int:
+ for i in range(2,floor(sqrt(n))+1):
+ if n%i == 0:
+ return i
+ else:
+ return -1
+
+N = int(argv[-1])
+f = naive_factor(N)
+if f == -1:
+ print(N, "is prime")
+else:
+ print(N, "=", f, "*", N//f)
diff --git a/images/beer.jpg b/images/beer.jpg
Binary files differ.
diff --git a/images/clock.png b/images/clock.png
Binary files differ.
diff --git a/images/clock2.png b/images/clock2.png
Binary files differ.
diff --git a/images/demo.jpg b/images/demo.jpg
Binary files differ.
diff --git a/images/ec1.png b/images/ec1.png
Binary files differ.
diff --git a/images/ec2.png b/images/ec2.png
Binary files differ.
diff --git a/images/ec3.png b/images/ec3.png
Binary files differ.
diff --git a/images/euclid.png b/images/euclid.png
Binary files differ.
diff --git a/images/factorization.webp b/images/factorization.webp
Binary files differ.
diff --git a/images/number-line.svg b/images/number-line.svg
@@ -0,0 +1,262 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!-- Created with Inkscape (http://www.inkscape.org/) -->
+<svg
+ xmlns:dc="http://purl.org/dc/elements/1.1/"
+ xmlns:cc="http://web.resource.org/cc/"
+ xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
+ xmlns:svg="http://www.w3.org/2000/svg"
+ xmlns="http://www.w3.org/2000/svg"
+ xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
+ xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
+ width="400"
+ height="50"
+ id="svg2"
+ sodipodi:version="0.32"
+ inkscape:version="0.45.1"
+ version="1.0"
+ sodipodi:docbase="/Users/ezrakatz/Desktop"
+ sodipodi:docname="NumberLineIntegersAlt.svg"
+ inkscape:output_extension="org.inkscape.output.svg.inkscape"
+ inkscape:export-filename="/Users/ezrakatz/Documents/BasicMath/NumberLine.png"
+ inkscape:export-xdpi="180"
+ inkscape:export-ydpi="180">
+ <defs
+ id="defs4">
+ <marker
+ inkscape:stockid="StopL"
+ orient="auto"
+ refY="0.0"
+ refX="0.0"
+ id="StopL"
+ style="overflow:visible">
+ <path
+ id="path3272"
+ d="M 0.0,5.65 L 0.0,-5.65"
+ style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt"
+ transform="scale(0.8)" />
+ </marker>
+ <marker
+ inkscape:stockid="Dot_l"
+ orient="auto"
+ refY="0.0"
+ refX="0.0"
+ id="Dot_l"
+ style="overflow:visible">
+ <path
+ id="path3227"
+ d="M -2.5,-1.0 C -2.5,1.7600000 -4.7400000,4.0 -7.5,4.0 C -10.260000,4.0 -12.5,1.7600000 -12.5,-1.0 C -12.5,-3.7600000 -10.260000,-6.0 -7.5,-6.0 C -4.7400000,-6.0 -2.5,-3.7600000 -2.5,-1.0 z "
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none;marker-end:none"
+ transform="scale(0.8) translate(7.4, 1)" />
+ </marker>
+ <marker
+ inkscape:stockid="RazorWire"
+ id="RazorWire"
+ refX="0"
+ refY="0"
+ orient="auto">
+ style="overflow:visible">
+ <path
+ id="path3751"
+ transform="scale(0.8,0.8)"
+ style="fill:#808080;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:0.1pt"
+ d="M 0.022727273,-0.74009011 L 0.022727273,0.69740989 L -7.7585227,3.0099099 L 10.678977,3.0099099 L 3.4914773,0.69740989 L 3.4914773,-0.74009011 L 10.741477,-2.8963401 L -7.7272727,-2.8963401 L 0.022727273,-0.74009011 z " />
+</marker>
+ <marker
+ inkscape:stockid="DiamondL"
+ orient="auto"
+ refY="0.0"
+ refX="0.0"
+ id="DiamondL"
+ style="overflow:visible">
+ <path
+ id="path3661"
+ d="M 0,-7.0710768 L -7.0710894,0 L 0,7.0710589 L 7.0710462,0 L 0,-7.0710768 z "
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none"
+ transform="scale(0.8)" />
+ </marker>
+ <marker
+ inkscape:stockid="Dot_m"
+ orient="auto"
+ refY="0.0"
+ refX="0.0"
+ id="Dot_m"
+ style="overflow:visible">
+ <path
+ id="path3646"
+ d="M -2.5,-1.0 C -2.5,1.7600000 -4.7400000,4.0 -7.5,4.0 C -10.260000,4.0 -12.5,1.7600000 -12.5,-1.0 C -12.5,-3.7600000 -10.260000,-6.0 -7.5,-6.0 C -4.7400000,-6.0 -2.5,-3.7600000 -2.5,-1.0 z "
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none;marker-end:none"
+ transform="scale(0.4) translate(7.4, 1)" />
+ </marker>
+ <marker
+ inkscape:stockid="Arrow1Lend"
+ orient="auto"
+ refY="0"
+ refX="0"
+ id="Arrow1Lend"
+ style="overflow:visible">
+ <path
+ id="path3584"
+ d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z "
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
+ transform="matrix(-0.8,0,0,-0.8,-10,0)" />
+ </marker>
+ <marker
+ inkscape:stockid="TriangleInL"
+ orient="auto"
+ refY="0"
+ refX="0"
+ id="TriangleInL"
+ style="overflow:visible">
+ <path
+ id="path3670"
+ d="M 5.77,0 L -2.88,5 L -2.88,-5 L 5.77,0 z "
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
+ transform="scale(-0.8,-0.8)" />
+ </marker>
+ <marker
+ inkscape:stockid="Arrow1Mstart"
+ orient="auto"
+ refY="0"
+ refX="0"
+ id="Arrow1Mstart"
+ style="overflow:visible">
+ <path
+ id="path3587"
+ d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z "
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
+ transform="matrix(0.4,0,0,0.4,4,0)" />
+ </marker>
+ <marker
+ inkscape:stockid="Arrow1Lstart"
+ orient="auto"
+ refY="0"
+ refX="0"
+ id="Arrow1Lstart"
+ style="overflow:visible">
+ <path
+ id="path3581"
+ d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z "
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
+ transform="matrix(0.8,0,0,0.8,10,0)" />
+ </marker>
+ </defs>
+ <sodipodi:namedview
+ id="base"
+ pagecolor="#ffffff"
+ bordercolor="#666666"
+ borderopacity="1.0"
+ gridtolerance="10000"
+ guidetolerance="10"
+ objecttolerance="10"
+ inkscape:pageopacity="0.0"
+ inkscape:pageshadow="2"
+ inkscape:zoom="7.9195959"
+ inkscape:cx="52.143012"
+ inkscape:cy="11.483946"
+ inkscape:document-units="px"
+ inkscape:current-layer="g2179"
+ width="400px"
+ height="50px"
+ inkscape:window-width="1329"
+ inkscape:window-height="810"
+ inkscape:window-x="80"
+ inkscape:window-y="0"
+ showguides="true"
+ inkscape:guide-bbox="true" />
+ <metadata
+ id="metadata7">
+ <rdf:RDF>
+ <cc:Work
+ rdf:about="">
+ <dc:format>image/svg+xml</dc:format>
+ <dc:type
+ rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
+ </cc:Work>
+ </rdf:RDF>
+ </metadata>
+ <g
+ inkscape:label="Layer 1"
+ inkscape:groupmode="layer"
+ id="layer1">
+ <path
+ style="font-size:12px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
+ d="M 23.938099,40.28371 L 27.924427,40.28371 L 27.924427,42.130878 L 23.938099,42.130878 L 23.938099,40.28371 M 33.345325,40.271015 C 32.917912,40.27102 32.596298,40.410668 32.380482,40.68996 C 32.16889,40.96503 32.063095,41.379743 32.063099,41.934101 C 32.063095,42.488466 32.16889,42.905295 32.380482,43.184589 C 32.596298,43.459656 32.917912,43.597188 33.345325,43.597187 C 33.776961,43.597188 34.098575,43.459656 34.310169,43.184589 C 34.525984,42.905295 34.633894,42.488466 34.6339,41.934101 C 34.633894,41.379743 34.525984,40.96503 34.310169,40.68996 C 34.098575,40.410668 33.776961,40.27102 33.345325,40.271015 M 36.36681,35.719746 L 36.36681,37.471699 C 35.964784,37.281277 35.586041,37.141628 35.230579,37.052753 C 34.875104,36.959662 34.5281,36.913113 34.189564,36.913105 C 33.461694,36.913113 32.894638,37.116238 32.488392,37.52248 C 32.082138,37.924505 31.84516,38.5233 31.777454,39.318867 C 32.056748,39.111516 32.359319,38.957056 32.685169,38.855488 C 33.011011,38.7497 33.36648,38.696803 33.751575,38.696796 C 34.720645,38.696803 35.501406,38.980331 36.093861,39.547382 C 36.690532,40.114444 36.988872,40.85712 36.98888,41.77541 C 36.988872,42.791037 36.656678,43.605652 35.992298,44.219257 C 35.327903,44.828632 34.437117,45.13332 33.319935,45.13332 C 32.088486,45.13332 31.134223,44.718607 30.457142,43.889179 C 29.784289,43.055522 29.447864,41.874859 29.447865,40.347187 C 29.447864,38.781438 29.841418,37.55211 30.628529,36.659199 C 31.419867,35.762073 32.503199,35.313505 33.878529,35.313496 C 34.314395,35.313505 34.737572,35.347359 35.14806,35.415058 C 35.558535,35.482776 35.964784,35.584338 36.36681,35.719746 M 51.969349,40.28371 L 55.955677,40.28371 L 55.955677,42.130878 L 51.969349,42.130878 L 51.969349,40.28371 M 58.050404,35.472187 L 64.125111,35.472187 L 64.125111,37.268574 L 59.999134,37.268574 L 59.999134,38.734882 C 60.185328,38.684107 60.371526,38.646021 60.557728,38.620625 C 60.748153,38.591009 60.944931,38.576197 61.14806,38.576191 C 62.303328,38.576197 63.202578,38.866073 63.845814,39.44582 C 64.489035,40.021346 64.810649,40.825381 64.810658,41.857929 C 64.810649,42.88202 64.459413,43.68394 63.756947,44.263691 C 63.058698,44.843444 62.087508,45.13332 60.843372,45.13332 C 60.305934,45.13332 59.772731,45.080423 59.243763,44.974628 C 58.719021,44.873066 58.196398,44.716491 57.675892,44.504902 L 57.675892,42.581562 C 58.192166,42.877788 58.680935,43.099956 59.1422,43.248066 C 59.607692,43.396179 60.04568,43.470235 60.456165,43.470234 C 61.048609,43.470235 61.514103,43.326355 61.85265,43.038593 C 62.195418,42.746603 62.366804,42.353049 62.36681,41.857929 C 62.366804,41.358584 62.195418,40.96503 61.85265,40.677265 C 61.514103,40.389509 61.048609,40.245629 60.456165,40.245625 C 60.104925,40.245629 59.730414,40.292179 59.33263,40.385273 C 58.934841,40.474145 58.507433,40.613793 58.050404,40.804218 L 58.050404,35.472187 M 79.975208,40.28371 L 83.961536,40.28371 L 83.961536,42.130878 L 79.975208,42.130878 L 79.975208,40.28371 M 89.464954,37.484394 L 86.786243,41.451679 L 89.464954,41.451679 L 89.464954,37.484394 M 89.058704,35.472187 L 91.775501,35.472187 L 91.775501,41.451679 L 93.127552,41.451679 L 93.127552,43.222675 L 91.775501,43.222675 L 91.775501,44.949238 L 89.464954,44.949238 L 89.464954,43.222675 L 85.262806,43.222675 L 85.262806,41.127949 L 89.058704,35.472187 M 107.98107,40.28371 L 111.9674,40.28371 L 111.9674,42.130878 L 107.98107,42.130878 L 107.98107,40.28371 M 118.74035,39.839375 C 119.37934,40.004419 119.86387,40.292179 120.19396,40.702656 C 120.52826,41.10891 120.69542,41.627301 120.69542,42.257832 C 120.69542,43.197286 120.33571,43.912455 119.61632,44.403339 C 118.89691,44.889993 117.84744,45.13332 116.46788,45.13332 C 115.98123,45.13332 115.49246,45.093118 115.00158,45.012714 C 114.51492,44.936543 114.0325,44.820169 113.55431,44.663593 L 113.55431,42.778339 C 114.01134,43.006857 114.46414,43.180359 114.91271,43.298847 C 115.36551,43.413107 115.80984,43.470235 116.24572,43.470234 C 116.89317,43.470235 117.38829,43.358094 117.73107,43.133808 C 118.07807,42.909526 118.25157,42.587912 118.25158,42.168964 C 118.25157,41.737327 118.07384,41.411481 117.71837,41.191425 C 117.36713,40.967145 116.84662,40.855004 116.15685,40.855 L 115.17931,40.855 L 115.17931,39.280781 L 116.20763,39.280781 C 116.82123,39.280786 117.27826,39.185572 117.57872,38.995136 C 117.87917,38.800481 118.0294,38.506373 118.02941,38.112812 C 118.0294,37.748887 117.88341,37.467474 117.59142,37.268574 C 117.29942,37.069688 116.88683,36.970242 116.35363,36.970234 C 115.96007,36.970242 115.56228,37.014675 115.16027,37.103535 C 114.75825,37.19241 114.35834,37.323594 113.96056,37.497089 L 113.96056,35.70705 C 114.44298,35.571643 114.92117,35.470081 115.39513,35.402363 C 115.86909,35.334664 116.33458,35.30081 116.79161,35.3008 C 118.02305,35.30081 118.94346,35.503935 119.55285,35.910175 C 120.16644,36.312202 120.47325,36.919461 120.47326,37.731953 C 120.47325,38.286321 120.32725,38.741236 120.03527,39.096699 C 119.74327,39.447941 119.31163,39.6955 118.74035,39.839375 M 135.98693,40.28371 L 139.97326,40.28371 L 139.97326,42.130878 L 135.98693,42.130878 L 135.98693,40.28371 M 144.43566,43.152851 L 148.60607,43.152851 L 148.60607,44.949238 L 141.71886,44.949238 L 141.71886,43.152851 L 145.17833,40.099628 C 145.48725,39.820337 145.71576,39.547388 145.86388,39.280781 C 146.01199,39.014185 146.08604,38.737004 146.08605,38.449238 C 146.08604,38.004909 145.93582,37.647325 145.63536,37.376484 C 145.33914,37.105658 144.94347,36.970242 144.44835,36.970234 C 144.06749,36.970242 143.65066,37.052761 143.19786,37.217793 C 142.74506,37.378607 142.26053,37.619818 141.74425,37.941425 L 141.74425,35.859394 C 142.29438,35.677437 142.83816,35.539905 143.3756,35.446796 C 143.91303,35.349475 144.43989,35.30081 144.95617,35.3008 C 146.09027,35.30081 146.97048,35.550484 147.59679,36.049824 C 148.22732,36.549181 148.54258,37.245307 148.54259,38.138203 C 148.54258,38.654485 148.40928,39.136906 148.14269,39.585468 C 147.87608,40.029809 147.31537,40.626488 146.46056,41.375507 L 144.43566,43.152851 M 163.99279,40.28371 L 167.97911,40.28371 L 167.97911,42.130878 L 163.99279,42.130878 L 163.99279,40.28371 M 170.21984,43.260761 L 172.37804,43.260761 L 172.37804,37.135273 L 170.16271,37.592304 L 170.16271,35.929218 L 172.36535,35.472187 L 174.68859,35.472187 L 174.68859,43.260761 L 176.84679,43.260761 L 176.84679,44.949238 L 170.21984,44.949238 L 170.21984,43.260761 M 201.79308,40.201191 C 201.79307,39.016301 201.68093,38.182643 201.45665,37.700214 C 201.2366,37.213568 200.8642,36.970242 200.33947,36.970234 C 199.81472,36.970242 199.44021,37.213568 199.21593,37.700214 C 198.99164,38.182643 198.8795,39.016301 198.87951,40.201191 C 198.8795,41.398786 198.99164,42.243023 199.21593,42.733906 C 199.44021,43.224793 199.81472,43.470235 200.33947,43.470234 C 200.85997,43.470235 201.23236,43.224793 201.45665,42.733906 C 201.68093,42.243023 201.79307,41.398786 201.79308,40.201191 M 204.23693,40.220234 C 204.23692,41.790224 203.89838,43.002625 203.2213,43.857441 C 202.54421,44.708027 201.5836,45.13332 200.33947,45.13332 C 199.09109,45.13332 198.12836,44.708027 197.45128,43.857441 C 196.7742,43.002625 196.43566,41.790224 196.43566,40.220234 C 196.43566,38.646021 196.7742,37.43362 197.45128,36.583027 C 198.12836,35.728218 199.09109,35.30081 200.33947,35.3008 C 201.5836,35.30081 202.54421,35.728218 203.2213,36.583027 C 203.89838,37.43362 204.23692,38.646021 204.23693,40.220234 M 224.45421,43.260761 L 226.61242,43.260761 L 226.61242,37.135273 L 224.39708,37.592304 L 224.39708,35.929218 L 226.59972,35.472187 L 228.92296,35.472187 L 228.92296,43.260761 L 231.08117,43.260761 L 231.08117,44.949238 L 224.45421,44.949238 L 224.45421,43.260761 M 253.79308,43.152851 L 257.96349,43.152851 L 257.96349,44.949238 L 251.07628,44.949238 L 251.07628,43.152851 L 254.53576,40.099628 C 254.84467,39.820337 255.07319,39.547388 255.2213,39.280781 C 255.36941,39.014185 255.44346,38.737004 255.44347,38.449238 C 255.44346,38.004909 255.29324,37.647325 254.99279,37.376484 C 254.69656,37.105658 254.30089,36.970242 253.80577,36.970234 C 253.42491,36.970242 253.00808,37.052761 252.55529,37.217793 C 252.10248,37.378607 251.61795,37.619818 251.10167,37.941425 L 251.10167,35.859394 C 251.6518,35.677437 252.19558,35.539905 252.73302,35.446796 C 253.27045,35.349475 253.79731,35.30081 254.31359,35.3008 C 255.4477,35.30081 256.3279,35.550484 256.95421,36.049824 C 257.58474,36.549181 257.90001,37.245307 257.90001,38.138203 C 257.90001,38.654485 257.7667,39.136906 257.50011,39.585468 C 257.2335,40.029809 256.67279,40.626488 255.81798,41.375507 L 253.79308,43.152851 M 283.22081,39.839375 C 283.8598,40.004419 284.34434,40.292179 284.67443,40.702656 C 285.00873,41.10891 285.17588,41.627301 285.17589,42.257832 C 285.17588,43.197286 284.81618,43.912455 284.09679,44.403339 C 283.37738,44.889993 282.3279,45.13332 280.94835,45.13332 C 280.4617,45.13332 279.97293,45.093118 279.48204,45.012714 C 278.99539,44.936543 278.51297,44.820169 278.03478,44.663593 L 278.03478,42.778339 C 278.49181,43.006857 278.94461,43.180359 279.39318,43.298847 C 279.84597,43.413107 280.29031,43.470235 280.72618,43.470234 C 281.37364,43.470235 281.86876,43.358094 282.21154,43.133808 C 282.55854,42.909526 282.73204,42.587912 282.73204,42.168964 C 282.73204,41.737327 282.5543,41.411481 282.19884,41.191425 C 281.8476,40.967145 281.32709,40.855004 280.63732,40.855 L 279.65978,40.855 L 279.65978,39.280781 L 280.6881,39.280781 C 281.3017,39.280786 281.75873,39.185572 282.05919,38.995136 C 282.35964,38.800481 282.50987,38.506373 282.50988,38.112812 C 282.50987,37.748887 282.36387,37.467474 282.07189,37.268574 C 281.77989,37.069688 281.36729,36.970242 280.8341,36.970234 C 280.44054,36.970242 280.04275,37.014675 279.64074,37.103535 C 279.23872,37.19241 278.83881,37.323594 278.44103,37.497089 L 278.44103,35.70705 C 278.92345,35.571643 279.40164,35.470081 279.8756,35.402363 C 280.34955,35.334664 280.81505,35.30081 281.27208,35.3008 C 282.50352,35.30081 283.42393,35.503935 284.03331,35.910175 C 284.64691,36.312202 284.95372,36.919461 284.95372,37.731953 C 284.95372,38.286321 284.80772,38.741236 284.51574,39.096699 C 284.22374,39.447941 283.7921,39.6955 283.22081,39.839375 M 309.06847,37.484394 L 306.38976,41.451679 L 309.06847,41.451679 L 309.06847,37.484394 M 308.66222,35.472187 L 311.37902,35.472187 L 311.37902,41.451679 L 312.73107,41.451679 L 312.73107,43.222675 L 311.37902,43.222675 L 311.37902,44.949238 L 309.06847,44.949238 L 309.06847,43.222675 L 304.86632,43.222675 L 304.86632,41.127949 L 308.66222,35.472187 M 332.77697,35.472187 L 338.85167,35.472187 L 338.85167,37.268574 L 334.7257,37.268574 L 334.7257,38.734882 C 334.91189,38.684107 335.09809,38.646021 335.28429,38.620625 C 335.47472,38.591009 335.67149,38.576197 335.87462,38.576191 C 337.02989,38.576197 337.92914,38.866073 338.57238,39.44582 C 339.2156,40.021346 339.53721,40.825381 339.53722,41.857929 C 339.53721,42.88202 339.18598,43.68394 338.48351,44.263691 C 337.78526,44.843444 336.81407,45.13332 335.56993,45.13332 C 335.0325,45.13332 334.49929,45.080423 333.97033,44.974628 C 333.44558,44.873066 332.92296,44.716491 332.40245,44.504902 L 332.40245,42.581562 C 332.91873,42.877788 333.4075,43.099956 333.86876,43.248066 C 334.33425,43.396179 334.77224,43.470235 335.18273,43.470234 C 335.77517,43.470235 336.24067,43.326355 336.57921,43.038593 C 336.92198,42.746603 337.09337,42.353049 337.09337,41.857929 C 337.09337,41.358584 336.92198,40.96503 336.57921,40.677265 C 336.24067,40.389509 335.77517,40.245629 335.18273,40.245625 C 334.83149,40.245629 334.45698,40.292179 334.05919,40.385273 C 333.6614,40.474145 333.234,40.613793 332.77697,40.804218 L 332.77697,35.472187 M 363.22033,40.271015 C 362.79291,40.27102 362.4713,40.410668 362.25548,40.68996 C 362.04389,40.96503 361.9381,41.379743 361.9381,41.934101 C 361.9381,42.488466 362.04389,42.905295 362.25548,43.184589 C 362.4713,43.459656 362.79291,43.597188 363.22033,43.597187 C 363.65196,43.597188 363.97358,43.459656 364.18517,43.184589 C 364.40098,42.905295 364.50889,42.488466 364.5089,41.934101 C 364.50889,41.379743 364.40098,40.96503 364.18517,40.68996 C 363.97358,40.410668 363.65196,40.27102 363.22033,40.271015 M 366.24181,35.719746 L 366.24181,37.471699 C 365.83978,37.281277 365.46104,37.141628 365.10558,37.052753 C 364.7501,36.959662 364.4031,36.913113 364.06456,36.913105 C 363.33669,36.913113 362.76964,37.116238 362.36339,37.52248 C 361.95714,37.924505 361.72016,38.5233 361.65245,39.318867 C 361.93175,39.111516 362.23432,38.957056 362.56017,38.855488 C 362.88601,38.7497 363.24148,38.696803 363.62658,38.696796 C 364.59564,38.696803 365.37641,38.980331 365.96886,39.547382 C 366.56553,40.114444 366.86387,40.85712 366.86388,41.77541 C 366.86387,42.791037 366.53168,43.605652 365.8673,44.219257 C 365.2029,44.828632 364.31212,45.13332 363.19493,45.13332 C 361.96349,45.13332 361.00922,44.718607 360.33214,43.889179 C 359.65929,43.055522 359.32286,41.874859 359.32286,40.347187 C 359.32286,38.781438 359.71642,37.55211 360.50353,36.659199 C 361.29487,35.762073 362.3782,35.313505 363.75353,35.313496 C 364.1894,35.313505 364.61257,35.347359 365.02306,35.415058 C 365.43353,35.482776 365.83978,35.584338 366.24181,35.719746"
+ id="text2185" />
+ <g
+ id="g2179">
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.99763459px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
+ d="M 2,25.25 L 2,26.25 L 398,26.25 L 398,25.25 L 2,25.25 z "
+ id="path2189"
+ sodipodi:nodetypes="ccccc" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 17.6875,20.75 L 15.84375,21.28125 L 1.875,25.28125 L 0.1875,25.75 L 1.875,26.25 L 15.84375,30.21875 L 17.6875,30.75 L 16.3125,29.40625 L 12.65625,25.75 L 16.3125,22.125 L 17.6875,20.75 z "
+ id="path2185"
+ sodipodi:nodetypes="ccccccccccc" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 32.71875,21.25 L 32.71875,30.28125 L 33.71875,30.28125 L 33.71875,21.25 L 32.71875,21.25 z "
+ id="path2187" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 60.21875,21.25 L 60.21875,30.28125 L 61.21875,30.28125 L 61.21875,21.25 L 60.21875,21.25 z "
+ id="path2190" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 88.4375,21.25 L 88.4375,30.28125 L 89.4375,30.28125 L 89.4375,21.25 L 88.4375,21.25 z "
+ id="path2192" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 116.65625,21.25 L 116.65625,30.28125 L 117.65625,30.28125 L 117.65625,21.25 L 116.65625,21.25 z "
+ id="path2194" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 144.3125,21.25 L 144.3125,30.28125 L 145.3125,30.28125 L 145.3125,21.25 L 144.3125,21.25 z "
+ id="path2196" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 172.34375,21.25 L 172.34375,30.28125 L 173.34375,30.28125 L 173.34375,21.25 L 172.34375,21.25 z "
+ id="path2198" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 227,21.25 L 227,30.28125 L 228,30.28125 L 228,21.25 L 227,21.25 z "
+ id="path2200" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 253.78125,21.25 L 253.78125,30.28125 L 254.78125,30.28125 L 254.78125,21.25 L 253.78125,21.25 z "
+ id="path2202" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 280.9375,21.25 L 280.9375,30.28125 L 281.9375,30.28125 L 281.9375,21.25 L 280.9375,21.25 z "
+ id="path2204" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 308.4375,21.25 L 308.4375,30.28125 L 309.4375,30.28125 L 309.4375,21.25 L 308.4375,21.25 z "
+ id="path2206" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 334.84375,21.25 L 334.84375,30.28125 L 335.84375,30.28125 L 335.84375,21.25 L 334.84375,21.25 z "
+ id="path2208" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 362.34375,21.25 L 362.34375,30.28125 L 363.34375,30.28125 L 363.34375,21.25 L 362.34375,21.25 z "
+ id="path2210" />
+ <path
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
+ d="M 382.3125,20.75 L 383.6875,22.125 L 387.34375,25.75 L 383.6875,29.40625 L 382.3125,30.75 L 384.15625,30.21875 L 398.125,26.25 L 399.8125,25.75 L 398.125,25.28125 L 384.15625,21.28125 L 382.3125,20.75 z "
+ id="path2212"
+ sodipodi:nodetypes="ccccccccccc" />
+ </g>
+ <path
+ sodipodi:type="arc"
+ style="fill:#000000;fill-opacity:1;stroke:none;stroke-width:5.99987173;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
+ id="path4331"
+ sodipodi:cx="189.10715"
+ sodipodi:cy="6.2500005"
+ sodipodi:rx="0.17857143"
+ sodipodi:ry="0.17857143"
+ d="M 189.28572 6.2500005 A 0.17857143 0.17857143 0 1 1 188.92858,6.2500005 A 0.17857143 0.17857143 0 1 1 189.28572 6.2500005 z"
+ transform="matrix(14,0,0,14,-2447.4708,-61.85223)" />
+ </g>
+</svg>
diff --git a/images/numbers.jpg b/images/numbers.jpg
Binary files differ.
diff --git a/images/questions.png b/images/questions.png
Binary files differ.
diff --git a/images/sum-1a.png b/images/sum-1a.png
Binary files differ.
diff --git a/images/sum-1b.png b/images/sum-1b.png
Binary files differ.
diff --git a/images/sum-1c.png b/images/sum-1c.png
Binary files differ.
diff --git a/images/sum-2a.png b/images/sum-2a.png
Binary files differ.
diff --git a/images/sum-2b.png b/images/sum-2b.png
Binary files differ.
diff --git a/images/sum-2c.png b/images/sum-2c.png
Binary files differ.
diff --git a/images/sum-3a.png b/images/sum-3a.png
Binary files differ.
diff --git a/images/sum-3b.png b/images/sum-3b.png
Binary files differ.
diff --git a/images/sum-3c.png b/images/sum-3c.png
Binary files differ.
diff --git a/images/sum-4a.png b/images/sum-4a.png
Binary files differ.
diff --git a/images/sum-4b.png b/images/sum-4b.png
Binary files differ.
diff --git a/images/sum-4c.png b/images/sum-4c.png
Binary files differ.
diff --git a/index.html b/index.html
@@ -0,0 +1,622 @@
+<!doctype html>
+<html lang="en">
+<head>
+ <title>Elliptic Curves and the ECM algorithm</title>
+ <meta name="viewport" content="width=device-width" />
+
+ <!-- Import MathJax script -->
+ <script id="MathJax-script" async src=
+ "https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"
+ ></script>
+
+ <!-- Import highlight.js script and style sheet -->
+ <script id="highlight.js" src="
+ https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.9.0/highlight.min.js"
+ ></script>
+ <link rel="stylesheet" href="
+ https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.9.0/styles/vs.css"
+ >
+
+ <!-- Custom style -->
+ <style>
+ html { height: 100vh; width: 98vw; margin: auto; font-family: sans-serif; }
+ h1 { font-size: 3.5vw; background-color: #eeeeee; margin: 0; }
+ body { font-size: 2.2vw; height: 100%; width: 100%; }
+ a, a:visited { color: #0f2899; text-decoration: none; }
+ a:hover { text-decoration: underline; }
+ figcaption { text-align: center; font-size: 1.5vw; }
+ em { font-style: normal; color: blue; }
+
+ .slide { outline: none; height: 100vh; width: 100%; }
+ .slide {
+ display: flex;
+ flex-direction: column;
+ justify-content: space-between;
+ }
+ .slide ul { margin-left: 1.5vw; }
+ .slide ol { margin-left: 1.5vw; }
+ .slide p { margin-left: 1.5vw; }
+
+ .slide.titlepage p, a { text-align: center; }
+ .slide.titlepage span.title { font-size: 3.6vw; font-weight: bold; }
+ .slide.titlepage span.author { }
+
+ .slide.ecsum img { width: 50%; display: block; margin: auto; }
+
+ .slide div.centertext { text-align: center; margin: auto; width: 60%; }
+
+ .columns {
+ display: flex;
+ flex-direction: row;
+ justify-content: space-between;
+ align-items: center;
+ }
+
+ .footer { font-size: 1.8vw; background-color: #eeeeee; }
+ .footer table { width: 100%; }
+ .footer-title { font-weight: bold; }
+ .footer-link { text-align: right; }
+ </style>
+ <meta charset="utf-8">
+</head>
+
+<body>
+
+<div class="slide titlepage" tabindex="-1"
+style="background-image: url('images/sum-2c.png');
+background-position: center;
+background-repeat: no-repeat;
+background-size: 70%;
+background-color: rgba(255, 255, 255, 0.85);
+background-blend-mode: overlay;">
+
+<p></p>
+
+<p><span class="title">Elliptic curves and the ECM algorithm<span></p>
+<p><span class="author">Sebastiano Tronto<span></p>
+<p><span class="event">ALTEN Scientific Software Evening<span></p>
+
+</div>
+
+<div class="slide titlepage" tabindex="-1"
+style="background-image: url('images/numbers.jpg');
+background-position: center;
+background-repeat: no-repeat;
+background-size: 100%;
+background-color: rgba(255, 255, 255, 0.75);
+background-blend-mode: overlay;">
+<p></p>
+<p><span class="title">Part I: Numbers<span></p>
+<p></p>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>The integers</h1>
+
+<img alt="The number line" src="images/number-line.svg"
+ style="width: 70%; margin-left: 15%; margin-right: 15%;"/>
+
+<ul>
+<li>Operations: sum \(+\), difference \(-\) and multiplication \(\times\)</li>
+<li>Various properties: associativity, commutativity, etc...</li>
+<li>What about division (without remainder)?<br>
+If <tt>\(\frac ab\)</tt> is an integer we say that
+<tt>\(a\)</tt><em> divides </em><tt>\(b\)</tt> (in code:
+<tt>a % b == 0</tt>)</li>
+</ul>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>The integers modulo N</h1>
+
+<div class="columns">
+
+<ul>
+<!-- li>Integers modulo <tt>N</tt>: the possible remainders of
+division by <tt>N</tt><br-->
+<li>Two numbers are the same if they give the <em>same remainder</em>
+when divided by <tt>N</tt></li>
+<li>Think of <tt>int</tt>, but with <tt>% N</tt>
+after every operation</li>
+<li>Examples with \(N=12\):
+\[9+5\equiv 14\equiv 2\pmod{12}\]
+\[7-11\equiv-4\equiv 8\pmod{12}\]
+\[3\times 4\equiv 12\equiv 0\pmod{12}\]
+</li>
+</ul>
+
+<img alt="The number clock" src="images/clock.png"
+ style="width: 35%;"/>
+
+</div>
+
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>The integers modulo N - Division</h1>
+
+<p style="text-align: center;"><strong>What about division?</strong></p>
+
+<ul>
+<li>
+Sometimes it works
+\[
+\frac 37\equiv 9 \pmod{12} \qquad
+\text{because} \qquad 9\times 7 \equiv 63 \equiv 3 \pmod{12}
+\]
+</li>
+
+<li>
+Sometimes it does not
+\[
+\frac 32\equiv \; ? \pmod{4} \qquad {\color{red}\text{Impossible!}}
+\]
+</li>
+</ul>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Integers modulo N - Division</h1>
+
+<ul>
+<li>
+Sometimes it's... weird?
+\[
+\frac 62 \equiv \; ? \pmod{8} \quad
+\begin{array}{l}
+\rightarrow {\color{red}3} \times 2 \equiv 6\pmod{8}\\
+\rightarrow {\color{red}7} \times 2 \equiv 14 \equiv 6 \pmod{8}
+\end{array}
+\]
+</li>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Integers modulo N - Division</h1>
+<div class="columns">
+<ul>
+<li>Can divide by \(a\) when \[\operatorname{GCD}(a, N)=1\]</li>
+<li>With the
+<a href="https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm">
+extended GCD algorithm</a> find \(x\) and \(y\) such that
+\[
+ax+Ny=1
+\]
+<li>
+This means \(\frac{1}{a}\equiv x\pmod{N}\)
+</li>
+</ul>
+<pre><code class="language-python"
+style="border: 0.2vw solid; font-size: 2.2vw;">
+def extended_gcd(a, b):
+ if b == 0:
+ return a, 1, 0
+ g, x, y = extended_gcd(b, a % b)
+ return g, y, x - y*(a // b)
+</code></pre>
+</div>
+<p style="text-align: center;">
+Division always works if \(N\) is a <em>prime</em> number!</p>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Modular arithmetic - recap</h1>
+<div class="columns">
+<ul>
+<li>Integers modulo \(N\) are (almost) like numbers</li>
+<li>Normal operations like \(+\), \(-\) and \(\times\) work</li>
+<li>Division sometimes works, sometimes not</li>
+<li>Division always works if \(N\) is <em>prime</em></li>
+</ul>
+<img alt="The number line" src="images/clock2.png" style="width: 40%;"/>
+</div>
+</div>
+
+<div class="slide titlepage" tabindex="-1"
+style="background-image: url('images/sum-2c.png');
+background-position: center;
+background-repeat: no-repeat;
+background-size: 70%;
+background-color: rgba(255, 255, 255, 0.85);
+background-blend-mode: overlay;">
+<p></p>
+<p><span class="title">Part II: Elliptic Curves<span></p>
+<p></p>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Elliptic curves</h1>
+
+<div class="columns">
+
+<p>
+An <em>elliptic curve</em> is a curve with equation
+\[ y^2 = x^3+Ax+B \]
+Where \(A\) and \(B\) are numbers with \[4A^3+27B^2\neq 0\]
+</p>
+
+<figure style="width: 45%;">
+<figcaption>\(y^2=x^3-x+1\) <br> \((A=-1, B=1\))</figcaption>
+<img alt="An elliptic curve" src="images/ec1.png" style="width: 100%;"/>
+</figure>
+
+</div>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Elliptic curves</h1>
+
+<div class="columns">
+
+<figure style="width: 45%;">
+<figcaption>\(y^2=x^3+13x-34\) <br> \((A=13, B=-34\))</figcaption>
+<img alt="An elliptic curve" src="images/ec3.png" style="width: 100%;"/>
+</figure>
+
+<figure style="width: 45%;">
+<figcaption>\(y^2=x^3-x\) <br> \((A=-1, B=0\))</figcaption>
+<img alt="An elliptic curve" src="images/ec2.png" style="width: 100%;"/>
+</figure>
+
+</div>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Elliptic curves</h1>
+
+<div class="columns">
+<ul>
+<li>There is a "sum" operation for points of a curve
+(NOT the sum of coordinates)</li>
+<li>To make things work out nicely, we pretend the curve has
+a <em>point at infinity</em> that acts as \(0\):
+\[P+0=0\qquad 0+P=0\qquad P-P=0\]</li>
+</ul>
+
+<img alt="Elliptic curve sum" src="images/sum-2c.png" style="width: 80%;"/>
+
+</div>
+</div>
+
+<div class="slide ecsum" tabindex="-1">
+<h1>Elliptic curves - sum operation - example 1</h2>
+<img alt="Elliptic curve sum" src="images/sum-2a.png"/>
+</div>
+<div class="slide ecsum" tabindex="-1">
+<h1>Elliptic curves - sum operation - example 1</h2>
+<img alt="Elliptic curve sum" src="images/sum-2b.png"/>
+</div>
+<div class="slide ecsum" tabindex="-1">
+<h1>Elliptic curves - sum operation - example 1</h2>
+<img alt="Elliptic curve sum" src="images/sum-2c.png"/>
+</div>
+
+<div class="slide ecsum" tabindex="-1">
+<h1>Elliptic curves - sum operation - example 2</h2>
+<img alt="Elliptic curve sum" src="images/sum-3a.png"/>
+</div>
+<div class="slide ecsum" tabindex="-1">
+<h1>Elliptic curves - sum operation - example 2</h2>
+<img alt="Elliptic curve sum" src="images/sum-3b.png"/>
+</div>
+<div class="slide ecsum" tabindex="-1">
+<h1>Elliptic curves - sum operation - example 2</h2>
+<img alt="Elliptic curve sum" src="images/sum-3c.png"/>
+</div>
+
+<div class="slide ecsum" tabindex="-1">
+<h1>Elliptic curves - sum operation - example 3</h2>
+<img alt="Elliptic curve sum" src="images/sum-4a.png"/>
+</div>
+<div class="slide ecsum" tabindex="-1">
+<h1>Elliptic curves - sum operation - example 3</h2>
+<img alt="Elliptic curve sum" src="images/sum-4b.png"/>
+</div>
+<div class="slide ecsum" tabindex="-1">
+<h1>Elliptic curves - sum operation - example 3</h2>
+<img alt="Elliptic curve sum" src="images/sum-4c.png"/>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Elliptic curves - sum operation - code</h1>
+
+<div class="columns">
+<pre><code class="language-python"
+style="font-size: 2.8vh;">
+# Computes p+q on the elliptic curve y^2 = x^3 + Ax + B
+def ec_sum(p: Point, q: Point, A: double) -> Point:
+ if p.is_zero:
+ return q
+ if q.is_zero:
+ return p
+ if p.x == q.x and p.y == -q.y:
+ return Point(is_zero = True)
+
+ if p.x != q.x:
+ k = (p.y - q.y) / (p.x - q.x)
+ else:
+ k = (3 * p.x**2 + A) / (p.y + q.y)
+
+ new_x = k**2 - p.x - q.x
+ new_y = k * (p.x - new_x) - p.y
+ return Point(x = new_x, y = new_y)
+</code></pre>
+
+<pre><code class="language-python"
+style="border: 0.2vw solid; font-size: 2.8vh;">
+@dataclass
+class Point:
+ x: int = 0
+ y: int = 0
+ is_zero: bool = False
+</code></pre>
+
+</div>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Elliptic curves - recap</h1>
+<div class="columns">
+<ul>
+<li>Curves of equation \(y^2=x^3+Ax+B\)</li>
+<li>Can "sum" points of the same curve</li>
+<li>Nice properties: associativity, commutativity...</li>
+<li>The sum operation can be easily implemented</li>
+</ul>
+<img alt="The number line" src="images/sum-2c.png" style="width: 40%;"/>
+</div>
+</div>
+
+<div class="slide titlepage" tabindex="-1"
+style="background-image: url('images/factorization.webp');
+background-position: center;
+background-repeat: no-repeat;
+background-size: 50%;
+background-color: rgba(255, 255, 255, 0.90);
+background-blend-mode: overlay;">
+<p></p>
+<p><span class="title">Part III: The Elliptic Curve Factorization Method<span></p>
+<p></p>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Integer factorization</h1>
+<p style="text-align: center;"><strong>
+Every positive integer can be written as the product of prime numbers
+</strong></p>
+<div class="columns">
+<ul>
+<li>Example: \(69420 = 2\times 2\times 3\times 5\times 13\times 89\)</li>
+<li>Computationally hard</li>
+<li>Important for cryptography!</li>
+</ul>
+<img src="images/euclid.png" style="height: 60vh;"/>
+</div>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Integer factorization - high-level procedure</h1>
+
+<div class="columns">
+<pre><code class="language-python"
+style="border: 0.2vw solid; font-size: 1.4vw;">
+# Returns the list of prime factors of n
+def factorize(n: int) -> list:
+ if n == 1:
+ return []
+
+ if is_prime(n):
+ return [n]
+
+ f = find_factor(n)
+
+ return factorize(n) + factorize(n//f)
+</code></pre>
+
+<ul>
+<li><tt>is_prime(n)</tt> can be implemented
+efficiently
+(<a href="https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test">Miller-Rabin</a>,
+<a href="https://en.wikipedia.org/wiki/AKS_primality_test">AKS</a>
+or <a href="https://en.wikipedia.org/wiki/Elliptic_curve_primality">ECPP</a>)
+</li>
+<li>Naive implementation of <tt>find_factor(n):</tt>
+<pre><code class="language-python" style="font-size: 2vw;">
+def find_factor(n: int) -> int:
+ for i in range(2,floor(sqrt(n))+1):
+ if n % i == 0:
+ return i
+</code></pre>
+</li>
+</ul>
+
+</div>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Find Factor - Elliptic Curve Method</h1>
+<div>
+<p><strong>To find a factor of \(n\):</strong><p>
+<ol>
+<li>Take a random Elliptic Curve \(E\)
+and a random point \(P\) of \(E\)</li>
+<li>Take a <em>suitable number \(m\)</em></li>
+<li>Try to compute \(m\cdot P = P+P+\cdots+P\quad\) (\(m\) times)
+with <em>coordinates modulo \(n\)</em></li>
+<li>If you attempt an <em>impossible division</em> by some number \(d\),
+<em>return \(\operatorname{GCD}(n,d)\)</em></li>
+<li>Go back to 1.</li>
+</ol>
+</div>
+</div>
+
+<div class="slide" tabindex="-1" style="font-size: 2vw;">
+<h1>Find Factor - Elliptic Curve Method - Example</h1>
+<ul>
+<li>Take \(n = 91\)</li>
+<li>Take \(E: y^2 = x^3 + 51x -371\) and \(P = (11, 39)\) and \(M = 2\)</li>
+<li>
+Try to compute \(M\cdot P=P+P\pmod n\):
+\[ k = \frac{3x_p^2+51}{2y_p} \pmod n\]
+Is \(2y_p=78\) invertible modulo \(91\)?
+\[ \operatorname{GCD}(78, 91) = 13 \neq 1 \quad \implies \quad \text{NO!} \]
+</li>
+<li>Found factor: \(13\)</li>
+</div>
+
+<div class="slide titlepage" tabindex="-1"
+style="background-image: url('images/demo.jpg');
+background-position: center;
+background-repeat: no-repeat;
+background-size: 100%;
+background-color: rgba(255, 255, 255, 0.60);
+background-blend-mode: overlay;">
+<p></p>
+<p><span class="title">Demo time!<span></p>
+<a href="https://git.tronto.net/ecm">git.tronto.net/ecm</a>
+<p></p>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Elliptic Curve Method - Questions</h1>
+<div class="centertext">
+<p><strong>
+Q: Aren't we just computing the \(\operatorname{GCD}\) with random numbers?
+</strong></p>
+<p>
+A: Yes, but Elliptic Curve operations produce "good candidates"
+for these random numbers.
+</p>
+</div>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Elliptic Curve Method - Questions</h1>
+<div class="centertext">
+<p><strong>Q: Can we do the same without elliptic curves?</strong></p>
+<p>A: Yes, with
+<a href="https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm">
+Pollard's \(p-1\) Algorithm</a>, but ECM is faster.</p>
+</div>
+</div>
+
+<div class="slide" tabindex="-1">
+<h1>Elliptic Curve Method - Questions</h1>
+<div class="centertext">
+<p><strong>
+Q: Are there objects that are more complicated than Elliptic Curves
+and can make the method even faster?
+</strong></p>
+<p>A: Yes, there are higher-dimensional
+<a href="https://en.wikipedia.org/wiki/Abelian_variety">
+Abelian Varieties</a> and other
+<a href="https://en.wikipedia.org/wiki/Algebraic_group">
+Algebraic Groups</a>, but they are much harder (if not impossible)
+to implement efficiently.</p>
+</div>
+</div>
+
+<div class="slide titlepage" tabindex="-1"
+style="background-image: url('images/questions.png');
+background-position: center;
+background-repeat: no-repeat;
+background-size: 60%;
+background-color: rgba(255, 255, 255, 0.85);
+background-blend-mode: overlay;">
+<p></p>
+<p><span class="title">More questions?<span></p>
+<p></p>
+</div>
+
+<div class="slide titlepage" tabindex="-1"
+style="background-image: url('images/beer.jpg');
+background-position: center;
+background-repeat: no-repeat;
+background-size: 80%;
+background-color: rgba(255, 255, 255, 0.65);
+background-blend-mode: overlay;">
+<p></p>
+<p><span class="title">Drinks!<span></p>
+<p></p>
+</div>
+
+<script>
+ // The list of all slides of the presentation.
+ const slides = document.querySelectorAll(".slide");
+
+ // Navigation keys.
+ const keysNext = ["ArrowRight", "ArrowDown", " "];
+ const keysPrev = ["ArrowLeft", "ArrowUp"];
+
+ // Function to move to a given slide.
+ // This also focuses the slide, so any key press will be
+ // handled by the correct slide's event handler.
+ function goto(slide) {
+ slide.focus();
+ slide.scrollIntoView({
+ behavior: "instant",
+ block: "start"
+ });
+ }
+
+ // Handle key press events.
+ 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]);
+ }
+ }
+
+ // Handle click or tap events.
+ // Tapping on the right half of the screen scrolls forwards,
+ // tapping on the left half scrolls backwards.
+ 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]);
+ }
+ }
+
+ // 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 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;
+ }
+
+ // Add slide footers and event handlers.
+ for (let i = 0; i < slides.length; i++) {
+ slides[i].innerHTML += slideFooter();
+ slides[i].addEventListener("keydown", e => onkeydown(i, e));
+ slides[i].addEventListener("click", e => onclick(i, e));
+ }
+
+ // Focus and scroll into view the first slide.
+ goto(slides[0]);
+
+ // Call highlight.js
+ hljs.highlightAll();
+</script>
+
+</body>
+</html>
