Integer Explorer Introduction
Factorization
Precomputed Primes Division Trials
Primes are precomputed until the 3 403rd (31 643): the size of the table is 82 KB.
The algorithm tries to divide each number to be decomposed by those primes sucessively, begining with the least (2), to check if the reminder is 0.
If, after trying to divide by a prime, the remainder is 0 then we found a prime divisor. The initial number is replaced by the result of the division (to make the following calculations easier)
and we try the same prime again to see if it can divide our initial number more than once.
If, after trying a prime once or several times, the remainder is not 0 then this prime is not or is no more a divisor of our initial number, and the next prime is tried.
The algorithm stops in two cases:
- the remaining factor is less than the square of the prime currently tested: this means that the remaining factor is prime, and the decomposition is done.
- the last precomputed prime has been reached: the last big factor must be decomposed through another method, unless the primality test says it is prime.
It is really efficient for composite numbers with small factors up to 5 digits like factorials or even R24 = 3 × 7 × 11 × 13 × 37 × 73 × 101 × 137 × 9 901 × 99 990 001:
all the prime factors but the last one are less than 31 643 and thus are sucessfully found and the last factor is less than 31 6432 = 1 001 279 449 and thus is
dectected as being prime too.
Regular Division Trials
To find bigger factors, a more regular algorithm tries to divide by all the successive factors greater than the previous limit (31 643), either they are prime or not prime.
Of course, the test division with composite factors will always fail but this avoid to test their primality for optimization reasons. Nonetheless, to prevent from testing multiples of 2 and 3, only the factors of the form 6k+1
and 6k+5 are tested.
This algorithm can be stopped and can be resumed at anytime (you just need to remember the last number you have tested). It is runned by default for only 1 second.
This algorithm finds easily factors with 5 to 10 digits, like the second factor of
R31 = 2 791 × 6 943 319 × 57 336 415 063 790 604 359.
The same atgorithm detects that the third factor is prime because all the divisors are tested until its square root (7 572 081 290).
Pollard's Rho
Coming soon...
Primality Test
Fermat Primality Test
According to Fermat's little theorem:
if p is prime and a is coprime with p, ap-1≡1 (mod p).
This means that if p is prime then for any a such as 1≤a≤p, ap-1≡1 (mod p).
To be sure that a big number is composite, we need to find a a such as this equality is false.
For a=1 this equality is obvious. For a=p-1, we have that is a≡-1 (mod p) and therefore if p odd this equality is obvious too.
As a consequence the interval taken for a is generally 1<a<p
If a0p-1≡1 (mod p) and a1p-1≡1 (mod p) then (a0a1)p-1≡1 (mod p), so only the a that are prime in this interval need to be tested.
Miller-Rabbin Primality Test
Coming soon...
p=2sd+1
ad≡1 (mod p)
a2rd≡p-1 (mod p) for 0≤r≤s