[GAP Forum] IsPrime

[Frank Lübeck]

On Thu, Jun 09, 2005 at 02:28:57PM +0700, Vdovin Evgenii wrote:
> I wonder if anybody knows what algorithm is used in GAP to check whether
> a given integer is prime.  Does anybody know another program that can
> check whether a given integer is prime? Now I'm considering a prime
> p=2^44497-1 and the problem is to check if p^2-p+1 is prime.

Dear Forum, dear Vdovin Evgenii,

I have already given a hint to Vdovin that the number p^2-p+1  above
is divisible by 2797. This can be found by trial division and one does not
even need to expand the number p:
  l := 2797;
  pp := PowerMod(2, 44497, l)-1;
  (pp^2 - pp + 1) mod l;
  
But let me add a few remarks on the current 'IsPrimeInt(n);' in GAP:
This performs only tests for "probable primes", this means if the answer is
'false' then the number n is composite, but if the answer is 'true' then n
still may be composite (each prime n yields the answer 'true'). But as far as I
know no composite n is explicitly known for which our test yields 'true'
(nevertheless, it is expected that such n exist).

It is known that for 1 < n < 10^13 the test in GAP returns 'true' if and
only if n is prime. A detailed description of the algorithm is in the
file lib/integer.gi in the GAP distribution (search for "#F  IsPrimeInt").

There exist algorithms (APR-CL, ECPP, ...) which can practically prove the
primality of (random) integers with up to a few thousand  digits.
(If someone implemented such an algorithm in GAP we would be very
interested!)

The primality of the  much bigger number p above (with more than 
13000 digits) can be shown using its special structure (it is a "small"  
Mersenne prime). But such a function is not contained in the GAP library.

With a small change of the GAP library (which will be put in the next update
of GAP) the 'IsPrimeInt(p);' runs about 90 minutes on my machine; a demo
coming with GMP, a package for fast integer arithmetic, needs 20 minutes for
a Miller-Rabin test.  So, testing of "probable primality" of numbers of this
size is doable, but not for much bigger numbers.

Best regards,

  Frank

-- 
///  Dr. Frank Lübeck, Lehrstuhl D für Mathematik, Templergraben 64,  ///
\\\                    52062 Aachen, Germany                          \\\
///  E-mail: Frank.Luebeck at Math.RWTH-Aachen.De                        ///
\\\  WWW:    http://www.math.rwth-aachen.de/~Frank.Luebeck/           \\\