New feature in my ECM applet

[Robert_JD]

Originally Posted by alpertron

Robert J DuChateau was running ECM using the applet on 24+29^81 and found the factorization:

347 x 34503928686970842350938851377044353167566697578436905273
(Curve 210438) x
2377058158103859925326651218033244145946260234462377898431463

So he found a 56-digit factor using the applet (a new record). Of course this could have been found faster with SIQS or GNFS (the latter is not implemented in the applet and it will never be done).

Hello Dario,

Speaking of SIQS, and GNFS, those factors had already been found around 3 months ago just after I submitted my P50 factor to your applet

Nevertheless, I was determined to use your much slower ECM applet because I had good reason to believe that I could break the current record of 51 digits, especially after my previous success with that P50 factor.

Utilizing the entire 12 hyperthreads available on my 6 core 980x box, the factoring took approximately 2000 wall clock hours in finally resolving that ECM P56, P61 on your website

P.S. If it hadn't been for Paul Zimmermann's GMP-6.3 ECM, I never would have gained the insight into adjusting the B1, B2 parameters and ascertaining the best guesses on the range of elliptical curves necessary in successfully factoring such large integers

P.S.S. And of course an equal measure of credit goes to you Dario for having set up such an invaluable and educational website to tinker with

Best Regards,

RJD

[alpertron]

This is not related to factoring, but I've just converted the Web page which includes the factoring applet (http://www.alpertron.com.ar/ECM.HTM) to XHTML 1.0 Strict. I also made changes so it validates on accessibility checkers. Please let me know if there are errors introduced. I will convert the entire Web site to XHTML 1.0 Strict but it will take some time.

[Robert_JD]

Attention Dario,

I am pleased to announce the discovery of a new record factor on your applet

The input number is 121 digits and the two largest factors are p59 and p61, with a curve number of 914151.

The complete factorization results are included in an attachment below.

P.S. I've noticed the initial changes to your website, and have detected no errors so far.

RJ Duchateau

[alpertron]

This is interesting because for that curve the applet uses B1=11 million, B2 = 1100 million, which is optimized for finding 45-digit primes. If my applet used larger values of B1 and B2 for these curves, you should have saved at least 20%-30% of the time needed to find the prime factors.

Of course when there is a low probability to find 40-digit primes of your 120 digit number, you should have used another algorithm such as GNFS which is a lot faster (more than 100x).

[Robert_JD]

"This is interesting because for that curve the applet uses B1=11 million, B2 = 1100 million, which is optimized for finding 45-digit primes. If my applet used larger values of B1 and B2 for these curves, you should have saved at least 20%-30% of the time needed to find the prime factors".

Yep. You're absolutely right. I actually considered at one time in recompiling the ecm source code to ramp up the B1-B2 values to around 260e6 to about at least 1e12 on the B2 side. However, all I really wanted was to find out whether a B1-B2 of only 11e6-11e8 could actually be achieved at below the 1000000 curve mark. Otherwise, I would most likely abandon the factorization altogether.

But apparently I got very very lucky this time

"Of course when there is a low probability to find 40-digit primes of your 120 digit number, you should have used another algorithm such as GNFS which is a lot faster (more than 100x)".

Believe it or not, I've been using the latest version of GGNFS/ Msieve for about 6 months now. While those much faster and more efficient algorithms factored out that very same number in less than 3 hours, again all I ever wanted to accomplish was to see just how far I could go using your ecm applet at the more optimized, 45 factor B1-B2 values in order to hopefully resolve those factors. Just think, it took me nearly 6 months of 24/7 factoring on a 20 CPU clustered system to finally strike gold. What a relief!!!

Nevertheless, I think I'll be taking a much needed breather for the time being. It would appear that going for even higher values at this point would seem a bit on the absurd side, you think? My machines should undoubtedly thank me for finally coming to my senses for once

RJ DuChateau

[alpertron]

In general it is best for step 2 to run about in half the time of step 1. So incrementing B1 to 260M and B2 to 1T would not be a good idea because in that case the step 2 will take too long. GMP-ECM uses a different algorithm that needs a lot of memory (no applet can use that amount of memory) which allows greater values for B2.

[Robert_JD]

Incidently, I've been using ECM-GMP lately, and I must say I've been very impressed with the speed, while it's the ecm applet that seems to have a strong tendency in becoming a voracious memory hog - especially when running concurrent apps. But still if ecm-gmp needs a lot of memory to handle the increased B2 values, with much more efficiency, then obviously I'll be using it much more often.

BTW, which do you think is more faster; the latest version of mpir or gmp-5.0.1 ?

RJ DuChateau

[alpertron]

The applet cannot use more than 256 MB (this is specified in the XHTML page). The problem you experience is related to the priority of the process that runs the applet (Internet Explorer, Firefox, Google Chrome, etc.). That process and your applications have the same prority. Since the applet is always running, it will slow down other applications.

The solution to your problem is to decrease the navigator process priority. This can be done in Windows by launching the Task Manager (CTRL + SHIFT + Esc), then select the process (firefox.exe) and pop up the context menu using the right button of your mouse. Finally select Set Priority -> BelowNormal. In this way the applet will only run when other applications are not running.

[Robert_JD]

Thanks for that very helpful advice

Since I mainly use Linux for running factoring programs, I can simply go to "System Monitor" on a Fedora 14 distro and make the appropriate priority adjustments for Firefox similar to Windows.

RJ Duchateau

[alpertron]

A few days ago, the Java runtime was updated automatically to version 1.7.0_65 and my applet stopped working due to a bug in that JRE. If you want to continue using the applet, you will need to go to http://www.java.com and download the latest JRE, version 1.7.0_67, that has the bug fixed.

[ThiloHarich]

Hello,

can I use the ECM part of your code in my factoring application?
How can i call the ecm.java Class to get a factizization?

To give some Background:
I'm trying a variant of the SIQS where I use very small factors p_1, p_2,.. of the factorbase to get an a=p_1*p_2 * .. * p_s of the sieve polynom (ax+b)^2 -N.
So we get the maximal number of b's (2^(s-1)) out of the the polynom. But unfortunately then the sieve interval on x is smaller then the largest prime in the Factorbase. So we can not sieve anymore. A simple Variant would be using a fast factorization for small values with small primes. This could be your Elliptic curve algorithm.
Daniel Bernstein suggested to use a product tree http://cr.yp.to/papers/sf.pdf, which is faster then sieving. But Java has no fast FFT multiplication. We might combine the Product Tree with the Elliptic Curve. The running time of the ECM is basically bounded by the size of the factors and not the number to factorize. But I might also use a simple Variant of my Quadratic sieve.