20081206, 08:47  #1 
Oct 2008
2^{4} 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 15digit factors Sat Dec 06 16:44:27 2008 commencing quadratic sieve (61digit 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 
20081206, 09:07  #2 
"Jacob"
Sep 2006
Brussels, Belgium
2^{4}·3·37 Posts 
Dario Alpern's Factorization using the Elliptic Curve Method uses about 7 seconds to factor that number on my WS.
Jacob 
20081206, 09:11  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
11×881 Posts 
Obviously, Mathematica ECMs (or TFs) just a little bit higher, so it finds the 16digit factor without the use of heavy artillery.
Jason arbitrarily set his small factor limit to 15digits, 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 20081206 at 09:19 
20081206, 09:27  #4 
Nov 2008
2×3^{3}×43 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 <num> Code:
msieve v <num> Code:
msieve e <num> Code:
msieve e v <num> Last fiddled with by 10metreh on 20081206 at 09:30 
20081206, 10:04  #5  
Oct 2008
2^{4} Posts 
how do you know ?
Quote:
know "Mathematica ECMs (or TFs) just a little bit higher"? Are you the employee of Wolfram Research? 

20081206, 10:12  #6 
Nov 2008
4422_{8} Posts 
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 15digit 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 20081206 at 10:19 
20081206, 10:45  #7 
"Robert Gerbicz"
Oct 2005
Hungary
1,531 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? 
20081206, 13:35  #8 
Tribal Bullet
Oct 2004
3×1,181 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 ECMproof numbers unduly slower. Put another way: if you need to factor a 100digit input that will take 12 hours, would you want to waste 2 hours on ECM to 30digits 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 20081206 at 13:52 
20081206, 15:31  #9 
Nov 2008
2·3^{3}·43 Posts 
For a 100digit number, I would probably run half the number of curves @ 25e4. I can't remember what I did for my still unfactored C100.

20081206, 16:27  #10  
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
3·5·397 Posts 
Quote:
also one core of an overclocked Q6600 chomps through it in less than 30 mins 

20081206, 17:12  #11 
Nov 2008
2·3^{3}·43 Posts 
25e4 is the 30 digit level. I generally run full 25digits 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 halflevel 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 20digit level, so that number is not the best example  the perfect size is around 70 digits.)
Last fiddled with by 10metreh on 20081206 at 17:14 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Do you know this method to factorize?  Godzilla  Miscellaneous Math  28  20171031 18:14 
recognise this easily?  wildrabbitt  Hardware  5  20160913 01:40 
Another interesting pattern of Mersenne exponents: they are prime!!!!1111  ProximaCentauri  Miscellaneous Math  22  20141205 13:07 
Easily identify composites using multiplication  Nightgamer360  Miscellaneous Math  9  20070709 17:38 