mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-12-06, 08:47   #1
aaa120
 
Oct 2008

24 Posts
Default 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
aaa120 is offline   Reply With Quote
Old 2008-12-06, 09:07   #2
S485122
 
S485122's Avatar
 
"Jacob"
Sep 2006
Brussels, Belgium

22×439 Posts
Default

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

Jacob
S485122 is offline   Reply With Quote
Old 2008-12-06, 09:11   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·7·229 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2008-12-06, 09:27   #4
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

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>
or
Code:
msieve -v <num>
use
Code:
msieve -e <num>
or
Code:
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.

Last fiddled with by 10metreh on 2008-12-06 at 09:30
10metreh is offline   Reply With Quote
Old 2008-12-06, 10:04   #5
aaa120
 
Oct 2008

24 Posts
Default how do you know ?

Quote:
Originally Posted by Batalov View Post
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?
aaa120 is offline   Reply With Quote
Old 2008-12-06, 10:12   #6
10metreh
 
10metreh's Avatar
 
Nov 2008

44228 Posts
Default

Quote:
Originally Posted by aaa120 View Post
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
10metreh is offline   Reply With Quote
Old 2008-12-06, 10:45   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101111011112 Posts
Default

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?
R. Gerbicz is offline   Reply With Quote
Old 2008-12-06, 13:35   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

354310 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2008-12-06, 15:31   #9
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

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.
10metreh is offline   Reply With Quote
Old 2008-12-06, 16:27   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×2,969 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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
henryzz is offline   Reply With Quote
Old 2008-12-06, 17:12   #11
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

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
10metreh is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Do you know this method to factorize? Godzilla Miscellaneous Math 28 2017-10-31 18:14
recognise this easily? wildrabbitt Hardware 5 2016-09-13 01:40
Another interesting pattern of Mersenne exponents: they are prime!!!!1111 ProximaCentauri Miscellaneous Math 22 2014-12-05 13:07
Easily identify composites using multiplication Nightgamer360 Miscellaneous Math 9 2007-07-09 17:38

All times are UTC. The time now is 07:53.


Mon Dec 6 07:53:57 UTC 2021 up 136 days, 2:22, 0 users, load averages: 1.48, 1.74, 1.58

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.