Faster factorization applet
 

Hello folks,

Yesterday I updated the new version of [URL=http://www.alpertron.com.ar/ECM.HTM]my factorization applet[/URL]. 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.

Thanks Dario. Great program.
For the record my Athlon XP2100+ does 10^59+213 in 1m 12s.

That's great Dario.

If you don't mind answering, how specifically did you improve the performance?

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.

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 :innocent: ) :[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 [/CODE]
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 [B]17:31[/B]] Iteration: __00000/#### [18.83%]. Per iteration time: 0.086 sec.
[Mar 11 [B]06:50[/B]] Iteration: __10000/#### [18.86%]. Per iteration time: [B]4.160 [/B] sec.

13.333 hours to do 10000 iterations! :shock: Ouch. :cry:

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.

:flex: A very powerful application, :showoff:

Bruce

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

[QUOTE=Maybeso]
Here's what was interesting (I'm still factoring it, so the number's secret :innocent: ) :[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 [/CODE]
[/QUOTE]
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

[QUOTE=Maybeso]
Using the (sweet) cookie feature, it is still working on the first composite:
curve 452, >= 30 digits 58%.
[/QUOTE]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

[QUOTE=xilman]Just spotted this. You are probably wasting your time ...[/QUOTE] :sad: And I was so hoping to get on the applets list of record factors. :sad:
(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! :bow:
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 [B]hint[/B]. :wink:

Bruce

[QUOTE=Maybeso]You, (or anyone else, he said, throwing down the gauntlet) have until then to find N. I will then, ..., give you, ..., a [B]hint[/B]. :wink:[/QUOTE]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 [b]very[/b] 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

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.