mersenneforum.org mathematica7.0 can easily factorize 10^67+1111
 Register FAQ Search Today's Posts Mark Forums Read

 2008-12-06, 08:47 #1 aaa120   Oct 2008 24 Posts mathematica7.0 can easily factorize 10^67+1111 input :Timing[FactorInteger[10^67 + 1111]] output :{4.703, {{2225021, 1}, {1857766060519267, 1}, {2419217198278205425660754412115585800799721473, 1}}} I also used msieve 1.39 to factorize 10^67+1111,I tried for several times ,but it always slower than Mathematica 7.0! WHO can explain this phenomenon ? Sat Dec 06 16:44:25 2008 Sat Dec 06 16:44:25 2008 Sat Dec 06 16:44:25 2008 Msieve v. 1.39 Sat Dec 06 16:44:25 2008 random seeds: 474384f4 452b00a4 Sat Dec 06 16:44:25 2008 factoring 10000000000000000000000000000000000000000000000000000000000000001111 (68 digits) Sat Dec 06 16:44:26 2008 searching for 15-digit factors Sat Dec 06 16:44:27 2008 commencing quadratic sieve (61-digit input) Sat Dec 06 16:44:27 2008 using multiplier of 1 Sat Dec 06 16:44:27 2008 using 64kb Pentium 4 sieve core Sat Dec 06 16:44:27 2008 sieve interval: 3 blocks of size 65536 Sat Dec 06 16:44:27 2008 processing polynomials in batches of 34 Sat Dec 06 16:44:27 2008 using a sieve bound of 67891 (3400 primes) Sat Dec 06 16:44:27 2008 using large prime bound of 3394550 (21 bits) Sat Dec 06 16:44:27 2008 using trial factoring cutoff of 22 bits Sat Dec 06 16:44:27 2008 polynomial 'A' values have 8 factors Sat Dec 06 16:44:58 2008 4171 relations (1647 full + 2524 combined from 19166 partial), need 3496 Sat Dec 06 16:44:59 2008 begin with 20813 relations Sat Dec 06 16:44:59 2008 reduce to 6297 relations in 2 passes Sat Dec 06 16:44:59 2008 attempting to read 6297 relations Sat Dec 06 16:44:59 2008 recovered 6297 relations Sat Dec 06 16:44:59 2008 recovered 5424 polynomials Sat Dec 06 16:44:59 2008 attempting to build 4171 cycles Sat Dec 06 16:44:59 2008 found 4171 cycles in 1 passes Sat Dec 06 16:44:59 2008 distribution of cycle lengths: Sat Dec 06 16:44:59 2008 length 1 : 1647 Sat Dec 06 16:44:59 2008 length 2 : 2524 Sat Dec 06 16:44:59 2008 largest cycle: 2 relations Sat Dec 06 16:44:59 2008 matrix is 3400 x 4171 (0.5 MB) with weight 114662 (27.49/col) Sat Dec 06 16:44:59 2008 sparse part has weight 114662 (27.49/col) Sat Dec 06 16:44:59 2008 filtering completed in 4 passes Sat Dec 06 16:44:59 2008 matrix is 3216 x 3280 (0.4 MB) with weight 84767 (25.84/col) Sat Dec 06 16:44:59 2008 sparse part has weight 84767 (25.84/col) Sat Dec 06 16:44:59 2008 commencing Lanczos iteration Sat Dec 06 16:44:59 2008 memory use: 0.5 MB Sat Dec 06 16:44:59 2008 lanczos halted after 52 iterations (dim = 3211) Sat Dec 06 16:44:59 2008 recovered 61 nontrivial dependencies Sat Dec 06 16:44:59 2008 p7 factor: 2225021 Sat Dec 06 16:44:59 2008 prp16 factor: 1857766060519267 Sat Dec 06 16:44:59 2008 prp46 factor: 2419217198278205425660754412115585800799721473 Sat Dec 06 16:44:59 2008 elapsed time 00:00:34
 2008-12-06, 09:07 #2 S485122     "Jacob" Sep 2006 Brussels, Belgium 25×3×19 Posts Dario Alpern's Factorization using the Elliptic Curve Method uses about 7 seconds to factor that number on my WS. Jacob
 2008-12-06, 09:11 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100110101100112 Posts Obviously, Mathematica ECMs (or TFs) just a little bit higher, so it finds the 16-digit factor without the use of heavy artillery. Jason arbitrarily set his small factor limit to 15-digits, and then proceeds with QS. This can be tweaked very easily; stop being such a user, go in the source and change a couple parameters and msieve will be faster. :-) OTOH, my opinion is that it doesn't have to be a swiss army knife, it is perfect for what it is doing - the big numbers. You have a choice of many tools, pick the one fitting your personal goal. If none fit, write your own. That's the zen. Last fiddled with by Batalov on 2008-12-06 at 09:19
 2008-12-06, 09:27 #4 10metreh     Nov 2008 44228 Posts In the "Running Msieve" thread, I explained that msieve with -e was better for factoring a number completely. It factors your number in 2 seconds on my 1.7GHz P4, compared to 34 seconds without -e. Instead of Code: msieve  or Code: msieve -v  use Code: msieve -e  or Code: msieve -e -v  to factor a number completely. Only use the first two if you are pretty sure there are no factors up to ~2/7 the size of the number. Last fiddled with by 10metreh on 2008-12-06 at 09:30
