galois.is_prime

galois.is_prime(n)

Determines if \(n\) is prime.

Parameters

n (int) – A positive integer.

Returns

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

Return type

bool

Notes

This algorithm will first run Fermat’s primality test to check \(n\) for compositeness, see galois.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 galois.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