mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-01-27, 12:13   #1
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23×132 Posts
Default 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.
alpertron is offline   Reply With Quote
Old 2005-01-27, 18:40   #2
Wolf
 
Wolf's Avatar
 
Jul 2003
UK

638 Posts
Default

Thanks Dario. Great program.
For the record my Athlon XP2100+ does 10^59+213 in 1m 12s.
Wolf is offline   Reply With Quote
Old 2005-01-27, 18:53   #3
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

7678 Posts
Default

That's great Dario.

If you don't mind answering, how specifically did you improve the performance?
grandpascorpion is offline   Reply With Quote
Old 2005-01-27, 19:16   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23×132 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2005-03-12, 01:38   #5
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default 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
Maybeso is offline   Reply With Quote
Old 2005-03-12, 03:35   #6
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101Γ—103 Posts

254C16 Posts
Default

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
Uncwilly is offline   Reply With Quote
Old 2005-03-12, 08:31   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·19·281 Posts
Default

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.

I'll think about it.


Paul
xilman is online now   Reply With Quote
Old 2005-03-12, 08:46   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1067810 Posts
Default

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
xilman is online now   Reply With Quote
Old 2005-03-12, 09:50   #9
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default

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
Maybeso is offline   Reply With Quote
Old 2005-03-12, 13:02   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101001101101102 Posts
Default

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.

Now thinking about the c1965.

Paul
xilman is online now   Reply With Quote
Old 2005-03-13, 00:56   #11
PBMcL
 
PBMcL's Avatar
 
Jan 2005

2×31 Posts
Default

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.
PBMcL is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New feature in my ECM applet alpertron Factoring 87 2014-11-21 21:23
New online applet for factorization ET_ Lone Mersenne Hunters 69 2014-06-01 17:34
Porting my factorization applet to Android alpertron Programming 2 2013-03-19 11:28
A strange applet: 3.14159 Miscellaneous Math 7 2010-06-01 01:29
GMP-ECM vs. Alpertron's factoring applet ixfd64 GMP-ECM 4 2006-01-02 13:13

All times are UTC. The time now is 15:46.

Fri May 7 15:46:35 UTC 2021 up 29 days, 10:27, 1 user, load averages: 5.20, 4.66, 4.40

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.