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:
- + for addition
- - for subtraction
- * for multiplication
- / for integer division
- % for modulus (remainder of the integer division)
- ^ or ** for exponentiation (the exponent must be greater than or equal to zero).
- n!: factorial (n must be greater than or equal to zero).
- p#: primorial (product of all primes less or equal than p).
- F(n): Fibonacci number F_{n}
- L(n): Lucas number L_{n} = F_{n-1} + F_{n+1}
- P(n): Unrestricted Partition Number (number of decompositions of n into sums of integers without regard to order).
- Gcd(m,n): Greatest common divisor of these two integers.
- Modinv(m,n): inverse of m modulo n, only valid when gcd(m,n)=1.
- Modexp(m,n,r): finds m^{n} modulo r.
You can use the prefix 0x for hexadecimal numbers, for example 0x38 is equal to 56.
Digits | Values of B1 | Expected curves |
---|---|---|
15 | 2000 | 25 |
20 | 11000 | 90 |
25 | 50000 | 300 |
30 | 250000 | 700 |
35 | 1 000000 | 1800 |
40 | 3 000000 | 5100 |
45 | 11 000000 | 10600 |
50 | 43 000000 | 19300 |
55 | 110 000000 | 49000 |
60 | 260 000000 | 124000 |
65 | 850 000000 | 210000 |
70 | 2900 000000 | 340000 |
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.
Digits | 31-55 | 56-60 | 61-65 | 66-70 | 71-75 | 76-80 | 81-85 | 86-90 | 91-95 |
---|---|---|---|---|---|---|---|---|---|
Curve | 10 | 15 | 22 | 26 | 35 | 50 | 100 | 150 | 200 |
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:
- Digits per group: In order to improve readability, big numbers are separated by spaces forming groups of a fixed number of digits. With this input box, you can determine the number of digits in a group.
- Batch mode: See explanation in next section.
- Verbose mode: Not ready yet.
- Pretty print: If this checkbox is set, the exponents are shown in superscripts and the multiplication sign is " × ". The application also shows the number of digits for numbers with more than 30 digits. If the checkbox is not set, the exponents are preceded by the exponentiation sign " ^ " and the multiplication is indicated by asterisks. Also the number of digits is never displayed. This mode eases copying the results to other mathematical programs.
- Use Cunningham tables on server: When selected, if the number to be factored has the form a^{b} ± 1, the application will attempt to retrieve the known factors from the Web server. In order to reduce the database, only factors with at least 14 digits are included, so the application will find the small factors. These factors comes from Jonathan Crombie list and it includes 2674850 factors of Cunningham numbers.
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:
- 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 'c' (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);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.