Integer factorization calculator

This application factors numbers or numeric expressions using fast algorithms ECM and SIQS.

The program uses local storage to remember the progress of the factorization, so 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 even start this application without Internet connection after the first run.

The source code is written in C and compiled to asm.js and WebAssembly. The latter is faster, but it is not supported in all Web browsers. You can see the version while a number is being factored.

See factorization records for this application.

Expressions

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

You can use the prefix 0x for hexadecimal numbers, for example 0x38 is equal to 56.

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 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 when a factorization is in progress, press the button named More, type this number on the input box located on the new window and press 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).

Factoring using the Self Initializing Quadratic Sieve (SIQS)

When the number to be factorized is in the range 31 to 95 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-5556-6061-6566-7071-7576-8081-8586-9091-95
Curve101522263550100150200

Configuration

You can change settings for this application by pressing the Config button when a factorization is not in progress. A new window will pop up where you can select different settings:

The configuration is saved in your device, so when you start again the Web browser, all settings remain the same.

Batch factorization

After you enable batch mode by using the checkbox in the configuration window, put an expression per line, then press the appropriate 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);c-100;x-1.

Source code

You can download the source of the current program and the old factorization applet from GitHub. Notice that the source code is in C language and you need the Emscripten environment in order to generate Javascript.

Written by Dario Alpern. Last updated 6 May 2017.