Primality Testing and Integer Factorization: The Computational Edge

How do we de­ter­mine if a very large number is prime, or find its prime fac­tors? These are cen­tral ques­tions in com­pu­ta­tion­al number theory.

Pri­mal­i­ty Test­ing

Pri­mal­i­ty test­ing is the prob­lem of de­ter­min­ing whether a given in­te­ger $N$ is prime or com­pos­ite.

• Trial Di­vi­sion: The sim­plest method. To test $N$, try di­vid­ing it by all primes up to $\sqrt{N}$. If none divide $N$, then $N$ is prime. This is ef­fi­cient for small $N$ but be­comes im­prac­ti­cal­ly slow for large num­bers (e.g., hun­dreds of digits).

• Fermat's Little The­o­rem: If $p$ is a prime number, then for any in­te­ger $a$ not di­vis­i­ble by $p$, we have:

(This means $a^{p-1} - 1$ is di­vis­i­ble by $p$). This can be used for a prob­a­bilis­tic test: pick a random $a$. If $a^{N-1} \not\equiv 1 \pmod{N}$, then $N$ is def­i­nite­ly com­pos­ite. If $a^{N-1} \equiv 1 \pmod{N}$, then $N$ is prob­a­bly prime. How­ev­er, some com­pos­ite num­bers (Carmichael num­bers) pass this test for all $a$ co­prime to $N$.

• Miller-Rabin Test: A more so­phis­ti­cat­ed prob­a­bilis­tic test based on Fermat's Little The­o­rem. It has a very low prob­a­bil­i­ty of de­clar­ing a com­pos­ite number as prime. By re­peat­ing the test with mul­ti­ple random choic­es of $a$, the prob­a­bil­i­ty of error can be made ar­bi­trar­i­ly small. This is widely used in prac­tice.

• AKS Pri­mal­i­ty Test (Agraw­al-Kayal-Saxena): Dis­cov­ered in 2002, this was a major break­through. It is the first al­go­rithm that is:

• Gen­er­al: Works for all num­bers.

• Poly­no­mi­al-time: Its run­time is bound­ed by a poly­no­mi­al in the number of digits of $N$.

• De­ter­min­is­tic: Always gives the cor­rect answer (not prob­a­bilis­tic).

• Un­con­di­tion­al: Its cor­rect­ness does not rely on any un­proven hy­pothe­ses (like RH).

  While the­o­ret­i­cal­ly im­por­tant, AKS is slower in prac­tice for most num­bers than Miller-Rabin.

In­te­ger Fac­tor­iza­tion

In­te­ger fac­tor­iza­tion is the prob­lem of find­ing the prime fac­tors of a given com­pos­ite in­te­ger $N$. This is be­lieved to be a much harder com­pu­ta­tion­al prob­lem than pri­mal­i­ty test­ing.

• For small num­bers, trial di­vi­sion works.

• For larger num­bers, more ad­vanced al­go­rithms are needed, such as:

• Pol­lard's rho al­go­rithm

• Qua­drat­ic Sieve (QS)

• Gen­er­al Number Field Sieve (GNFS): This is the fastest known al­go­rithm for fac­tor­ing very large in­te­gers (typ­i­cal­ly over 100 digits).

The pre­sumed dif­fi­cul­ty of fac­tor­ing large num­bers is the cor­ner­stone of many modern public-key cryp­tog­ra­phy sys­tems, most no­tably the RSA al­go­rithm. If some­one dis­cov­ered a fast, gen­er­al-pur­pose fac­tor­iza­tion al­go­rithm, it would break much of today's in­ter­net se­cu­ri­ty.