Initial commit

1 files changed, 75 insertions, 0 deletions

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 @@
+#! /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)