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 ```

GAP 3.4.4
April 1997