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 returnsTrue
, then \(n\) could be prime or pseudoprime. If so, then the algorithm will run seven rounds of Miller-Rabin’s primality test, seegalois.is_prime_miller_rabin
. 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 [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