mathematica7.0 can easily factorize 10^67+1111

[aaa120]

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

[S485122]

Dario Alpern's Factorization using the Elliptic Curve Method uses about 7 seconds to factor that number on my WS.

Jacob

[Batalov]

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.

[10metreh]

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

msieve <num>

or

msieve -v <num>

use

msieve -e <num>

or

msieve -e -v <num>

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.

[aaa120]

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?

[10metreh]

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.

[R. Gerbicz]

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?

[jasonp]

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.

[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.

[henryzz]

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

[10metreh]

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.)