Matthew Johnson wrote in his e-mail message of 1996/02/01

However, the following bug also appears under the Mac and NextStep builds
of the same version of the kernel and relevant libraries. The bug is
largely explained in the comments of the code, but I will say here that
removing the call to IsPrimeInt() makes the problem go away; I will also
say that the crash may appear with a quite different error message if any
other code is added to the loop or if run under the Mac or NextStep
versions: under NextStep (a GUI-enhanced MACH UNIX) I usually get a
"Segmentation Fault", under NT I usually get a "STack Overflow" (but
occasionally as in NExtStep), under MacOS 7.5 I get Segmentation Fault.

Burkhard Hoefling wrote in his e-mail message of 1996/02/05

The reason for Mathew's problem is simply a stack overflow, caused by
performing prime tests on large integers (large strong pseudoprimes for
the base 2, to be more precise).

It is correct that 'IsPrimeInt' uses quite a bit of stack space.
'IsPrimeInt' uses a Lucas pseudoprime test for integers that have no
factor less than 1000 and which are strong pseudoprimes for the base 2.
This test computes the trace of an element recursively, where the depth
of the recursion is roughly the number of bits of the tested integer.

What surprises me is that the problem reportedly happens under NextStep.
NextStep should give each process more stack space than what is needed
for 'IsPrimeInt( Fibonacci( 2971 ) );'.

Burkhard continued

In so far, the GAP manual is wrong in claiming that IsPrimeInt can test
numbers with "a few hundred digits".

Well, 'IsPrimeInt' *can* test 'Fibonacci( 2971 )'. But of course it
needs enough resources. On the machine under my desk (a Pentium@90MHz
under FreeBSD 2.1) it needs about 280 KByte stack, 500 KByte heap, and it
takes about 80 seconds.

Burkhard continued

To be more technical, IsPrimeInt performs various prime tests (see the
manual and the documentation in Integer.g for details), and the 2971th
Fibonacci number is the first to pass all tests except for the last one
(to be more precise, it is a strong pseudoprime for the base 2). The last
(probabilistic) prime test uses recursion to check whether a number is a
prime, and for the 2971th Fibonacci number, this would require a
recursion depth of about 2600, each call requiring about 160 bytes on my
Macintosh this should be system dependent. Thus a (program) stack of
about 400 Kilobytes would be required for this calculation, while the
usual stack size for GAP seems to be about 64 Kilobytes.

To be precise. 'Fibonacci(2971)' is not the first Fibonacci number that
passes all tests except the last one. The following numbers also pass
all tests except the last one (in fact all also pass the last one too):
3,4,5,7,11,13,17,23,29,43,47,83,131,137,359,431,433,449,509,569,571.
But apparently they are not large enough to trigger this problem.
The recursion depth for 'Fibonacci(2971)', by the way, is 2063.

Burkhard continued

- Since this phenomenon is very likely to occur also in other contexts,
GAP should check whether there is still enough processor stack space when
doing a (recursive) function call. This is, of course, system dependent,
and there should be a function in the system dependent part of GAP which
would then be called before every function call. This, of course, does
not resolve the problem with IsPrimeInt, but it helps finding such
problems.

The problem with that is, that it would slow down GAP function calls.
For many computations the speed of function calls is critical for the
overall speed. But it could be a compile time option.

Also finding out how much stack space is available and how much is used
for each function frame is very system dependent.

Note that on UNIX workstations this is generally not such a problem.
They provide much (virtual) stack space. Also, if you exhaust the stack
you don't overwrite the heap (I think this is what happens on the Mac).
Instead the GAP kernel is terminated, which is bad enough of course,
but that can't lead to undetected errors.

Burkhard continued

- Perhaps it is useful to use another prime test. For example, as far as
I remember from my lectures on number theory, a reasonable solution is to
pick r positive integers n_1, ... n_r at random, and to check whether the
number p in question is a strong pseudoprime with respect to all the
numbers n_1, ... , n_r. Choosing the number r large enough, the
probability that p is not a prime can be made as close to zero as
desired. (But don't quote me on the details ...).

The combination of an ordinary pseudoprime test and a Lucas test (as used
in GAP) is generally considered to be stronger than a number of repeated
ordinary pseudoprime tests. One reason is, that an integer that is a
pseudoprime w.r.t. one base is quite likely a pseudoprime w.r.t. other
bases as well. There are known integers that are pseudoprimes w.r.t. to
all bases less than 100. But there are no known integers that fool the
combined test used by GAP.

Furthermore the algorithm used by GAP's 'IsPrime' is not per se
recursive. Only the current implementation of the function 'TraceModQF'
is recursive. This could be replaced by a non-recursive implementation.

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany