Prime Factorization and Primality Test (Big Integers)
Tests primality and factors whole numbers into primes in exponent form, using exact big-integer arithmetic.
Use the tool
Why this tool exists
Factoring is the basis of fractions, divisibility and number theory homework. Type 360 and get 2^3 x 3^2 x 5, with the number of divisors, their sum and Euler totient. The same tool copes with numbers of 30 digits or more.
Small factors are removed by trial division, primality is tested with Miller-Rabin using twelve fixed bases (proven correct for numbers below about 3.3e24), and larger composites are split with Pollard rho. Above 3.3e24 a prime verdict is marked as probable. If a very hard number resists the time budget, the unfactored composite part is shown instead of guessing.
How to use it
- Enter one or more whole numbers, one per line.
- Read the factorization or the statement that the number is prime.
- Use the divisor count, divisor sum and totient lines if you need them.
- For numbers over 30 digits, expect some to take a while or stay partly factored.
Frequently asked questions
Is a prime verdict always proven?
Below about 3.3e24 yes. Above it the result is a very strong probable-prime test.
What is the Euler totient?
The count of numbers up to n that share no factor with n.
Can it factor RSA-size numbers?
No. Hundreds of digits are far beyond this method.
Are my numbers sent anywhere?
No.