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.
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).
- <, ==, >; <=, >=, != for comparisons. The operators return zero for false and -1 for true.
- AND, OR, XOR, NOT for binary logic.
- SHL: Shift left the number of bits specified on the right operand.
- SHR: Shift right the number of bits specified on the right operand.
- n!: factorial (n must be greater than or equal to zero).
- p#: primorial (product of all primes less or equal than p).
- B(n): Previous probable prime before n
- F(n): Fibonacci number Fn
- L(n): Lucas number Ln = Fn-1 + Fn+1
- N(n): Next probable prime after n
- 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.
- Modpow(m,n,r): finds mn modulo r.
- Totient(n): finds the number of positive integers less than n which are relatively prime to n.
- IsPrime(n): returns zero if n is not probable prime, -1 if it is.
- NumDivs(n): Number of positive divisors of n either prime or composite.
- SumDivs(n): Sum of positive divisors of n either prime or composite.
- NumDigits(n,r): Number of digits of n in base r.
- SumDigits(n,r): Sum of digits of n in base r.
- RevDigits(n,r): finds the value obtained by writing backwards the digits of n in base r.
- ConcatFact(m,n): Concatenates the prime factors of n according to the mode expressed in m which follows this table:
ConcatFact function modes Mode Order of factors Repeated factors 0 Ascending No 1 Descending No 2 Ascending Yes 3 Descending Yes
You can use the prefix 0x for hexadecimal numbers, for example 0x38 is equal to 56.
|Digits||Values of B1||Expected curves|
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.
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.
- 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.
- Hexadecimal output: If this checkbox is set, the numbers are shown in hexadecimal format instead of decimal, which is the common notation. To enter numbers in hexadecimal format, you will need to precede them by the string 0x. For instance 0x38 = 56. The program shows hexadecimal numbers with monospaced font.
- Use Cunningham tables on server: When selected, if the number to be factored has the form ab ± 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.
Write 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 or five expressions 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.
- Third expression: It holds the end expression condition. If it is equal to zero (meaning false) the loop finishes, otherwise the loop continues.
- Fourth expression: It holds the expression to be factored.
- Optional fifth expression: If this expression is different from zero (meaning true), the fourth expression is displayed or factored, and if is zero (meaning false), the fourth expression is ignored.
Except for the first expression, all other expressions must include the variable x and/or the counter c.
If the end expression is false after processing 1000 numbers, the Continue button will appear. Pressing this button will make the program to process the next 1000 numbers and so on.
Example 1: Find the factors of the first 100 numbers of the form prime minus one.
The line to type is:
Example 2: Find the Smith numbers less than 10000. A Smith number, according to Wikipedia, is a composite number for which, in a given base (in base 10 by default), the sum of its digits is equal to the sum of the digits in its prime factorization.
The line to type is:
x=1;x=x+1;x<10000;x;sumdigits(x, 10)==sumdigits(concatfact(2,x),10) and not isprime(x)
Written by Dario Alpern. Last updated 10 July 2018.