20050127, 12:13  #1 
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. 
20050127, 18:40  #2 
Jul 2003
UK
3·17 Posts 
Thanks Dario. Great program.
For the record my Athlon XP2100+ does 10^59+213 in 1m 12s. 
20050127, 18:53  #3 
Jan 2005
Transdniestr
503 Posts 
That's great Dario.
If you don't mind answering, how specifically did you improve the performance? 
20050127, 19:16  #4 
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. 
20050312, 01:38  #5 
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 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 510 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 
20050312, 03:35  #6 
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

20050312, 08:31  #7  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2·5,657 Posts 
Quote:
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. I'll think about it. Paul 

20050312, 08:46  #8  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2·5,657 Posts 
Quote:
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 

20050312, 09:50  #9  
Aug 2002
Portland, OR USA
2·137 Posts 
Quote:
(I've concluded that while up to the secondlargest 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 

20050312, 13:02  #10  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2·5,657 Posts 
Quote:
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^16011, 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. Now thinking about the c1965. Paul 

20050313, 00:56  #11 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New feature in my ECM applet  alpertron  Factoring  87  20141121 21:23 
New online applet for factorization  ET_  Lone Mersenne Hunters  69  20140601 17:34 
Porting my factorization applet to Android  alpertron  Programming  2  20130319 11:28 
A strange applet:  3.14159  Miscellaneous Math  7  20100601 01:29 
GMPECM vs. Alpertron's factoring applet  ixfd64  GMPECM  4  20060102 13:13 