2008-12-06, 10:04   #5
aaa120

Oct 2008

24 Posts
how do you know ?

Quote:
 Originally Posted by Batalov Obviously, Mathematica ECMs (or TFs) just a little bit higher, so it finds the 16-digit factor without the use of heavy artillery. .
Mathematica is not an open source software,How do you
know "Mathematica ECMs (or TFs) just a little bit higher"?
Are you the employee of Wolfram Research?

2008-12-06, 10:12   #6
10metreh

Nov 2008

1001000100102 Posts

Quote:
 Originally Posted by aaa120 Mathematica is not an open source software,How do you know "Mathematica ECMs (or TFs) just a little bit higher"? Are you the employee of Wolfram Research?
It's just common knowledge that Batalov's solution must be the answer. Mathematica's FactorInteger is made to run ECM up to about 2/7 the size of the number then run QS, whereas msieve without -e is made to check for 15-digit factors then run QS, regardless of the size of the number. Using -e runs ECM up to about 2/7 of the number then run QS, like Mathematica. (I think this is how Mathematica's FactorInteger works, I don't know for sure!) Sadly, for this size input, msieve with -e only runs ECM up to 15 digits. Using the 2/7 rule says you should ECM up to ~20 digits. In fact, msieve sometimes does find the p16 factor with ECM. Alpertron's applet is far more finely calibrated, but sadly it jumps straight from 15 digits to 25 digits.

Last fiddled with by 10metreh on 2008-12-06 at 10:19

 2008-12-06, 10:45 #7 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 30458 Posts One version older (mathematica 6) on a slower P4 Celeron 1.7GHz it took 1097 sec. to factorize this number. I'm not sure if they aren't using gmp ecm in this version 7. As I remember from version 6 they are using gmp library. Build in all free codes then sell it for money, nice, isn't it?
 2008-12-06, 13:35 #8 jasonp Tribal Bullet     Oct 2004 354510 Posts The ECM limit is set to 15 digits because this runs so fast (less than a second) that it can be used on any input, since an input would have to be very small (<50 digits) for QS to take only one second. The tuning of ECM time is such that the expected runtime is at most 5% of what the QS code would need. This is a useful compromise that factors most numbers much more quickly than QS alone, and does not make hard ECM-proof numbers unduly slower. Put another way: if you need to factor a 100-digit input that will take 12 hours, would you want to waste 2 hours on ECM to 30-digits that may not be necessary? Many professional (for money) mathematical software products use free software libraries. Maybe some of them even use msieve. I personally don't care, but others care so much that they will not release their code under other than the full GPL. Last fiddled with by jasonp on 2008-12-06 at 13:52
 2008-12-06, 15:31 #9 10metreh     Nov 2008 2·33·43 Posts For a 100-digit number, I would probably run half the number of curves @ 25e4. I can't remember what I did for my still unfactored C100.
2008-12-06, 16:27   #10
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

599210 Posts

Quote:
 Originally Posted by 10metreh For a 100-digit number, I would probably run half the number of curves @ 25e4. I can't remember what I did for my still unfactored C100.
i alway run full 25-digit ecm for anything over 90 digits but that is partly because i overwise spend so much time copying stuff into msieve or ggnfs that it wastes less time
also one core of an overclocked Q6600 chomps through it in less than 30 mins

 2008-12-06, 17:12 #11 10metreh     Nov 2008 232210 Posts 25e4 is the 30 digit level. I generally run full 25-digits on anything above 85 digits (the perfect size is around 88 digits). However, this doesn't mean I only go to 20 digits for an 84 digit number. For that size, I do half the normal number of 25 digit curves. This half-level idea is why I don't miss factors like the P16 from 10^67+1111. (It happens that for a 68 digit number I do full 20-digit level, so that number is not the best example - the perfect size is around 70 digits.) Last fiddled with by 10metreh on 2008-12-06 at 17:14

 Similar Threads Thread Thread Starter Forum Replies Last Post Godzilla Miscellaneous Math 28 2017-10-31 18:14 wildrabbitt Hardware 5 2016-09-13 01:40 ProximaCentauri Miscellaneous Math 22 2014-12-05 13:07 Nightgamer360 Miscellaneous Math 9 2007-07-09 17:38

All times are UTC. The time now is 22:24.

Tue Aug 16 22:24:07 UTC 2022 up 40 days, 17:11, 1 user, load averages: 1.15, 1.05, 1.03