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