galois.is_prime¶

galois.is_prime(n: int) → bool¶

Determines if \(n\) is prime.

Parameters

n: int¶

An integer.

Returns

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

See also

is_composite, is_prime_power, is_perfect_power

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