# Factorization using the Elliptic Curve Method

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:

• - for subtraction
• * for multiplication
• / for integer division
• ^ for exponentiation
• n!: factorial
• p#: primorial (product of all primes less or equal than p).
• B(n): Previous pseudoprime to n
• F(n): Fibonacci number Fn
• L(n): Lucas number Ln = Fn-1 + Fn+1
• N(n): Next pseudoprime to n
• P(n): Unrestricted Partition Number (number of decompositions of n into integer summands without regard to order).

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:

• First expression: It must start with the string 'x=' and it sets the first value of x.
• Second expression: It must start with the string 'x=' and it sets the next value of x. It can include the variables 'x' (the variable) and 'i' (the counter).
• Third expression: It holds the end expression condition. If it is greater than zero the loop finishes, otherwise the loop continues. It can include the variables mentioned above.
• Fourth expression: It holds the expression to be factored. It can include the variables mentioned above.

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.

 Digits Curve 31-35 36-40 41-45 46-50 51-55 56-60 61-65 66-70 71-75 76-80 81-85 86-90 5 8 15 25 27 32 43 70 150 300 350 600

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.