mersenneforum.org Strange timing for GMP-ECM 6.2.3
 Register FAQ Search Today's Posts Mark Forums Read

 2009-10-22, 19:42 #1 jyb     Aug 2005 Seattle, WA 2×34×11 Posts Strange timing for GMP-ECM 6.2.3 Can anybody explain the following anomaly, seen in GMP-ECM 6.2.3? Code: % echo 187916912042724004738494596691073958201795717624345429344224699255786723101372929902219413902513323285241 | ecm -sigma 3455028177 3e6 GMP-ECM 6.2.3 [powered by GMP 4.3.1] [ECM] Input number is 187916912042724004738494596691073958201795717624345429344224699255786723101372929902219413902513323285241 (105 digits) Using B1=3000000, B2=5706890290, polynomial Dickson(6), sigma=3455028177 Step 1 took 9263ms Step 2 took 4948ms ********** Factor found in step 2: 211523074369177100475152901773214226961 Found probable prime factor of 39 digits: 211523074369177100475152901773214226961 Probable prime cofactor 888399114863220054416373993221092999905502700297301957333000997481 has 66 digits This seems like a perfectly fine factorization. But if I now try to run the prime I just found through ecm with the same B1, it doesn't seem to finish (I only waited so long). If I drastically lower B1, I can see it finish, but in way more time than seems reasonable: Code: % echo 211523074369177100475152901773214226961 | ecm -sigma 3455028177 2e5 GMP-ECM 6.2.3 [powered by GMP 4.3.1] [ECM] Input number is 211523074369177100475152901773214226961 (39 digits) Using B1=200000, B2=128954290, polynomial Dickson(3), sigma=3455028177 Step 1 took 12669ms Step 2 took 1052ms Note the time for step 1, even with a B1 of 2e5! I have seen this with several other small input numbers, all in the 36-40 digit range. What the heck is ecm doing for those 12 seconds?
 2009-10-22, 21:12 #2 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 2·5·7·61 Posts Why are you trying to run ECM on a prime? No wonder it's being wacky... besides, I'm pretty sure that you'd find nothing at all, or the prime you're trying to ECM.
2009-10-22, 21:48   #3
jyb

Aug 2005
Seattle, WA

2×34×11 Posts

Quote:
 Originally Posted by Mini-Geek Why are you trying to run ECM on a prime? No wonder it's being wacky... besides, I'm pretty sure that you'd find nothing at all, or the prime you're trying to ECM.
There's nothing wacky about it at all. Since I'm using the same curve, it should find the input number itself (assuming I use the same B1; if I use a smaller B1 then I won't find anything, as you say; what's wrong with that?). If you look at the tests done in 'make check' you'll see a whole bunch of runs exactly like that.

Come to think of it, when I ran 'make check' all the tests passed, but some of them looked like they were taking way too long. I guess that's another example of the problem.

2009-10-22, 22:24   #4
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101011102 Posts

Quote:
 Originally Posted by jyb There's nothing wacky about it at all. Since I'm using the same curve, it should find the input number itself (assuming I use the same B1; if I use a smaller B1 then I won't find anything, as you say; what's wrong with that?). If you look at the tests done in 'make check' you'll see a whole bunch of runs exactly like that.
Works fine for me.
Code:
C:\Files\Prime\aliquot\ecm>ecm -sigma 3455028177 3000000
211523074369177100475152901773214226961
Input number is 211523074369177100475152901773214226961 (39 digits)
Using B1=3000000, B2=5706890290, polynomial Dickson(6), sigma=3455028177
Step 1 took 8500ms
Step 2 took 6047ms
********** Factor found in step 2: 211523074369177100475152901773214226961
Found input number N
1879169120427240047384945966910739582017957176243454293442246992557867231013729299022194139025133232
85241
Input number is 187916912042724004738494596691073958201795717624345429344224699255786723101372929902
219413902513323285241 (105 digits)
Using B1=3000000, B2=5706890290, polynomial Dickson(6), sigma=3455028177
Step 1 took 23703ms
Step 2 took 15328ms
********** Factor found in step 2: 211523074369177100475152901773214226961
Found probable prime factor of 39 digits: 211523074369177100475152901773214226961
Probable prime cofactor 888399114863220054416373993221092999905502700297301957333000997481 has 66 di
gits
Are you sure that you were using the right B1, (3e6) and not a typo (e.g. 3e7)?
By the way, here's the best B1 and B2 to find this particular factor with this particular sigma:
Code:
C:\Files\Prime\aliquot\ecm>ecm -sigma 3455028177 1961957 18910769
211523074369177100475152901773214226961
Input number is 211523074369177100475152901773214226961 (39 digits)
Using B1=1961957, B2=22231452, polynomial x^2, sigma=3455028177
Step 1 took 5297ms
Step 2 took 188ms
********** Factor found in step 2: 211523074369177100475152901773214226961
Found input number N

2009-10-23, 21:12   #5
jyb

Aug 2005
Seattle, WA

2·34·11 Posts

Quote:
 Originally Posted by Mini-Geek Works fine for me.
Ah, that's a good data point to know. Thanks. So it sounds like something in my particular build could be the problem. Akruppa, if you're out there, any advice on how to go about tracking this down? In particular, how can I figure out what ecm is doing for such a long time?

Quote:
 Originally Posted by Mini-Geek Are you sure that you were using the right B1, (3e6) and not a typo (e.g. 3e7)?
Oh yes, I tried it several times. Besides, you can look at my paste of output above and note that even for a ridiculously low B1 like 2e5, it still took longer than running the full B1 of 3e6 on the much larger composite number. Something is clearly wrong.

2010-02-10, 14:01   #6
akruppa

"Nancy"
Aug 2002
Alexandria

1001101000112 Posts

Quote:
 Originally Posted by jyb Can anybody explain the following anomaly, seen in GMP-ECM 6.2.3? Note the time for step 1, even with a B1 of 2e5! I have seen this with several other small input numbers, all in the 36-40 digit range. What the heck is ecm doing for those 12 seconds?
I finally have time to work on GMP-ECM again. The timing seems odd indeed. I can't reproduce the problem, with my 6.2.3 binary stage 1 with B1=2e5 takes 300ms. Does the binary with the weird timings still exist? If yes, can you send it to me?

Alex

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse GMP-ECM 8 2018-05-12 05:57 aurashift Software 5 2017-11-26 21:28 carpetpool Conjectures 'R Us 6 2016-12-31 06:02 jwh Information & Answers 1 2009-01-30 18:04 Kevin Software 3 2002-09-12 14:03

All times are UTC. The time now is 09:41.

Mon Dec 6 09:41:38 UTC 2021 up 136 days, 4:10, 0 users, load averages: 1.38, 1.64, 1.52