skip to page content
Dario Alpern's site Home Page
Ver sitio en castellano
alpertron logo

Factorization using the Elliptic Curve Method

In order to perform factorizations you need Java enabled. Please visit http://www.java.com in order to install Java.


Get the source code!

Applet configuration parameters




See factorization records

If your Web visualization program accepts cookies, you can complete the factorization of a large number in several sessions. Your computer will remember the state of the factorization. You only have to reload this page.

The execution time depends on the magnitude of the second largest prime factor and on your computer speed.

Since all calculations are performed in your computer, you can disconnect it from the Internet while the factorization is in progress.

You can also enter expressions that use the following operators and parentheses:

The pseudoprime tests used in functions B and N includes trial division by the 100 first primes and then up to 20 Rabin-Miller strong pseudoprime tests. So it has a very high probability to find a prime number.

The final value must have 10000 or fewer digits, intermediate results must have 20000 or fewer digits and in the case of divisions, the dividend must be multiple of the divisor.

The next table shows the optimal values of B1 given the number of digits of the factor and the expected number of curves using that limit. These values are averages.

Optimal values of B1 and expected curves
DigitsValues of B1Expected curves
15200025
201100090
2550000300
30250000700
351 0000001800
403 0000005100
4511 00000010600
5043 00000019300
55110 00000049000
60260 000000124000
65850 000000210000
702900 000000340000

The program runs 25 curves with limit B1 = 2000, 300 curves with limit B1 = 50000, 1675 curves with limit B1 = 1000000 and finally it uses curves with limit B1 = 11000000 until all factors are found.

Factoring Cunningham numbers

If the number to be factorized has the form ab 1 (Cunningham form) or if it is a Fibonacci or a Lucas number, the program finds all algebraic and Aurifeuillian factors before using ECM.

When the checkbox named Use Cunningham tables on server is enabled, the applet requests to the server known factors greater than 109, then it attempts to complete the factorization.

The sources of the data stored on the server are:

Factoring a number in several machines

The ECM factoring algorithm can be easily parallelized in several machines. In order to do it, run the factorization in the first computer from curve 1, run it in the second computer from curve 10000, in the third computer from curve 20000, and so on. In order to change the curve number, just type this number on the bottom-left input box and press Enter or click on the New Curve button.

When one of the machines discovers a new factor, you should enter this factor in the other computers by typing it in the bottom-right input box and pressing Enter (or clicking the Factor button).

Batch factorization

Put an expression per line, then press the appropiate button. The output will be placed in the lower pane.

Blank lines or comment lines (which start with a numeral '#' character) will be replicated on the lower pane.

Expression loop: with the following syntax you can factor or determine primality of several numbers typing only one line. You have to type four expression separated by semicolons:

Example: Find the factors of the first 100 numbers of the form prime minus one. The line to type is: x=3;x=n(x);i-100;x-1.



Factoring using the Self Initializing Quadratic Sieve (SIQS)

When the number to be factorized is in the range 31-90 digits, after computing some curves in order to find small factors, the program switches to SIQS (if the checkbox located below the applet enables it), which is an algorithm that is much faster than ECM when the number has two large prime factors. Since this method needs a large amount of your computer's memory, if you restart the applet the factorization begins from scratch. In order to start factoring immediately using SIQS, you can enter 0 in the New Curve box.

Threshold for switching to SIQS
Digits31-3536-4041-4546-5051-5556-6061-6566-7071-7576-8081-8586-90
Curve58152527324370150300350600

If you want to know the mathematics behind the computation of the sum of squares, click here.

If you find any error or you have a comment, please fill in the form.