>>>>> "Robert" == Robert Dodier <robert.dodier at gmail.com> writes:
Robert> Hello all,
Robert> Here is a message from Hans Joksch about factoring large integers with Maxima.
Robert> Maybe someone can comment on this topic.
Robert> I've mentioned to Hans the Miller-Rabin code.
Robert> (http://cvs.sf.net/viewcvs.py/*checkout*/maxima/maxima/share/contrib/ifactor.lisp)
Robert> Maybe factor should call ifactor in some circumstances? Just a thought.
That's not a bad idea. Or just replace factor with ifactor?
Robert> 1(38) was a remarkable exception: the program ran 4h 25min until I
Robert> interrupted it. It is obvious that
FWIW, ifactor on 1 GHz sparc with cmucl found that 1(38) has 3 factors
in 98 sec. (I compiled ifactor first. This probably helps quite a
bit with cmucl.)
Robert> Up to 1(16), Maxima also factored practically instantaneously.
Robert> Thereafter, the following differences appeared:
Robert> 1(17), just less than 1 sec, much more than 0.1 sec, a product of a 7-
Robert> and a 10-digit number
Robert> 1(31), I interrupted after 15 min, contains a 20-didgit factor
0.1 sec.
Robert> 1(33), I interrupted after 9 min, a 19-digit factor
0.08 sec
Robert> 1(34), I interrupted after 2.5 min, contains a 7-, a 10-, and an 11-digit factor
2.68 sec
Robert> 1(37), I interrupted after 3 hours, contains a 7-, a 9-, and a
Robert> 22-digit factor - Derive factored this in 0.2 sec!
1.52 sec. Slow compared to Derive, but not 3 hours. :-)
Robert> I also tried to factor 2^(2^n)+1. Here are the results
Robert> n Derive Maxima
Robert> 5 <0.1 sec instantaneous
Robert> 6 <0.1 sec 4 sec
Robert> 7 I interrupted after 15 min 5 min
n=7 took 58 sec.
ifactor seems quite nice.
Ray