Determines if \(n\) is prime.

Parameters:¶

n: int¶

An integer.

Returns:¶

True if the integer \(n\) is prime.

Notes¶

This algorithm will first run Fermat’s primality test to check \(n\) for compositeness, see fermat_primality_test(). If it determines \(n\) is composite, the function will quickly return.

If Fermat’s primality test returns True, then \(n\) could be prime or pseudoprime. If so, then the algorithm will run 10 rounds of Miller-Rabin’s primality test, see miller_rabin_primality_test(). With this many rounds, a result of True should have high probability of \(n\) being a true prime, not a pseudoprime.

Examples¶

In [1]: galois.is_prime(13)
Out[1]: True

In [2]: galois.is_prime(15)
Out[2]: False

The algorithm is also efficient on very large \(n\).

In [3]: galois.is_prime(1000000000000000035000061)
Out[3]: True