From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.symbolic
Subject: Bizarre Maple integer factoring blind spot
Date: 27 Feb 1997 14:46:36 GMT

I wrote a maple program which inexplicably became trapped for hours;
I finally traced the problem to this:

subshell 3 > maple
    |\^/|     Maple V Release 3 (N I U)
._|\|   |/|_. Copyright (c) 1981-1994 by Waterloo Maple Software and the
 \  MAPLE  /  University of Waterloo. All rights reserved. Maple and Maple V
 <____ ____>  are registered trademarks of Waterloo Maple Software.
      |       Type ? for help.
> ifactor(3511^2);
bytes used=10001380, alloc=1507052, time=57.07

(etc..)

To be able to trace the error to this point requires being number-theoretically
literate: p=3511 is one of only two known primes with  2^(p-1)=1 mod p^2.
The other is p=1093, but maple has no problem with  ifactor(1093^2);  since
ifactor begins with a trial division by all the primes through 1700.
Maple also has no problem factorizing numbers divisible by 3511 only to the
first power, or numbers divisible by  3511^3. 

I'm not sure of the most efficient fix. Because of ifactor's  "remember" 
option, typing  ifactor(3511^2):=ifactor(3511)^2;  will cure this particular
problem, but that doesn't seem to help with  ifactor(2*3511^2)  and so on.
It seems a little difficult to write a preprocessor for  ifactor  to look
for this prime, since  ifactor  begins with a generous type-sorter
(e.g.  ifactor(a/b), ifactor([a,b]), etc. are all allowed).

"Will wonders never cease!"

dave