73 digit ECM factor - Page 6

xilman · 2010-04-23, 18:03

Quote:

Originally Posted by chris2be8

Is anyone working on ECM on GPUs? That's the second biggest CPU sink in factoring.

Chris K

Yes.

Paul

jasonp · 2010-04-23, 22:25

Dan Bernstein has code available that runs ECM (stage 1) using Edwards curves on a GPU; IIRC his input size is very limited, essentially to support factorization of sieve reports from very large NFS runs.

bdodson · 2010-05-31, 19:11

Quote:

Originally Posted by wreck

Here is the second p73's group order

Code:

Magma V2.16-6     Mon Apr 19 2010 20:22:13    [Seed = 2434200602]
   -------------------------------------

[ <2, 2>, <3, 2>, <5, 1>, <23, 1>, <1429, 1>, <28229, 1>, <139133, 1>, <249677, 
1>, <389749, 1>, <15487861, 1>, <47501591, 1>, <111707179, 1>, <431421191, 1>, 
<13007798103359, 1> ]

Total time: 6.549 seconds, Total memory usage: 17.75MB

Looks like the third large factor is a p66

Code:

694217535399847678048415113186577758507635822252803808473674680017 
2^1073+1 3e9 3000000623 2010-05-31 J.Bos,T.Kleinjung,A.Lenstra,P.Montgomery

C281 = p66*p215; that's sigma = 3000000623.

(6th on the top50, in between the other two p66's by ecm)

axn · 2010-05-31, 19:31

Quote:

Originally Posted by bdodson

Looks like the third large factor is a p66

Code:

694217535399847678048415113186577758507635822252803808473674680017 
2^1073+1 3e9 3000000623 2010-05-31 J.Bos,T.Kleinjung,A.Lenstra,P.Montgomery

C281 = p66*p215; that's sigma = 3000000623.

(6th on the top50, in between the other two p66's by ecm)

That would be 2^1073-1, yes?

fivemack · 2010-05-31, 19:50

I'm finding it slightly uncanny that these large ECM runs on the not-very-many numbers of the form 2^10xx \pm 1 are finding so many factors that it would be post-facto infuriating to have found by kilobit SNFS.

I don't think I can quantify 'slightly uncanny', though I'm sure there are people who can.

xilman · 2010-05-31, 20:51

Quote:

Originally Posted by bdodson

Looks like the third large factor is a p66

Code:

694217535399847678048415113186577758507635822252803808473674680017 
2^1073+1 3e9 3000000623 2010-05-31 J.Bos,T.Kleinjung,A.Lenstra,P.Montgomery

C281 = p66*p215; that's sigma = 3000000623.

(6th on the top50, in between the other two p66's by ecm)

Arjen and I are now both at Eurocrypt in Nice&Monaco. I learned about this result as soon as he did and, I suspect, before anyone else outside EPFL. Joppe Bos is also here, but Thorsten and Peter are not. Aoki, however, is here. All the CNT people have been chatting together, as you may expect.

Very little number theory at this year's event.

Paul

bdodson · 2010-05-31, 23:12

Quote:

Originally Posted by axn

That would be 2^1073-1, yes?

Uhm, yes. +1 would have been larger news; not sure why my mouse
switched signs - I copied it from the ecmnet cgi report, which correctly
reads -1, along with Sam's page.

R.D. Silverman · 2010-06-01, 13:06

Quote:

Originally Posted by fivemack

I'm finding it slightly uncanny that these large ECM runs on the not-very-many numbers of the form 2^10xx \pm 1 are finding so many factors that it would be post-facto infuriating to have found by kilobit SNFS.

I don't think I can quantify 'slightly uncanny', though I'm sure there are people who can.

I don't find it uncanny at all. They are using B1 (and probably B2) limits
that are much larger than anyone else has tried. They are running ECM
on a fairly small set of numbers. It is not a surprise (to me, at least)
that they are finding ECM factors not found by others.

R. Gerbicz · 2010-06-01, 20:59

Quote:

Originally Posted by bdodson

Looks like the third large factor is a p66

Code:

694217535399847678048415113186577758507635822252803808473674680017 
2^1073+1 3e9 3000000623 2010-05-31 J.Bos,T.Kleinjung,A.Lenstra,P.Montgomery

C281 = p66*p215; that's sigma = 3000000623.

(6th on the top50, in between the other two p66's by ecm)

It looks like it was a big luck, found the p66 divisor at the 624th(?) curve (B1=3e9).

bdodson · 2010-06-02, 00:43

Quote:

Originally Posted by xilman

Arjen and I are now both at Eurocrypt in Nice&Monaco. I learned about this result as soon as he did and, I suspect, before anyone else outside EPFL. Joppe Bos is also here, but Thorsten and Peter are not. Aoki, however, is here. All the CNT people have been chatting together, as you may expect.

Very little number theory at this year's event.

Paul

So sounds like Eurocrypt gets the RSA768 paper?

jasonp · 2010-06-02, 01:44

It's not on the program...

Of course I wouldn't need to work that hard to justify a trip to the french riviera.

2010-06-02, 01:44	#66
jasonp Tribal Bullet Oct 2004 3×1,181 Posts	It's not on the program... Of course I wouldn't need to work that hard to justify a trip to the french riviera. Last fiddled with by jasonp on 2010-06-02 at 01:45

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factor a 108-digit number	sweety439	Factoring	9	2016-12-21 21:22
New 70 digit factor	R.D. Silverman	Cunningham Tables	16	2016-01-23 22:16
44-digit factor found using ECM w/ B1=1e6 & B2=1e8	WVU Mersenneer	Factoring	8	2010-04-24 17:01
Probability of n-digit factor?	roger	Factoring	3	2007-05-09 22:51
160 digit factor found of 366 digit (PRP-1)	AntonVrba	Factoring	7	2005-12-06 22:02

2010-04-23, 22:25	#57
jasonp Tribal Bullet Oct 2004 DD7₁₆ Posts	Dan Bernstein has code available that runs ECM (stage 1) using Edwards curves on a GPU; IIRC his input size is very limited, essentially to support factorization of sieve reports from very large NFS runs.

2010-05-31, 19:50	#60
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 6422₁₀ Posts	I'm finding it slightly uncanny that these large ECM runs on the not-very-many numbers of the form 2^10xx \pm 1 are finding so many factors that it would be post-facto infuriating to have found by kilobit SNFS. I don't think I can quantify 'slightly uncanny', though I'm sure there are people who can.