galois.is_prime

class galois.is_prime(n)

Determines if \(n\) is prime.

This algorithm will first run Fermat’s primality test to check \(n\) for compositeness, see galois.is_prime_fermat. 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 seven rounds of Miller-Rabin’s primality test, see galois.is_prime_miller_rabin. With this many rounds, a result of True should have high probability of \(n\) being a true prime, not a pseudoprime.

Parameters

n (int) – A positive integer.

Returns

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

Return type

bool

Examples

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

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

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

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