Primality Testing

Undoubtedly, prime numbers are crucial elements for many real-world applications, especially cryptography (see the RSA repository). One of the many problems related to prime numbers is determining whether a given number is prime (a primality test) or, equivalently, whether it is composite (a compositeness test). Deterministic methods exist, but none of them are efficient for large numbers. Therefore, practical implementations rely on probabilistic tests, which are highly efficient and can identify composite numbers with a high probabilities depending on the test used.

Fermat test

This method is inspired by Fermat's little theorem (and generally, Euler's theorem) which states that: $p$ prime $\implies$ for any $a \in \mathbb{Z}_p^\times$ , $a^{p-1} \equiv 1 \mod p$.

Therefore, a number for which this property doesn't hold for some base $a$ is certainly composite (in this case $a$ is called a witness), however, the inverse is not true in general, for example: $8^20 \equiv 1 \mod 21$ but $21=3*7$ is not prime (in this case, 8 is called non-witness for 21). The numbers for which the inverse always hold are called Carmichel numbers, the first 3 of them are 561, 1105 and 1729.

Miller-Rabin test

A witness according to Miller-Rabin test is a base $a$ verfying the following set of congruences: $a^k \not \equiv 1 \mod n$ and $a^{2^ik} \not \equiv -1 \mod n$ for $i \in {1 \cdots s-1}$ where $n-1 = 2^sk$.

No analogeous numbers to Carmichael numbers exists for this test, that is, for any composite number $n$, a witness coprime to n always exist.

For any composite number, at least $75%$ of bases are witnesses.

This Repository

This repository contains

• Functions to test primality of a given number based on both Fermat and Miller-Rabi methods.

• Functions to generate prime numbers of given bit-length using the two methods.

• A report explaining both methods with much more depth.

• Some comparative scripts and figures.

• Other methods will be added and further discussions will be made.

Author

Marouf Haider

For any questions, remarks, or suggestions, please contact me here: ensmmarouf@gmail.com

References

• Conrad, Keith. “THE MILLER–RABIN TEST.” (2017).
• Koblitz, N. (1987). Primality and Factoring. In: A Course in Number Theory and Cryptography. Graduate Texts in Mathematics, vol 114. Springer, New York, NY. https://doi.org/10.1007/978-1-4684-0310-7_5