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
GAP 3.4.4