## Modern Elliptic Curve Factorization, Part 2

### April 27, 2010

Here is our version, which relies on Montgomery’s elliptic arithmetic from the previous exercise:

`(define (ec-factor N B1 B2 S)`

(let-values (((An Ad Q) (curve12 N S)))

(let stage1 ((p 2) (Q Q))

(if (< p B1)

(stage1 (next-prime p) (multiply (expt p (ilog p B1)) Q An Ad N))

(let ((g (gcd (cdr Q) n))) (if (< 1 g n) g

(let ((QQ (double Q An Ad N))

(R (multiply (- B1 1) q An Ad n))

(T (multiply (+ B1 1) q An Ad n)))

(let stage2 ((p (next-prime B1)) (g g) (k (+ B1 1)) (R R) (T T))

(cond ((< B2 p) (let ((g (gcd g n))) (if (< 1 g n) g #f)))

((= k p) (stage2 (next-prime p) (modulo (* g (cdr T)) N)

(+ k 2) t (add T QQ R N)))

(else (stage2 p g (+ k 2) t (add T QQ R N))))))))))))

As an example, consider the factorization of the 99th repunit, the number that consists of 99 consecutive 1s, which is computed as (10^99-1)/9. The factors 3, 3, 37, 67, 199, 397, 21649, 34849, 333667, and 513239 are found by trial division or the rho method, leaving a 70-digit cofactor. The elliptic curve method finds a 19-digit factor 1344628210313298373 using the lucky curve with seed 85398978821858534277806684680913743239224200284672112948006322676318, leaving a remaining 51-digit prime co-factor 362853724342990469324766235474268869786311886053883, thus completing the factorization:

`> (ec-factor 250411029487608433927757216420194735307370292135006432870660366092481700801`

53000 2120000 85398978821858534277806684680913743239224200284672112948006322676318)

1344628210313298373

Here’s another example. On September 14, 1998, Conrad Curry found a 53-digit factor of 2^{677}-1 = 1943118631 · 531132717139346021081 · 978146583988637765536217 · P53 · P?? using bounds *B*_{1} = 11000000 and *B*_{2} = 100*B*_{1} with lucky curve *S* = 8689346476060549; with benefit of hindsight, we are able to reduce those bounds substantially:

`> (define (mersenne n) (- (expt 2 n) 1))`

> (define x (/ (mersenne 677) 1943118631 531132717139346021081 978146583988637765536217))

> (ec-factor x 9000000 16000000 8689346476060549)

53625112691923843508117942311516428173021903300344567

Curry’s accomplishment stood as a record for about fifteen months (that’s a long time in the factoring business). The current record elliptic-curve factor is a 73-digit factor of 2^{1181}-1 found by the team of Joppe Bos, Thorsten Kleinjung, Arjen Lenstra, and Peter Montgomery using a program running partly on a cluster of PlayStation 3 computers.

With the addition of the second stage, our elliptic curve factorization program is reasonably powerful; it has been used to find several 25-digit factors, which, notwithstanding the occasional record factorization as mentioned above, is about the limit of elliptic curve factorization. But elliptic curve factorization is generally slow, and our specific implementation is slower still, as we eschewed several algorithmic tricks in the interest of simplicity. There are fast implementations of elliptic curve factorization, but they are quite complicated; for instance, the GNU implementation contains 263 files and weighs in at 4.5MB of code, not counting the required big-integer library.

In addition to the elliptic arithmetic from the previous exercise, `ec-factor`

uses `ilog`

from the Standard Prelude and all of the machinery from the next-prime exercise. You can run the program at http://programmingpraxis.codepad.org/dN59DMk0.

Pages: 1 2

Two questions:

in line 6 of ecf, what is ‘q’

in line 11 of ecf, is that supposed to be g = gcd(*q*,n) like in the p-1 function?

In line 6, q should read Q-sub-z (it’s the z parameter of the point Q). I’ll fix that.

In line 11, g is the g that is initialized on line 6 and accumulated on line 11.

Since no one posted the source code for this so here is mine.How ever running this algorithm and Lenstra implementation, Lenstra seems to be good.

Lenstra Implementation

http://mukeshiiitm.wordpress.com/2011/01/17/elliptic-curve-prime-factorisation/

[…] is almost similar to previous example except using Montgomery curve rather than Lenstra curve. Programmingpraxis used Montgomery curve to find the prime factorisation. I personally feel that Lenstra algorithm […]

A solution in Python, borrowing the functions from http://programmingpraxis.com/2010/04/23/modern-elliptic-curve-factorization-part-1/#comment-1192:

I cannot wrap my head around the concept of Elliptic Curves let alone the ECM but I think I found a P195 factor. Is that a record as your article implies the current record stands at P73?

Here is the C227 composite and here are its factors using Yet Another Factorization Utility 1.34 from http://yafu.sourceforge.net

72862001761201652067512910912311143529912811111098135112781186477227938869603430735445831828875855453895937353829184560496255789629222413141111181212305252442828205640315040464229193625221719263020152111881958811118395473635456

=

2 x

2 x

2 x

2 x

2 x

2 x

2 x

7 x

5527 x

137885520290732817351584663 x

106705047172471266468660928563317852379901416010404723328566172957737395755840658022032569277618563231217065120661299797289022426791599936582159383554005399760617203071477939525944722428007054711

What am I missing ???

Also I currently I am factoring this number:

65453637459381111885198811211520302619172225361929424640503140562028284452523012121811111413242229967855624960451829383537598953548575881828345547330346069889322777641187811213598110111128995243111123109129752061651201762002867

Again a C227

Thank you for any feedback,

Email: pureprimes@yahoo.com

Web: http://www.heliwave.com

It seems the numbers have been truncated so I will break them into multiple 50-digit lines, sorry for the double post.

72862001761201652067512910912311143529912811111098

13511278118647722793886960343073544583182887585545

38959373538291845604962557896292224131411111812123

05252442828205640315040464229193625221719263020152

111881958811118395473635456

=

2 x

2 x

2 x

2 x

2 x

2 x

2 x

7 x

5527 x

137885520290732817351584663 x

10670504717247126646866092856331785237990141601040

47233285661729577373957558406580220325692776185632

31217065120661299797289022426791599936582159383554

005399760617203071477939525944722428007054711

Is the above P195 a record for ECMs?

And here is the number being currently factored:

65453637459381111885198811211520302619172225361929

42464050314056202828445252301212181111141324222996

78556249604518293835375989535485758818283455473303

46069889322777641187811213598110111128995243111123

109129752061651201762002867

Thank you for any feedback

You found seven factors of 2, one factor of 7, one factor of 5527, and one 27-digit factor of 137885520290732817351584663. You did not find the remaining P195 co-factor, it is just “left over” after all the factors that you did find. Sorry, not a record.