aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--README.md63
-rw-r--r--code/cpp/a.outbin0 -> 43664 bytes
-rw-r--r--code/cpp/bigint.h266
-rw-r--r--code/cpp/ecm.cpp91
-rw-r--r--code/cpp/naive.cpp23
-rw-r--r--code/cpp/zmodn.h79
-rwxr-xr-xcode/python/ecm.py75
-rwxr-xr-xcode/python/naive.py18
-rw-r--r--images/beer.jpgbin0 -> 508889 bytes
-rw-r--r--images/clock.pngbin0 -> 14805 bytes
-rw-r--r--images/clock2.pngbin0 -> 30188 bytes
-rw-r--r--images/demo.jpgbin0 -> 24404 bytes
-rw-r--r--images/ec1.pngbin0 -> 17744 bytes
-rw-r--r--images/ec2.pngbin0 -> 18917 bytes
-rw-r--r--images/ec3.pngbin0 -> 14559 bytes
-rw-r--r--images/euclid.pngbin0 -> 1054492 bytes
-rw-r--r--images/factorization.webpbin0 -> 14496 bytes
-rw-r--r--images/number-line.svg262
-rw-r--r--images/numbers.jpgbin0 -> 164839 bytes
-rw-r--r--images/questions.pngbin0 -> 125274 bytes
-rw-r--r--images/sum-1a.pngbin0 -> 18339 bytes
-rw-r--r--images/sum-1b.pngbin0 -> 19456 bytes
-rw-r--r--images/sum-1c.pngbin0 -> 20134 bytes
-rw-r--r--images/sum-2a.pngbin0 -> 18120 bytes
-rw-r--r--images/sum-2b.pngbin0 -> 24334 bytes
-rw-r--r--images/sum-2c.pngbin0 -> 25172 bytes
-rw-r--r--images/sum-3a.pngbin0 -> 17859 bytes
-rw-r--r--images/sum-3b.pngbin0 -> 24262 bytes
-rw-r--r--images/sum-3c.pngbin0 -> 25047 bytes
-rw-r--r--images/sum-4a.pngbin0 -> 17644 bytes
-rw-r--r--images/sum-4b.pngbin0 -> 21832 bytes
-rw-r--r--images/sum-4c.pngbin0 -> 22574 bytes
-rw-r--r--index.html622
33 files changed, 1499 insertions, 0 deletions
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..75f495a
--- /dev/null
+++ b/README.md
@@ -0,0 +1,63 @@
1# Elliptic curve factorization method
2
3Slides and code for the a presentation about
4[Lenstra's elliptic-curve factorization](https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization).
5
6See also [this blog post](https://sebastiano.tronto.net/blog/2025-02-27-ecm).
7
8## Abstract
9
10Elliptic curves are mathematical objects that have both a geometric and an
11arithmetic side. They turn out to be useful for real-world applications
12because they sit in a sweet spot: they are complicated enough to have
13interesting and useful arithmetic properties, but simple enough to be
14implemented in software in an efficient way. For example, they are used in
15cryptographic schemes, such as the Elliptic-curve Diffie-Hellman scheme,
16to obtain greater security with smaller keys.
17
18After introducing elliptic curves and modular arithmetic, we will take a
19look at the elliptic curve factorization method (ECM), one of the most
20efficient method to find the prime factors of an integer number. We
21will see in practice how much faster this method is compared to a naive
22algorithm, and we'll see that the implementation of this method is not
23that hard at all.
24
25## Slides
26
27The slides are a single html file, `index.html`. They rely on a couple
28of external JavaScript libraries. They are also hosted
29[here](https://sebastiano.tronto.net/talks/ecm).
30
31## Code
32
33The folder `code/python` contains two files:
34
35* `ecm.py`: an implementation of the ECM algorithm.
36* `naive.py`: an implementation of the simple O(√n) algorithm for finding
37 a factor of a number, for comparison.
38
39To use any of the two, pass the number to factor as a command-line argument,
40for example:
41
42```
43$ ./ecm.py 255000007030000033
44255000007030000033 = 510000011 * 500000003
45```
46
47Some benchmarks (note: the ECM is randomized, the time can vary a lot):
48
49```
50$ time ./ecm.py 255000007030000033
51255000007030000033 = 510000011 * 500000003
52 0m01.45s real 0m01.43s user 0m00.01s system
53$ time ./naive.py 255000007030000033
54255000007030000033 = 500000003 * 510000011
55 0m26.62s real 0m26.50s user 0m00.01s system
56```
57
58### C++ code (experimental)
59
60The folder `code/cpp` contains an experimental implementation of the ECM
61algorithm in C++. It works, but it is very slow: it requires suppport
62for compile-time big integers, which I implement in an inefficient way. I
63may optimize this code in the future.
diff --git a/code/cpp/a.out b/code/cpp/a.out
new file mode 100644
index 0000000..b52f011
--- /dev/null
+++ b/code/cpp/a.out
Binary files differ
diff --git a/code/cpp/bigint.h b/code/cpp/bigint.h
new file mode 100644
index 0000000..096ed9c
--- /dev/null
+++ b/code/cpp/bigint.h
@@ -0,0 +1,266 @@
1#ifndef BIGUNSIGNED_H
2#define BIGUNSIGNED_H
3
4#include <cstdint>
5#include <iostream>
6#include <random>
7#include <string_view>
8
9constexpr uint64_t abs64(int64_t);
10constexpr uint64_t pow10(uint64_t);
11
12// Big integer class for numbers of at most N decimal digits.
13// The number E is used to tune the size of each digit, mostly for
14// testing purposes.
15
16template<uint64_t N = 50, uint64_t E = 9>
17requires (E < 10)
18class BigInt {
19public:
20 // The member variables sign and digits are declared public so that
21 // BigInt becomes a structural type and can be used in templates.
22
23 static constexpr uint64_t M = pow10(E);
24 static constexpr uint64_t D = (N / E) + 1;
25
26 bool sign;
27 uint64_t digits[D];
28
29 constexpr BigInt() : sign{true} {
30 std::fill(digits, digits+D, 0);
31 }
32
33 constexpr BigInt(int64_t n) : sign{n >= 0} {
34 std::fill(digits, digits+D, 0);
35 digits[0] = abs64(n);
36 carryover();
37 }
38
39 constexpr BigInt(const std::string_view s) : sign{true} {
40 std::fill(digits, digits+D, 0);
41 if (s.size() == 0)
42 return;
43 for (int i = s.size()-1, j = 0; i >= 0; i--, j++) {
44 if (s[i] == '\'')
45 continue;
46 if (i == 0 && s[i] == '-') {
47 sign = false;
48 break;
49 }
50 digits[j/E] += (pow10(j % E))
51 * static_cast<uint64_t>(s[i] - '0');
52 }
53 }
54
55 constexpr auto operator<=>(const BigInt& other) const {
56 if (sign != other.sign)
57 return sign <=> other.sign;
58
59 for (int i = D-1; i >= 0; i--)
60 if (digits[i] != other.digits[i])
61 return sign ?
62 digits[i] <=> other.digits[i] :
63 other.digits[i] <=> digits[i];
64
65 return 0 <=> 0;
66 }
67
68 constexpr bool operator==(const BigInt& other) const = default;
69
70 constexpr BigInt abs() const {
71 BigInt ret = *this;
72 ret.sign = true;
73 return ret;
74 }
75
76 constexpr BigInt operator-() const {
77 if (*this == 0)
78 return 0;
79 BigInt ret = *this;
80 ret.sign = !ret.sign;
81 return ret;
82 }
83
84 constexpr BigInt operator+(const BigInt& z) const {
85 if (sign && z.sign)
86 return positive_sum(*this, z);
87 else if (sign && !z.sign)
88 return positive_diff(*this, -z);
89 else if (!sign && z.sign)
90 return positive_diff(z, -*this);
91 else
92 return -positive_sum(-*this, -z);
93 }
94
95 constexpr BigInt operator-(const BigInt& z) const {
96 return *this + (-z);
97 }
98
99 constexpr BigInt operator*(const BigInt& z) const {
100 BigInt ret;
101 ret.sign = !(sign ^ z.sign);
102 for (int i = 0; i < D; i++)
103 for (int j = 0; i+j < D; j++)
104 ret.digits[i+j] += digits[i] * z.digits[j];
105 ret.carryover();
106 return ret;
107 }
108
109 constexpr BigInt operator/(const BigInt& z) const {
110 auto [q, r] = euclidean_division(*this, z);
111 return q;
112 }
113
114 constexpr BigInt operator%(const BigInt& z) const {
115 auto [q, r] = euclidean_division(*this, z);
116 return r;
117 }
118
119 constexpr BigInt operator+=(const BigInt& z) { return *this = *this + z; }
120 constexpr BigInt operator++() { return *this += 1; }
121 constexpr BigInt operator-=(const BigInt& z) { return *this = *this - z; }
122 constexpr BigInt operator--() { return *this -= 1; }
123 constexpr BigInt operator*=(const BigInt& z) { return *this = *this * z; }
124 constexpr BigInt operator/=(const BigInt& z) { return *this = *this / z; }
125 constexpr BigInt operator%=(const BigInt& z) { return *this = *this % z; }
126
127 static BigInt random(BigInt r) {
128 std::random_device rd;
129 std::default_random_engine rng(rd());
130 std::uniform_int_distribution<int> distribution(0, M-1);
131
132 BigInt ret;
133 for (uint64_t i = 0; i < D; i++)
134 ret.digits[i] = distribution(rng);
135
136 return ret % r;
137 }
138
139 friend std::ostream& operator<<(std::ostream& os, const BigInt<N, E>& z) {
140 if (z == 0) {
141 os << "0";
142 return os;
143 }
144
145 if (!z.sign)
146 os << "-";
147
148 int j;
149 for (j = z.D-1; z.digits[j] == 0; j--) ;
150 os << z.digits[j]; // Top digit is not padded
151
152 for (int i = j-1; i >= 0; i--) {
153 std::string num = std::to_string(z.digits[i]);
154 os << std::string(E - num.length(), '0') << num;
155 }
156 return os;
157 }
158
159private:
160 constexpr void carryover() {
161 for (int i = 1; i < D; i++) {
162 auto c = digits[i-1] / M;
163 digits[i-1] -= c * M;
164 digits[i] += c;
165 }
166 }
167
168 constexpr BigInt half() const {
169 BigInt ret;
170 uint64_t carry = 0;
171 for (int i = D-1; i >= 0; i--) {
172 ret.digits[i] += (digits[i] + M * carry) / 2;
173 carry = digits[i] % 2;
174 }
175 return ret;
176 }
177
178 static constexpr BigInt powM(uint64_t e) {
179 BigInt ret;
180 ret.digits[e] = 1;
181 return ret;
182 }
183
184 // Sum of non-negative integers
185 static constexpr BigInt positive_sum(const BigInt& x, const BigInt& y) {
186 BigInt ret;
187 for (int i = 0; i < D; i++)
188 ret.digits[i] = x.digits[i] + y.digits[i];
189 ret.carryover();
190 return ret;
191 }
192
193 // Difference of non-negative integers (result may be negative)
194 static constexpr BigInt positive_diff(const BigInt& x, const BigInt& y) {
195 if (y > x)
196 return -positive_diff(y, x);
197
198 BigInt ret;
199 uint64_t carry = 0;
200 for (int i = 0; i < D; i++) {
201 uint64_t oldcarry = carry;
202 if (x.digits[i] < y.digits[i] + oldcarry) {
203 ret.digits[i] = M;
204 carry = 1;
205 } else {
206 carry = 0;
207 }
208 ret.digits[i] += x.digits[i];
209 ret.digits[i] -= y.digits[i] + oldcarry;
210 }
211 ret.carryover();
212 return ret;
213 }
214
215 // Division with remainder, UB if y == 0
216 static constexpr std::pair<BigInt, BigInt>
217 euclidean_division(const BigInt& x, const BigInt& y) {
218 auto [q, r] = positive_div(x.abs(), y.abs());
219 if (x.sign && y.sign)
220 return std::pair(q, r);
221 else if (x.sign && !y.sign)
222 return r == 0 ? std::pair(-q, 0) : std::pair(-q-1, y+r);
223 else if (!x.sign && y.sign)
224 return r == 0 ? std::pair(-q, r) : std::pair(-q-1, y-r);
225 else
226 return std::pair(q, -r);
227 }
228
229 // Division with remainder of non-negative integers, UB if y == 0
230 // This method is inefficient (O(log(x/y)) BigInt multiplications)
231 static constexpr std::pair<BigInt, BigInt>
232 positive_div(const BigInt& x, const BigInt& y) {
233 BigInt q = 0;
234 BigInt r = x;
235
236 if (y > x)
237 return std::pair(q, r);
238
239 BigInt lb = 0;
240 BigInt ub = x;
241 while (true) {
242 BigInt q = (ub + lb).half();
243 BigInt r = x - y*q;
244
245 if (r < 0)
246 ub = q;
247 else if (r >= y)
248 lb = q+1;
249 else
250 return std::pair(q, r);
251 }
252 }
253};
254
255constexpr uint64_t abs64(int64_t x) {
256 return static_cast<uint64_t>(x > 0 ? x : -x);
257}
258
259constexpr uint64_t pow10(uint64_t e) {
260 if (e == 0)
261 return 1;
262 else
263 return 10 * pow10(e-1);
264}
265
266#endif
diff --git a/code/cpp/ecm.cpp b/code/cpp/ecm.cpp
new file mode 100644
index 0000000..64dcb6b
--- /dev/null
+++ b/code/cpp/ecm.cpp
@@ -0,0 +1,91 @@
1#include "bigint.h"
2#include "zmodn.h"
3
4#include <cstdint>
5#include <iostream>
6#include <variant>
7
8constexpr BigInt N(NUMBER);
9
10class Point {
11public:
12 bool is_infinity;
13 Zmod<N> x;
14 Zmod<N> y;
15
16 Point(Zmod<N> a, Zmod<N> b) : is_infinity{false}, x{a}, y{b} {}
17 Point(bool inf) : is_infinity{inf}, x{0}, y{0} {}
18};
19
20std::variant<Point, BigInt<>>
21sum_or_factor(BigInt<> a, Point p, Point q) {
22 if (p.is_infinity) return q;
23 if (q.is_infinity) return p;
24 if (p.x == q.x && p.y + q.y == Zmod<N>(0)) return Point(true);
25
26 Zmod<N> l(0);
27 if (p.x != q.x)
28 if (auto inv_x = (p.x-q.x).inverse(); inv_x.has_value())
29 l = (p.y-q.y) * inv_x.value();
30 else
31 return std::get<0>(extended_gcd(N, (p.x-q.x).toint()));
32 else
33 if (auto inv_y = (p.y+q.y).inverse(); inv_y.has_value())
34 l = (Zmod<N>(3) * p.x * p.x + a) * inv_y.value();
35 else
36 return std::get<0>(extended_gcd(N, (p.y+q.y).toint()));
37
38 auto x = l*l - p.x - q.x;
39 auto y = l*(p.x-x) - p.y;
40
41 return Point(x, y);
42}
43
44std::variant<Point, BigInt<>>
45product_or_factor(BigInt<> a, std::variant<Point, BigInt<>> pi, BigInt<> m) {
46 if (std::holds_alternative<BigInt<>>(pi))
47 return std::get<BigInt<>>(pi);
48
49 auto p = std::get<Point>(pi);
50
51 if (m == 0)
52 return Point(true); // Anything multiplied by 0 is 0
53
54 // Divide-and-conquer multiplication (power) algorithm
55 if (m % 2 == 0) {
56 return product_or_factor(a, sum_or_factor(a, p, p), m/2);
57 } else {
58 auto pp = product_or_factor(a, p, m-1);
59 if (std::holds_alternative<BigInt<>>(pp))
60 return std::get<BigInt<>>(pp);
61 return sum_or_factor(a, p, std::get<Point>(pp));
62 }
63}
64
65BigInt<> find_factor_ecm() {
66 // Find a factor of the integer N.
67 // If N is prime, this method goes into an infinite loop.
68
69 while (true) {
70 BigInt a = BigInt<>::random(N);
71 Point p(BigInt<>::random(N), BigInt<>::random(N));
72 for (BigInt m = 2;
73 (m < 256 || m*m*m*m*m*m*m*m < N) && !p.is_infinity; m += 1) {
74 auto x = product_or_factor(a, p, m);
75 if (std::holds_alternative<BigInt<>>(x))
76 return std::get<BigInt<>>(x);
77 else
78 p = std::get<Point>(x);
79 }
80 }
81}
82
83int main() {
84 // N is a compile-time constant
85 if (BigInt f = find_factor_ecm(); f > 1 && f < N)
86 std::cout << N << " = " << f << " * " << N/f << std::endl;
87 else
88 std::cout << N << " is prime" << std::endl;
89
90 return 0;
91}
diff --git a/code/cpp/naive.cpp b/code/cpp/naive.cpp
new file mode 100644
index 0000000..ed741e6
--- /dev/null
+++ b/code/cpp/naive.cpp
@@ -0,0 +1,23 @@
1#include "bigint.h"
2
3#include <cstdint>
4#include <iostream>
5
6constexpr BigInt N(NUMBER);
7
8BigInt<> find_factor() {
9 for (BigInt i = 2; i*i < N; i += 1)
10 if (N % i == 0)
11 return i;
12 return -1;
13}
14
15int main() {
16 // N is a compile-time constant
17 if (auto f = find_factor(); f > 1 && f < N)
18 std::cout << N << " = " << f << " * " << N/f << std::endl;
19 else
20 std::cout << N << " is prime" << std::endl;
21
22 return 0;
23}
diff --git a/code/cpp/zmodn.h b/code/cpp/zmodn.h
new file mode 100644
index 0000000..a24f293
--- /dev/null
+++ b/code/cpp/zmodn.h
@@ -0,0 +1,79 @@
1#ifndef ZMODN_H
2#define ZMODN_H
3
4#include <cstdint>
5#include <iostream>
6#include <optional>
7#include <tuple>
8#include <type_traits>
9
10template<typename T>
11concept Integer = requires(T a, T b, int i, std::ostream& os) {
12 {T(i)};
13
14 {a + b} -> std::same_as<T>;
15 {a - b} -> std::same_as<T>;
16 {a * b} -> std::same_as<T>;
17 {a / b} -> std::same_as<T>;
18 {a % b} -> std::same_as<T>;
19
20 {a == b} -> std::same_as<bool>;
21 {a != b} -> std::same_as<bool>;
22
23 {os << a} -> std::same_as<std::ostream&>;
24};
25
26template<Integer T>
27std::tuple<T, T, T> extended_gcd(T a, T b) {
28 if (b == 0) return {a, 1, 0};
29 auto [g, x, y] = extended_gcd(b, a%b);
30 return {g, y, x - y*(a/b)};
31}
32
33template<Integer auto N>
34requires(N > 1)
35class Zmod {
36public:
37 Zmod(decltype(N) z) : value{(z%N + N) % N} {}
38 decltype(N) toint() const { return value; }
39
40 Zmod operator+(const Zmod& z) const { return value + z.value; }
41 Zmod operator-(const Zmod& z) const { return value - z.value; }
42 Zmod operator*(const Zmod& z) const { return value * z.value; }
43
44 Zmod operator+=(const Zmod& z) { return (*this) = value + z.value; }
45 Zmod operator-=(const Zmod& z) { return (*this) = value - z.value; }
46 Zmod operator*=(const Zmod& z) { return (*this) = value * z.value; }
47
48 Zmod operator^(decltype(N) z) const {
49 if (z == 0) return 1;
50 if (z % 2 == 0) return (((*this) * (*this)) ^ (z/2));
51 return (*this) * ((*this) ^ (z-1));
52 }
53
54 bool operator==(const Zmod& z) const { return value == z.value; }
55 bool operator!=(const Zmod& z) const { return value != z.value; }
56
57 std::optional<Zmod> inverse() const {
58 auto [g, a, _] = extended_gcd(value, N);
59 return g == 1 ? Zmod(a) : std::optional<Zmod>{};
60 }
61
62 std::optional<Zmod> operator/(const Zmod& d) const {
63 auto i = d.inverse();
64 return i ? (*this) * i.value() : i;
65 }
66
67 std::optional<Zmod> operator/=(const Zmod& d) {
68 auto q = *this / d;
69 return q ? (*this = q.value()) : q;
70 }
71
72 friend std::ostream& operator<<(std::ostream& os, const Zmod<N>& z) {
73 return os << "(" << z.value << " mod " << N << ")";
74 }
75private:
76 decltype(N) value;
77};
78
79#endif
diff --git a/code/python/ecm.py b/code/python/ecm.py
new file mode 100755
index 0000000..662facf
--- /dev/null
+++ b/code/python/ecm.py
@@ -0,0 +1,75 @@
1#! /bin/env python
2
3from sys import argv
4from random import randint
5from math import sqrt
6from dataclasses import dataclass
7
8@dataclass
9class Point:
10 x: int = 0
11 y: int = 0
12 is_zero: bool = False
13
14@dataclass
15class FactorFound(Exception):
16 factor: int = 0
17
18# Returns gcd(a, b) and x, y such that ax + by = gcd(a,b)
19def extended_gcd(a: int, b: int) -> (int, int, int):
20 if b == 0:
21 return a, 1, 0
22 g, x, y = extended_gcd(b, a % b)
23 return g, y, x - y * (a // b)
24
25def inverse_modulo(a: int, n: int) -> int:
26 g, x, y = extended_gcd(a, n)
27 if g != 1:
28 raise FactorFound(g)
29 return x
30
31def ec_sum(p: Point, q: Point, A: int, n: int) -> Point:
32 if p.is_zero:
33 return q
34 if q.is_zero:
35 return p
36 if (p.x - q.x) % n == 0 and (p.y + q.y) % n == 0:
37 return Point(is_zero = True)
38
39 if (p.x - q.x) % n != 0:
40 k = ((p.y - q.y) * inverse_modulo(p.x - q.x, n)) % n
41 else:
42 k = ((3 * p.x**2 + A) * inverse_modulo(p.y + q.y, n)) % n
43
44 x = (k**2 - p.x - q.x) % n
45 y = (k * (p.x - x) - p.y) % n
46
47 return Point(x = x, y = y)
48
49def ec_mul(M: int, p: Point, A: int, n: int) -> Point:
50 if M == 0:
51 return Point(is_zero = True)
52 if M % 2 == 0:
53 return ec_mul(M // 2, ec_sum(p, p, A, n), A, n)
54 return ec_sum(p, ec_mul(M - 1, p, A, n), A, n)
55
56# Elliptic curve factorization method
57# If n is prime, this method goes into an infinite loop
58def find_factor(n: int) -> int:
59 bound = max(int(sqrt(sqrt(sqrt(n)))), 256)
60
61 while True:
62 A = randint(0,n)
63 p = Point(x = randint(0,n), y = randint(0,n))
64 M = 2
65 while M < bound and not p.is_zero:
66 try:
67 p = ec_mul(M, p, A, n)
68 except FactorFound as ff:
69 #print("Found with A =", A, "M =", M, "and P =", p)
70 return ff.factor
71 M += 1
72
73N = int(argv[-1])
74f = find_factor(N)
75print(N, "=", f, "*", N//f)
diff --git a/code/python/naive.py b/code/python/naive.py
new file mode 100755
index 0000000..7f6ec00
--- /dev/null
+++ b/code/python/naive.py
@@ -0,0 +1,18 @@
1#!/bin/env python
2
3from sys import argv
4from math import floor, sqrt
5
6def naive_factor(n: int) -> int:
7 for i in range(2,floor(sqrt(n))+1):
8 if n%i == 0:
9 return i
10 else:
11 return -1
12
13N = int(argv[-1])
14f = naive_factor(N)
15if f == -1:
16 print(N, "is prime")
17else:
18 print(N, "=", f, "*", N//f)
diff --git a/images/beer.jpg b/images/beer.jpg
new file mode 100644
index 0000000..5a67225
--- /dev/null
+++ b/images/beer.jpg
Binary files differ
diff --git a/images/clock.png b/images/clock.png
new file mode 100644
index 0000000..631ee42
--- /dev/null
+++ b/images/clock.png
Binary files differ
diff --git a/images/clock2.png b/images/clock2.png
new file mode 100644
index 0000000..bc2706b
--- /dev/null
+++ b/images/clock2.png
Binary files differ
diff --git a/images/demo.jpg b/images/demo.jpg
new file mode 100644
index 0000000..eaf2cd9
--- /dev/null
+++ b/images/demo.jpg
Binary files differ
diff --git a/images/ec1.png b/images/ec1.png
new file mode 100644
index 0000000..1c31a1e
--- /dev/null
+++ b/images/ec1.png
Binary files differ
diff --git a/images/ec2.png b/images/ec2.png
new file mode 100644
index 0000000..c44f3c0
--- /dev/null
+++ b/images/ec2.png
Binary files differ
diff --git a/images/ec3.png b/images/ec3.png
new file mode 100644
index 0000000..6db47e4
--- /dev/null
+++ b/images/ec3.png
Binary files differ
diff --git a/images/euclid.png b/images/euclid.png
new file mode 100644
index 0000000..ccfec81
--- /dev/null
+++ b/images/euclid.png
Binary files differ
diff --git a/images/factorization.webp b/images/factorization.webp
new file mode 100644
index 0000000..892a53d
--- /dev/null
+++ b/images/factorization.webp
Binary files differ
diff --git a/images/number-line.svg b/images/number-line.svg
new file mode 100644
index 0000000..bc765a7
--- /dev/null
+++ b/images/number-line.svg
@@ -0,0 +1,262 @@
1<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2<!-- Created with Inkscape (http://www.inkscape.org/) -->
3<svg
4 xmlns:dc="http://purl.org/dc/elements/1.1/"
5 xmlns:cc="http://web.resource.org/cc/"
6 xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
7 xmlns:svg="http://www.w3.org/2000/svg"
8 xmlns="http://www.w3.org/2000/svg"
9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
11 width="400"
12 height="50"
13 id="svg2"
14 sodipodi:version="0.32"
15 inkscape:version="0.45.1"
16 version="1.0"
17 sodipodi:docbase="/Users/ezrakatz/Desktop"
18 sodipodi:docname="NumberLineIntegersAlt.svg"
19 inkscape:output_extension="org.inkscape.output.svg.inkscape"
20 inkscape:export-filename="/Users/ezrakatz/Documents/BasicMath/NumberLine.png"
21 inkscape:export-xdpi="180"
22 inkscape:export-ydpi="180">
23 <defs
24 id="defs4">
25 <marker
26 inkscape:stockid="StopL"
27 orient="auto"
28 refY="0.0"
29 refX="0.0"
30 id="StopL"
31 style="overflow:visible">
32 <path
33 id="path3272"
34 d="M 0.0,5.65 L 0.0,-5.65"
35 style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt"
36 transform="scale(0.8)" />
37 </marker>
38 <marker
39 inkscape:stockid="Dot_l"
40 orient="auto"
41 refY="0.0"
42 refX="0.0"
43 id="Dot_l"
44 style="overflow:visible">
45 <path
46 id="path3227"
47 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 "
48 style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none;marker-end:none"
49 transform="scale(0.8) translate(7.4, 1)" />
50 </marker>
51 <marker
52 inkscape:stockid="RazorWire"
53 id="RazorWire"
54 refX="0"
55 refY="0"
56 orient="auto">
57 style=&quot;overflow:visible&quot;&gt;
58 <path
59 id="path3751"
60 transform="scale(0.8,0.8)"
61 style="fill:#808080;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:0.1pt"
62 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 " />
63</marker>
64 <marker
65 inkscape:stockid="DiamondL"
66 orient="auto"
67 refY="0.0"
68 refX="0.0"
69 id="DiamondL"
70 style="overflow:visible">
71 <path
72 id="path3661"
73 d="M 0,-7.0710768 L -7.0710894,0 L 0,7.0710589 L 7.0710462,0 L 0,-7.0710768 z "
74 style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none"
75 transform="scale(0.8)" />
76 </marker>
77 <marker
78 inkscape:stockid="Dot_m"
79 orient="auto"
80 refY="0.0"
81 refX="0.0"
82 id="Dot_m"
83 style="overflow:visible">
84 <path
85 id="path3646"
86 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 "
87 style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none;marker-end:none"
88 transform="scale(0.4) translate(7.4, 1)" />
89 </marker>
90 <marker
91 inkscape:stockid="Arrow1Lend"
92 orient="auto"
93 refY="0"
94 refX="0"
95 id="Arrow1Lend"
96 style="overflow:visible">
97 <path
98 id="path3584"
99 d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z "
100 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
101 transform="matrix(-0.8,0,0,-0.8,-10,0)" />
102 </marker>
103 <marker
104 inkscape:stockid="TriangleInL"
105 orient="auto"
106 refY="0"
107 refX="0"
108 id="TriangleInL"
109 style="overflow:visible">
110 <path
111 id="path3670"
112 d="M 5.77,0 L -2.88,5 L -2.88,-5 L 5.77,0 z "
113 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
114 transform="scale(-0.8,-0.8)" />
115 </marker>
116 <marker
117 inkscape:stockid="Arrow1Mstart"
118 orient="auto"
119 refY="0"
120 refX="0"
121 id="Arrow1Mstart"
122 style="overflow:visible">
123 <path
124 id="path3587"
125 d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z "
126 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
127 transform="matrix(0.4,0,0,0.4,4,0)" />
128 </marker>
129 <marker
130 inkscape:stockid="Arrow1Lstart"
131 orient="auto"
132 refY="0"
133 refX="0"
134 id="Arrow1Lstart"
135 style="overflow:visible">
136 <path
137 id="path3581"
138 d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z "
139 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
140 transform="matrix(0.8,0,0,0.8,10,0)" />
141 </marker>
142 </defs>
143 <sodipodi:namedview
144 id="base"
145 pagecolor="#ffffff"
146 bordercolor="#666666"
147 borderopacity="1.0"
148 gridtolerance="10000"
149 guidetolerance="10"
150 objecttolerance="10"
151 inkscape:pageopacity="0.0"
152 inkscape:pageshadow="2"
153 inkscape:zoom="7.9195959"
154 inkscape:cx="52.143012"
155 inkscape:cy="11.483946"
156 inkscape:document-units="px"
157 inkscape:current-layer="g2179"
158 width="400px"
159 height="50px"
160 inkscape:window-width="1329"
161 inkscape:window-height="810"
162 inkscape:window-x="80"
163 inkscape:window-y="0"
164 showguides="true"
165 inkscape:guide-bbox="true" />
166 <metadata
167 id="metadata7">
168 <rdf:RDF>
169 <cc:Work
170 rdf:about="">
171 <dc:format>image/svg+xml</dc:format>
172 <dc:type
173 rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
174 </cc:Work>
175 </rdf:RDF>
176 </metadata>
177 <g
178 inkscape:label="Layer 1"
179 inkscape:groupmode="layer"
180 id="layer1">
181 <path
182 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"
183 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"
184 id="text2185" />
185 <g
186 id="g2179">
187 <path
188 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.99763459px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
189 d="M 2,25.25 L 2,26.25 L 398,26.25 L 398,25.25 L 2,25.25 z "
190 id="path2189"
191 sodipodi:nodetypes="ccccc" />
192 <path
193 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
194 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 "
195 id="path2185"
196 sodipodi:nodetypes="ccccccccccc" />
197 <path
198 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
199 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 "
200 id="path2187" />
201 <path
202 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
203 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 "
204 id="path2190" />
205 <path
206 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
207 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 "
208 id="path2192" />
209 <path
210 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
211 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 "
212 id="path2194" />
213 <path
214 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
215 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 "
216 id="path2196" />
217 <path
218 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
219 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 "
220 id="path2198" />
221 <path
222 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
223 d="M 227,21.25 L 227,30.28125 L 228,30.28125 L 228,21.25 L 227,21.25 z "
224 id="path2200" />
225 <path
226 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
227 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 "
228 id="path2202" />
229 <path
230 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
231 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 "
232 id="path2204" />
233 <path
234 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
235 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 "
236 id="path2206" />
237 <path
238 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
239 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 "
240 id="path2208" />
241 <path
242 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
243 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 "
244 id="path2210" />
245 <path
246 style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:0.79810767pt;stroke-opacity:1"
247 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 "
248 id="path2212"
249 sodipodi:nodetypes="ccccccccccc" />
250 </g>
251 <path
252 sodipodi:type="arc"
253 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"
254 id="path4331"
255 sodipodi:cx="189.10715"
256 sodipodi:cy="6.2500005"
257 sodipodi:rx="0.17857143"
258 sodipodi:ry="0.17857143"
259 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"
260 transform="matrix(14,0,0,14,-2447.4708,-61.85223)" />
261 </g>
262</svg>
diff --git a/images/numbers.jpg b/images/numbers.jpg
new file mode 100644
index 0000000..9b0f835
--- /dev/null
+++ b/images/numbers.jpg
Binary files differ
diff --git a/images/questions.png b/images/questions.png
new file mode 100644
index 0000000..eee3df2
--- /dev/null
+++ b/images/questions.png
Binary files differ
diff --git a/images/sum-1a.png b/images/sum-1a.png
new file mode 100644
index 0000000..61fb531
--- /dev/null
+++ b/images/sum-1a.png
Binary files differ
diff --git a/images/sum-1b.png b/images/sum-1b.png
new file mode 100644
index 0000000..f3a7972
--- /dev/null
+++ b/images/sum-1b.png
Binary files differ
diff --git a/images/sum-1c.png b/images/sum-1c.png
new file mode 100644
index 0000000..c534cce
--- /dev/null
+++ b/images/sum-1c.png
Binary files differ
diff --git a/images/sum-2a.png b/images/sum-2a.png
new file mode 100644
index 0000000..d925e7a
--- /dev/null
+++ b/images/sum-2a.png
Binary files differ
diff --git a/images/sum-2b.png b/images/sum-2b.png
new file mode 100644
index 0000000..dbd6f03
--- /dev/null
+++ b/images/sum-2b.png
Binary files differ
diff --git a/images/sum-2c.png b/images/sum-2c.png
new file mode 100644
index 0000000..4637bb8
--- /dev/null
+++ b/images/sum-2c.png
Binary files differ
diff --git a/images/sum-3a.png b/images/sum-3a.png
new file mode 100644
index 0000000..f85d7ff
--- /dev/null
+++ b/images/sum-3a.png
Binary files differ
diff --git a/images/sum-3b.png b/images/sum-3b.png
new file mode 100644
index 0000000..537c5b2
--- /dev/null
+++ b/images/sum-3b.png
Binary files differ
diff --git a/images/sum-3c.png b/images/sum-3c.png
new file mode 100644
index 0000000..ca093dc
--- /dev/null
+++ b/images/sum-3c.png
Binary files differ
diff --git a/images/sum-4a.png b/images/sum-4a.png
new file mode 100644
index 0000000..82eee13
--- /dev/null
+++ b/images/sum-4a.png
Binary files differ
diff --git a/images/sum-4b.png b/images/sum-4b.png
new file mode 100644
index 0000000..827c0c2
--- /dev/null
+++ b/images/sum-4b.png
Binary files differ
diff --git a/images/sum-4c.png b/images/sum-4c.png
new file mode 100644
index 0000000..bf323fd
--- /dev/null
+++ b/images/sum-4c.png
Binary files differ
diff --git a/index.html b/index.html
new file mode 100644
index 0000000..29d9e58
--- /dev/null
+++ b/index.html
@@ -0,0 +1,622 @@
1<!doctype html>
2<html lang="en">
3<head>
4 <title>Elliptic Curves and the ECM algorithm</title>
5 <meta name="viewport" content="width=device-width" />
6
7 <!-- Import MathJax script -->
8 <script id="MathJax-script" async src=
9 "https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"
10 ></script>
11
12 <!-- Import highlight.js script and style sheet -->
13 <script id="highlight.js" src="
14 https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.9.0/highlight.min.js"
15 ></script>
16 <link rel="stylesheet" href="
17 https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.9.0/styles/vs.css"
18 >
19
20 <!-- Custom style -->
21 <style>
22 html { height: 100vh; width: 98vw; margin: auto; font-family: sans-serif; }
23 h1 { font-size: 3.5vw; background-color: #eeeeee; margin: 0; }
24 body { font-size: 2.2vw; height: 100%; width: 100%; }
25 a, a:visited { color: #0f2899; text-decoration: none; }
26 a:hover { text-decoration: underline; }
27 figcaption { text-align: center; font-size: 1.5vw; }
28 em { font-style: normal; color: blue; }
29
30 .slide { outline: none; height: 100vh; width: 100%; }
31 .slide {
32 display: flex;
33 flex-direction: column;
34 justify-content: space-between;
35 }
36 .slide ul { margin-left: 1.5vw; }
37 .slide ol { margin-left: 1.5vw; }
38 .slide p { margin-left: 1.5vw; }
39
40 .slide.titlepage p, a { text-align: center; }
41 .slide.titlepage span.title { font-size: 3.6vw; font-weight: bold; }
42 .slide.titlepage span.author { }
43
44 .slide.ecsum img { width: 50%; display: block; margin: auto; }
45
46 .slide div.centertext { text-align: center; margin: auto; width: 60%; }
47
48 .columns {
49 display: flex;
50 flex-direction: row;
51 justify-content: space-between;
52 align-items: center;
53 }
54
55 .footer { font-size: 1.8vw; background-color: #eeeeee; }
56 .footer table { width: 100%; }
57 .footer-title { font-weight: bold; }
58 .footer-link { text-align: right; }
59 </style>
60 <meta charset="utf-8">
61</head>
62
63<body>
64
65<div class="slide titlepage" tabindex="-1"
66style="background-image: url('images/sum-2c.png');
67background-position: center;
68background-repeat: no-repeat;
69background-size: 70%;
70background-color: rgba(255, 255, 255, 0.85);
71background-blend-mode: overlay;">
72
73<p></p>
74
75<p><span class="title">Elliptic curves and the ECM algorithm<span></p>
76<p><span class="author">Sebastiano Tronto<span></p>
77<p><span class="event">ALTEN Scientific Software Evening<span></p>
78
79</div>
80
81<div class="slide titlepage" tabindex="-1"
82style="background-image: url('images/numbers.jpg');
83background-position: center;
84background-repeat: no-repeat;
85background-size: 100%;
86background-color: rgba(255, 255, 255, 0.75);
87background-blend-mode: overlay;">
88<p></p>
89<p><span class="title">Part I: Numbers<span></p>
90<p></p>
91</div>
92
93<div class="slide" tabindex="-1">
94<h1>The integers</h1>
95
96<img alt="The number line" src="images/number-line.svg"
97 style="width: 70%; margin-left: 15%; margin-right: 15%;"/>
98
99<ul>
100<li>Operations: sum \(+\), difference \(-\) and multiplication \(\times\)</li>
101<li>Various properties: associativity, commutativity, etc...</li>
102<li>What about division (without remainder)?<br>
103If <tt>\(\frac ab\)</tt> is an integer we say that
104<tt>\(a\)</tt><em> divides </em><tt>\(b\)</tt> (in code:
105<tt>a % b == 0</tt>)</li>
106</ul>
107</div>
108
109<div class="slide" tabindex="-1">
110<h1>The integers modulo N</h1>
111
112<div class="columns">
113
114<ul>
115<!-- li>Integers modulo <tt>N</tt>: the possible remainders of
116division by <tt>N</tt><br-->
117<li>Two numbers are the same if they give the <em>same remainder</em>
118when divided by <tt>N</tt></li>
119<li>Think of <tt>int</tt>, but with <tt>% N</tt>
120after every operation</li>
121<li>Examples with \(N=12\):
122\[9+5\equiv 14\equiv 2\pmod{12}\]
123\[7-11\equiv-4\equiv 8\pmod{12}\]
124\[3\times 4\equiv 12\equiv 0\pmod{12}\]
125</li>
126</ul>
127
128<img alt="The number clock" src="images/clock.png"
129 style="width: 35%;"/>
130
131</div>
132
133</div>
134
135<div class="slide" tabindex="-1">
136<h1>The integers modulo N - Division</h1>
137
138<p style="text-align: center;"><strong>What about division?</strong></p>
139
140<ul>
141<li>
142Sometimes it works
143\[
144\frac 37\equiv 9 \pmod{12} \qquad
145\text{because} \qquad 9\times 7 \equiv 63 \equiv 3 \pmod{12}
146\]
147</li>
148
149<li>
150Sometimes it does not
151\[
152\frac 32\equiv \; ? \pmod{4} \qquad {\color{red}\text{Impossible!}}
153\]
154</li>
155</ul>
156</div>
157
158<div class="slide" tabindex="-1">
159<h1>Integers modulo N - Division</h1>
160
161<ul>
162<li>
163Sometimes it's... weird?
164\[
165\frac 62 \equiv \; ? \pmod{8} \quad
166\begin{array}{l}
167\rightarrow {\color{red}3} \times 2 \equiv 6\pmod{8}\\
168\rightarrow {\color{red}7} \times 2 \equiv 14 \equiv 6 \pmod{8}
169\end{array}
170\]
171</li>
172</div>
173
174<div class="slide" tabindex="-1">
175<h1>Integers modulo N - Division</h1>
176<div class="columns">
177<ul>
178<li>Can divide by \(a\) when \[\operatorname{GCD}(a, N)=1\]</li>
179<li>With the
180<a href="https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm">
181extended GCD algorithm</a> find \(x\) and \(y\) such that
182\[
183ax+Ny=1
184\]
185<li>
186This means \(\frac{1}{a}\equiv x\pmod{N}\)
187</li>
188</ul>
189<pre><code class="language-python"
190style="border: 0.2vw solid; font-size: 2.2vw;">
191def extended_gcd(a, b):
192 if b == 0:
193 return a, 1, 0
194 g, x, y = extended_gcd(b, a % b)
195 return g, y, x - y*(a // b)
196</code></pre>
197</div>
198<p style="text-align: center;">
199Division always works if \(N\) is a <em>prime</em> number!</p>
200</div>
201
202<div class="slide" tabindex="-1">
203<h1>Modular arithmetic - recap</h1>
204<div class="columns">
205<ul>
206<li>Integers modulo \(N\) are (almost) like numbers</li>
207<li>Normal operations like \(+\), \(-\) and \(\times\) work</li>
208<li>Division sometimes works, sometimes not</li>
209<li>Division always works if \(N\) is <em>prime</em></li>
210</ul>
211<img alt="The number line" src="images/clock2.png" style="width: 40%;"/>
212</div>
213</div>
214
215<div class="slide titlepage" tabindex="-1"
216style="background-image: url('images/sum-2c.png');
217background-position: center;
218background-repeat: no-repeat;
219background-size: 70%;
220background-color: rgba(255, 255, 255, 0.85);
221background-blend-mode: overlay;">
222<p></p>
223<p><span class="title">Part II: Elliptic Curves<span></p>
224<p></p>
225</div>
226
227<div class="slide" tabindex="-1">
228<h1>Elliptic curves</h1>
229
230<div class="columns">
231
232<p>
233An <em>elliptic curve</em> is a curve with equation
234\[ y^2 = x^3+Ax+B \]
235Where \(A\) and \(B\) are numbers with \[4A^3+27B^2\neq 0\]
236</p>
237
238<figure style="width: 45%;">
239<figcaption>\(y^2=x^3-x+1\) <br> \((A=-1, B=1\))</figcaption>
240<img alt="An elliptic curve" src="images/ec1.png" style="width: 100%;"/>
241</figure>
242
243</div>
244</div>
245
246<div class="slide" tabindex="-1">
247<h1>Elliptic curves</h1>
248
249<div class="columns">
250
251<figure style="width: 45%;">
252<figcaption>\(y^2=x^3+13x-34\) <br> \((A=13, B=-34\))</figcaption>
253<img alt="An elliptic curve" src="images/ec3.png" style="width: 100%;"/>
254</figure>
255
256<figure style="width: 45%;">
257<figcaption>\(y^2=x^3-x\) <br> \((A=-1, B=0\))</figcaption>
258<img alt="An elliptic curve" src="images/ec2.png" style="width: 100%;"/>
259</figure>
260
261</div>
262</div>
263
264<div class="slide" tabindex="-1">
265<h1>Elliptic curves</h1>
266
267<div class="columns">
268<ul>
269<li>There is a "sum" operation for points of a curve
270(NOT the sum of coordinates)</li>
271<li>To make things work out nicely, we pretend the curve has
272a <em>point at infinity</em> that acts as \(0\):
273\[P+0=0\qquad 0+P=0\qquad P-P=0\]</li>
274</ul>
275
276<img alt="Elliptic curve sum" src="images/sum-2c.png" style="width: 80%;"/>
277
278</div>
279</div>
280
281<div class="slide ecsum" tabindex="-1">
282<h1>Elliptic curves - sum operation - example 1</h2>
283<img alt="Elliptic curve sum" src="images/sum-2a.png"/>
284</div>
285<div class="slide ecsum" tabindex="-1">
286<h1>Elliptic curves - sum operation - example 1</h2>
287<img alt="Elliptic curve sum" src="images/sum-2b.png"/>
288</div>
289<div class="slide ecsum" tabindex="-1">
290<h1>Elliptic curves - sum operation - example 1</h2>
291<img alt="Elliptic curve sum" src="images/sum-2c.png"/>
292</div>
293
294<div class="slide ecsum" tabindex="-1">
295<h1>Elliptic curves - sum operation - example 2</h2>
296<img alt="Elliptic curve sum" src="images/sum-3a.png"/>
297</div>
298<div class="slide ecsum" tabindex="-1">
299<h1>Elliptic curves - sum operation - example 2</h2>
300<img alt="Elliptic curve sum" src="images/sum-3b.png"/>
301</div>
302<div class="slide ecsum" tabindex="-1">
303<h1>Elliptic curves - sum operation - example 2</h2>
304<img alt="Elliptic curve sum" src="images/sum-3c.png"/>
305</div>
306
307<div class="slide ecsum" tabindex="-1">
308<h1>Elliptic curves - sum operation - example 3</h2>
309<img alt="Elliptic curve sum" src="images/sum-4a.png"/>
310</div>
311<div class="slide ecsum" tabindex="-1">
312<h1>Elliptic curves - sum operation - example 3</h2>
313<img alt="Elliptic curve sum" src="images/sum-4b.png"/>
314</div>
315<div class="slide ecsum" tabindex="-1">
316<h1>Elliptic curves - sum operation - example 3</h2>
317<img alt="Elliptic curve sum" src="images/sum-4c.png"/>
318</div>
319
320<div class="slide" tabindex="-1">
321<h1>Elliptic curves - sum operation - code</h1>
322
323<div class="columns">
324<pre><code class="language-python"
325style="font-size: 2.8vh;">
326# Computes p+q on the elliptic curve y^2 = x^3 + Ax + B
327def ec_sum(p: Point, q: Point, A: double) -> Point:
328 if p.is_zero:
329 return q
330 if q.is_zero:
331 return p
332 if p.x == q.x and p.y == -q.y:
333 return Point(is_zero = True)
334
335 if p.x != q.x:
336 k = (p.y - q.y) / (p.x - q.x)
337 else:
338 k = (3 * p.x**2 + A) / (p.y + q.y)
339
340 new_x = k**2 - p.x - q.x
341 new_y = k * (p.x - new_x) - p.y
342 return Point(x = new_x, y = new_y)
343</code></pre>
344
345<pre><code class="language-python"
346style="border: 0.2vw solid; font-size: 2.8vh;">
347@dataclass
348class Point:
349 x: int = 0
350 y: int = 0
351 is_zero: bool = False
352</code></pre>
353
354</div>
355</div>
356
357<div class="slide" tabindex="-1">
358<h1>Elliptic curves - recap</h1>
359<div class="columns">
360<ul>
361<li>Curves of equation \(y^2=x^3+Ax+B\)</li>
362<li>Can "sum" points of the same curve</li>
363<li>Nice properties: associativity, commutativity...</li>
364<li>The sum operation can be easily implemented</li>
365</ul>
366<img alt="The number line" src="images/sum-2c.png" style="width: 40%;"/>
367</div>
368</div>
369
370<div class="slide titlepage" tabindex="-1"
371style="background-image: url('images/factorization.webp');
372background-position: center;
373background-repeat: no-repeat;
374background-size: 50%;
375background-color: rgba(255, 255, 255, 0.90);
376background-blend-mode: overlay;">
377<p></p>
378<p><span class="title">Part III: The Elliptic Curve Factorization Method<span></p>
379<p></p>
380</div>
381
382<div class="slide" tabindex="-1">
383<h1>Integer factorization</h1>
384<p style="text-align: center;"><strong>
385Every positive integer can be written as the product of prime numbers
386</strong></p>
387<div class="columns">
388<ul>
389<li>Example: \(69420 = 2\times 2\times 3\times 5\times 13\times 89\)</li>
390<li>Computationally hard</li>
391<li>Important for cryptography!</li>
392</ul>
393<img src="images/euclid.png" style="height: 60vh;"/>
394</div>
395</div>
396
397<div class="slide" tabindex="-1">
398<h1>Integer factorization - high-level procedure</h1>
399
400<div class="columns">
401<pre><code class="language-python"
402style="border: 0.2vw solid; font-size: 1.4vw;">
403# Returns the list of prime factors of n
404def factorize(n: int) -> list:
405 if n == 1:
406 return []
407
408 if is_prime(n):
409 return [n]
410
411 f = find_factor(n)
412
413 return factorize(n) + factorize(n//f)
414</code></pre>
415
416<ul>
417<li><tt>is_prime(n)</tt> can be implemented
418efficiently
419(<a href="https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test">Miller-Rabin</a>,
420<a href="https://en.wikipedia.org/wiki/AKS_primality_test">AKS</a>
421or <a href="https://en.wikipedia.org/wiki/Elliptic_curve_primality">ECPP</a>)
422</li>
423<li>Naive implementation of <tt>find_factor(n):</tt>
424<pre><code class="language-python" style="font-size: 2vw;">
425def find_factor(n: int) -> int:
426 for i in range(2,floor(sqrt(n))+1):
427 if n % i == 0:
428 return i
429</code></pre>
430</li>
431</ul>
432
433</div>
434</div>
435
436<div class="slide" tabindex="-1">
437<h1>Find Factor - Elliptic Curve Method</h1>
438<div>
439<p><strong>To find a factor of \(n\):</strong><p>
440<ol>
441<li>Take a random Elliptic Curve \(E\)
442and a random point \(P\) of \(E\)</li>
443<li>Take a <em>suitable number \(m\)</em></li>
444<li>Try to compute \(m\cdot P = P+P+\cdots+P\quad\) (\(m\) times)
445with <em>coordinates modulo \(n\)</em></li>
446<li>If you attempt an <em>impossible division</em> by some number \(d\),
447<em>return \(\operatorname{GCD}(n,d)\)</em></li>
448<li>Go back to 1.</li>
449</ol>
450</div>
451</div>
452
453<div class="slide" tabindex="-1" style="font-size: 2vw;">
454<h1>Find Factor - Elliptic Curve Method - Example</h1>
455<ul>
456<li>Take \(n = 91\)</li>
457<li>Take \(E: y^2 = x^3 + 51x -371\) and \(P = (11, 39)\) and \(M = 2\)</li>
458<li>
459Try to compute \(M\cdot P=P+P\pmod n\):
460\[ k = \frac{3x_p^2+51}{2y_p} \pmod n\]
461Is \(2y_p=78\) invertible modulo \(91\)?
462\[ \operatorname{GCD}(78, 91) = 13 \neq 1 \quad \implies \quad \text{NO!} \]
463</li>
464<li>Found factor: \(13\)</li>
465</div>
466
467<div class="slide titlepage" tabindex="-1"
468style="background-image: url('images/demo.jpg');
469background-position: center;
470background-repeat: no-repeat;
471background-size: 100%;
472background-color: rgba(255, 255, 255, 0.60);
473background-blend-mode: overlay;">
474<p></p>
475<p><span class="title">Demo time!<span></p>
476<a href="https://git.tronto.net/ecm">git.tronto.net/ecm</a>
477<p></p>
478</div>
479
480<div class="slide" tabindex="-1">
481<h1>Elliptic Curve Method - Questions</h1>
482<div class="centertext">
483<p><strong>
484Q: Aren't we just computing the \(\operatorname{GCD}\) with random numbers?
485</strong></p>
486<p>
487A: Yes, but Elliptic Curve operations produce "good candidates"
488for these random numbers.
489</p>
490</div>
491</div>
492
493<div class="slide" tabindex="-1">
494<h1>Elliptic Curve Method - Questions</h1>
495<div class="centertext">
496<p><strong>Q: Can we do the same without elliptic curves?</strong></p>
497<p>A: Yes, with
498<a href="https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm">
499Pollard's \(p-1\) Algorithm</a>, but ECM is faster.</p>
500</div>
501</div>
502
503<div class="slide" tabindex="-1">
504<h1>Elliptic Curve Method - Questions</h1>
505<div class="centertext">
506<p><strong>
507Q: Are there objects that are more complicated than Elliptic Curves
508and can make the method even faster?
509</strong></p>
510<p>A: Yes, there are higher-dimensional
511<a href="https://en.wikipedia.org/wiki/Abelian_variety">
512Abelian Varieties</a> and other
513<a href="https://en.wikipedia.org/wiki/Algebraic_group">
514Algebraic Groups</a>, but they are much harder (if not impossible)
515to implement efficiently.</p>
516</div>
517</div>
518
519<div class="slide titlepage" tabindex="-1"
520style="background-image: url('images/questions.png');
521background-position: center;
522background-repeat: no-repeat;
523background-size: 60%;
524background-color: rgba(255, 255, 255, 0.85);
525background-blend-mode: overlay;">
526<p></p>
527<p><span class="title">More questions?<span></p>
528<p></p>
529</div>
530
531<div class="slide titlepage" tabindex="-1"
532style="background-image: url('images/beer.jpg');
533background-position: center;
534background-repeat: no-repeat;
535background-size: 80%;
536background-color: rgba(255, 255, 255, 0.65);
537background-blend-mode: overlay;">
538<p></p>
539<p><span class="title">Drinks!<span></p>
540<p></p>
541</div>
542
543<script>
544 // The list of all slides of the presentation.
545 const slides = document.querySelectorAll(".slide");
546
547 // Navigation keys.
548 const keysNext = ["ArrowRight", "ArrowDown", " "];
549 const keysPrev = ["ArrowLeft", "ArrowUp"];
550
551 // Function to move to a given slide.
552 // This also focuses the slide, so any key press will be
553 // handled by the correct slide's event handler.
554 function goto(slide) {
555 slide.focus();
556 slide.scrollIntoView({
557 behavior: "instant",
558 block: "start"
559 });
560 }
561
562 // Handle key press events.
563 function onkeydown(i, e) {
564 if (keysNext.includes(e.key) && i+1 < slides.length) {
565 goto(slides[i+1]);
566 }
567 if (keysPrev.includes(e.key) && i > 0) {
568 goto(slides[i-1]);
569 }
570 }
571
572 // Handle click or tap events.
573 // Tapping on the right half of the screen scrolls forwards,
574 // tapping on the left half scrolls backwards.
575 function onclick(i, e) {
576 const w = slides[i].offsetWidth;
577 const x = e.clientX;
578
579 if (x > w/2 && i+1 < slides.length) {
580 goto(slides[i+1]);
581 }
582 if (x < w/2 && i > 0) {
583 goto(slides[i-1]);
584 }
585 }
586
587 // Disable default action of the navigation keys (e.g. scrolling).
588 document.addEventListener("keydown", function(e) {
589 if (keysNext.includes(e.key) || keysPrev.includes(e.key)) {
590 e.preventDefault();
591 }
592 });
593
594 // Function to add a footer to every slide.
595 function slideFooter() {
596 const start = "<div class=\"footer\"><table class=\"footer-table\"><tr>";
597 const title = "Elliptic Curves and the ECM algorithm"
598 const link = "<a href=https://tronto.net/talks/ecm>tronto.net/talks/ecm</a>";
599 const end = "</tr></table></div>";
600 const content =
601 "<td class=\"footer-title\">" + title + "</td>" +
602 "<td class=\"footer-link\">" + link + "</td>";
603
604 return start + content + end;
605 }
606
607 // Add slide footers and event handlers.
608 for (let i = 0; i < slides.length; i++) {
609 slides[i].innerHTML += slideFooter();
610 slides[i].addEventListener("keydown", e => onkeydown(i, e));
611 slides[i].addEventListener("click", e => onclick(i, e));
612 }
613
614 // Focus and scroll into view the first slide.
615 goto(slides[0]);
616
617 // Call highlight.js
618 hljs.highlightAll();
619</script>
620
621</body>
622</html>

Generated with cgit - Back to sebastiano.tronto.net