Function maths_traits::algebra::ring_like::miller_rabin

pub fn miller_rabin<Z: Natural>(n: Z) -> bool

Determines if a given Natural number is prime using the Miller-Rabin primality test

The algorithm works in essence by searching for counter-examples to Fermat's Little theorem, ie, that a^(p-1) = 1 for all a in Z/pZ when p is prime. In general, this tactic only gives a way to prove a number is not prime, but with a few modifications to the check and by picking the right examples, it is possible to turn this into a deterministic test. *

Furthermore, this particular algorithm has the surprising benefit of having a runtime that is polynomial in the number of bits in the input. Of course, this does not guarantee that this function is particularly "fast" per se, but in testing, the algorithm runs reasonable fast for all primitive integer types.

* It is important to note that the particular method used to achieve a Deterministic Miller Robin algorithm in polynomial time, technically depends on the Generalized Riemann Hypothesis. So I guess that means that for super huge numbers, this technically could give a false positive... ¯\_(ツ)_/¯ But hey, what else is there? The AKS Primality Test?