mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2009-10-22, 19:42   #1
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

2×34×11 Posts
Default 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?
jyb is offline   Reply With Quote
Old 2009-10-22, 21:12   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2·5·7·61 Posts
Default

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.
Mini-Geek is offline   Reply With Quote
Old 2009-10-22, 21:48   #3
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

2×34×11 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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.
jyb is offline   Reply With Quote
Old 2009-10-22, 22:24   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101011102 Posts
Default

Quote:
Originally Posted by jyb View Post
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
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
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
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
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
Mini-Geek is offline   Reply With Quote
Old 2009-10-23, 21:12   #5
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

2·34·11 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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 View Post
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.
jyb is offline   Reply With Quote
Old 2010-02-10, 14:01   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

Quote:
Originally Posted by jyb View Post
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
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Timing for different B1 values? CRGreathouse GMP-ECM 8 2018-05-12 05:57
mprime #7 timing summary request aurashift Software 5 2017-11-26 21:28
Timing for large candidate carpetpool Conjectures 'R Us 6 2016-12-31 06:02
Very strange mem timing behavior, Asus M3A67-EM jwh Information & Answers 1 2009-01-30 18:04
Timing Options 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.