From 7f1b8a358515b45d717c3c4b5baf2fbc0f568170 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Wed, 26 Feb 2025 17:12:06 +0100 Subject: Initial commit --- README.md | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 63 insertions(+) create mode 100644 README.md (limited to 'README.md') diff --git a/README.md b/README.md new file mode 100644 index 0000000..75f495a --- /dev/null +++ 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. -- cgit v1.3