galois.is_prime¶
-
galois.
is_prime
(n)[source]¶ Determines if \(n\) is prime.
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 returnsTrue
, then \(n\) could be prime or pseudoprime. If so, then the algorithm will run seven rounds of Miller-Rabin’s primality test, seegalois.miller_rabin_primality_test
. With this many rounds, a result ofTrue
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
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