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