GAP Manual: 10.16. IsPrimeInt

IsPrimeInt( n )

IsPrimeInt returns false if it can prove that n is composite and true otherwise. By convention IsPrimeInt(0) = IsPrimeInt(1) = false and we define IsPrimeInt( -n ) = IsPrimeInt( n ).

IsPrimeInt will return true for all prime n. IsPrimeInt will return false for all composite n < 10^(13) and for all composite n that have a factor p < 1000. So for integers n < 10^(13), IsPrimeInt is a proper primality test. It is conceivable that IsPrimeInt may return true for some composite n > 10^(13), but no such n is currently known. So for integers n > 10^(13), IsPrimeInt is a probable-primality test. If composites that fool IsPrimeInt do exist, they would be extremly rare, and finding one by pure chance is less likely than finding a bug in GAP.

IsPrimeInt is a deterministic algorithm, i.e., the computations involve no random numbers, and repeated calls will always return the same result. IsPrimeInt first does trial divisions by the primes less than 1000. Then it tests that n is a strong pseudoprime w.r.t. the base 2. Finally it tests whether n is a Lucas pseudoprime w.r.t. the smallest quadratic nonresidue of n. A better description can be found in the comment in the library file integer.g.

The time taken by IsPrimeInt is approximately proportional to the third power of the number of digits of n. Testing numbers with several hundreds digits is quite feasible.

    gap> IsPrimeInt( 2^31 - 1 );
    true
    gap> IsPrimeInt( 10^42 + 1 );
    false