mersenneforum.org Faster factorization applet
 Register FAQ Search Today's Posts Mark Forums Read

 2005-01-27, 12:13 #1 alpertron     Aug 2002 Buenos Aires, Argentina 1,447 Posts Faster factorization applet Hello folks, Yesterday I updated the new version of my factorization applet. The ECM factoring is about 20% faster and SIQS is about twice as fast as the previous version. For instance, the number 10^69+2607 = P35 x P35 is factored in 15m 14s and the number 10^59+213 = P30 x P30 is factored in 1m 30s in a Pentium 4 2.4 GHz. The last number is factored in 1m 57s in a Duron 1300 MHz. Of course an applet will never be as fast as a native program that is optimized for a particular processor.
 2005-01-27, 18:40 #2 Wolf     Jul 2003 UK 3·17 Posts Thanks Dario. Great program. For the record my Athlon XP2100+ does 10^59+213 in 1m 12s.
 2005-01-27, 18:53 #3 grandpascorpion     Jan 2005 Transdniestr 503 Posts That's great Dario. If you don't mind answering, how specifically did you improve the performance?
 2005-01-27, 19:16 #4 alpertron     Aug 2002 Buenos Aires, Argentina 1,447 Posts The applet used arrays of longs (64 bits) where the lower half (32 bits) were the "digits" of the big numbers. Now I reduced it to 31 bits so the carry management is much easier, producing a speed increase of about 20% in the modular multiplication routines (this takes most of the time in ECM factoring and primality proving). When I was doing the conversion I noticed that the there was a bug in the division of a big number by a long number (up to 64 bits) when the number represented in the array was negative. That bug caused to miss half of the congruences in the SIQS routine. After fixing the division routine the speed was doubled.
 2005-03-12, 01:38 #5 Maybeso     Aug 2002 Portland, OR USA 2×137 Posts Running Dario's applet with prime95. I was working on a factoring algorithm, when a large test number I tried produced some interesting results. I'd only coded it for small numbers and was just checking if it would blow up. It didn't, but it couldn't factor the number any further. Naturally, I entered the number in Dario's most excellent applet. Here's what was interesting (I'm still factoring it, so the number's secret ) : Code:  Factor Digits 3^2 1 11 2 331 3 24691 5 I got this far __ 316033 6 53840 816371 11 13 615553 872073 14 74 876004 778411 14 4 333087 .. (composite) 229 889924 .. (composite) 482 217 777567 .. (composite) 1965 Using the (sweet) cookie feature, it is still working on the first composite: curve 452, >= 30 digits 58%. However, now that Dario has improved the applet, here is its effect on prime95: [Mar 10 16:58] Iteration: __80000/#### [18.76%]. Per iteration time: 0.080 sec. [Mar 10 17:17] Iteration: __90000/#### [18.79%]. Per iteration time: 0.113 sec. [Mar 10 17:31] Iteration: __00000/#### [18.83%]. Per iteration time: 0.086 sec. [Mar 11 06:50] Iteration: __10000/#### [18.86%]. Per iteration time: 4.160 sec. 13.333 hours to do 10000 iterations! Ouch. It takes 5-10 seconds for the machine to respond to anything I do. Now I am very careful to have only one of them active at at time. A very powerful application, Bruce
 2005-03-12, 03:35 #6 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 10,531 Posts With Luigi's factor3_2 it is like throwing an anchor out. Prime95 suffers a slow down that is so large that the 6. sec iter times have been seen
2005-03-12, 08:31   #7
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2·5,657 Posts

Quote:
 Originally Posted by Maybeso Here's what was interesting (I'm still factoring it, so the number's secret ) : Code:  Factor Digits 3^2 1 11 2 331 3 24691 5 I got this far __ 316033 6 53840 816371 11 13 615553 872073 14 74 876004 778411 14 4 333087 .. (composite) 229 889924 .. (composite) 482 217 777567 .. (composite) 1965
Now there's a nice challenge. Reverse-engineer the secret number from the partial information given and from plausible assumptions about what may be regarded as "interesting".

For a start, note that 2^823+1 = 3.316033.13615553872073. C229 so that number is one of the algebraic factors of your mysterious N. There are clearly at least two more algebraic factors, or you would not have the factorization C482*C1965.

As yet, I haven't unambiguously identified the other small factors in my various tables of factorizations.

Paul

2005-03-12, 08:46   #8
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2·5,657 Posts

Quote:
 Originally Posted by Maybeso Using the (sweet) cookie feature, it is still working on the first composite: curve 452, >= 30 digits 58%.
Just spotted this. You are probably wasting your time.

If as noted earlier, the C229 is the cofactor of 2,823+ it has already had a large amount of ECM work done on it. You may find a factor with a relatively small B1 but the odds are very much against you.

Paul

2005-03-12, 09:50   #9
Maybeso

Aug 2002
Portland, OR USA

2·137 Posts

Quote:
 Originally Posted by xilman Just spotted this. You are probably wasting your time ...
And I was so hoping to get on the applets list of record factors.
(I've concluded that while up to the second-largest factor can be eligible, the final remaining factor is not, since it is always discovered by division.)

Yes, 2,823+ is one of the algebraic factors. Nice sleuthing!
I will stop the app when I go to work on monday, and get back to my exponent. I'm not about to tackle either the C482 or the C1965.
You, (or anyone else, he said, throwing down the gauntlet) have until then to find N. I will then, ..., give you, ..., a hint.

Bruce

2005-03-12, 13:02   #10
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2·5,657 Posts

Quote:
 Originally Posted by Maybeso You, (or anyone else, he said, throwing down the gauntlet) have until then to find N. I will then, ..., give you, ..., a hint.
I further note that 2^1601+1 = c482 = 8892483295418....290753

If that c482 is the same as yours, that's another one gone. I rather doubt it though, as that number is 3.3203.c478 with no more really tiny factors and you would have found those easily

If your number is 2^1601-1, its factorization is 158098751.9839849981808839.c458 and, again, you should have found the small factors without trouble.

There are, of course, a very large numbers near your c482 and I only have a notion of "interest" to decide among them, which is not a very good discriminant.

Paul

 2005-03-13, 00:56 #11 PBMcL     Jan 2005 2×31 Posts I believe the number he's trying to factor is.... (drum roll, please) 2^12345 + 1. All of the small divisors given divide this integer, which has the (large) algebraic factors 2^823 + 1, 2^(3*823)+1), and 2^(5*823) + 1. In Cunningham notation this would be 2^n + 1 n 1 = 3 3 = (1) 3 5 = (1) 11 15 = (1, 3, 5) 331 823 = (1) 316033.13615553872073.C229 (4333087...517267) 2469 = (1, 3, 823) 74876004778411.C482 (1392864...1088129) 4115 = (1, 5, 823) C(?)990 (8899242...1968931) 12345 = (1, 3, 5, 15, 823, 2469, 4115) 24691.53840816371.C1965 (2177775672...205611) I believe he transposed the C990 digits onto the C482.

 Similar Threads Thread Thread Starter Forum Replies Last Post alpertron Factoring 87 2014-11-21 21:23 ET_ Lone Mersenne Hunters 69 2014-06-01 17:34 alpertron Programming 2 2013-03-19 11:28 3.14159 Miscellaneous Math 7 2010-06-01 01:29 ixfd64 GMP-ECM 4 2006-01-02 13:13

All times are UTC. The time now is 14:11.

Wed May 25 14:11:13 UTC 2022 up 41 days, 12:12, 0 users, load averages: 1.78, 1.55, 1.35