Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
| Download
18.783 Lecture 10: Simple implementation of the elliptic curve factorization method (ECM) using Montgomery curves
Project: 18.783 Spring 2022
Views: 160License: MIT
Image: ubuntu2004
Kernel: SageMath 9.2
Montgomery curve group operations
In [1]:
In [2]:
Montgomery time: 0.13179600000000002
Weierstrass time: 0.3893659999999999
Single stage ECM using Montgomery curves
In [3]:
In [5]:
B = 6340
Expected number of iterations is about 51
1
2^2 * 3^2 * 53 * 83 * 107 * 31021313
2
2^5 * 3^2 * 5^2 * 7 * 10429652971
3
2^3 * 3^3 * 5 * 7 * 751 * 92584589
4
2^2 * 3 * 23 * 31 * 53 * 1159187767
5
2^3 * 3 * 5 * 191 * 22934315101
6
2^2 * 3^3 * 5 * 973434365177
7
2^3 * 3 * 7 * 179 * 8039 * 2174383
8
2^2 * 3^2 * 11 * 13 * 285611 * 357509
9
2^5 * 3^3 * 17 * 41 * 1439 * 606587
10
2^4 * 3^4 * 5 * 248299 * 326701
11
2^5 * 3 * 73 * 457 * 1657 * 99053
12
2^2 * 3 * 13 * 19 * 3539 * 50111993
13
2^3 * 3 * 5^2 * 71 * 1151 * 10720511
14
2^3 * 3 * 383 * 57186086557
15
2^3 * 3^3 * 19 * 23 * 5568846251
16
2^3 * 3^2 * 5 * 53 * 27550026401
17
2^3 * 3^2 * 7300757733821
18
2^3 * 3^5 * 5 * 31 * 1427 * 1222499
19
2^2 * 3^4 * 5 * 7^2 * 13 * 18899 * 26953
20
2^2 * 3^6 * 19 * 4217 * 2249861
21
2^2 * 3^3 * 4867171688773
22
2^2 * 3^2 * 7 * 127 * 239 * 68722387
23
2^9 * 3 * 5 * 7 * 31 * 673 * 468667
24
2^9 * 3^2 * 3187 * 35793643
25
2^6 * 3 * 13 * 18013 * 11691487
26
2^3 * 3^2 * 123637 * 59049937
27
2^4 * 3 * 11 * 995557826719
28
2^3 * 3 * 21902273581427
29
2^7 * 3^4 * 67 * 756711997
30
2^3 * 3^2 * 7 * 13 * 59 * 757 * 839 * 2141
525654532248367
ECM time: 9.709927
525654532248367
In [0]: