Hello all,
Here is a message from Hans Joksch about factoring large integers with Maxima.
Maybe someone can comment on this topic.
I've mentioned to Hans the Miller-Rabin code.
(http://cvs.sf.net/viewcvs.py/*checkout*/maxima/maxima/share/contrib/ifactor.lisp)
Maybe factor should call ifactor in some circumstances? Just a thought.
all the best,
Robert Dodier
------------------------- begin forwarded message from Hans Joksch
-------------------------
Comparing factoring numbers by Maxima 5.9.2 and Derive 4.
I have Maxima 5.9.2 on an Aurox 9.2 (clone of Red Hat 9) Linux
partition, and Derive 4 on a PC-DOS 7 Partition on the same computer
with an Athlon 2200 CPU and 512MB RAM.
To test the factoring algorithms, I used numbers consisting entirely
of the digit "1"; let's define 1(n) as a number consisting of n times
the "1".
For n=1 ... 40, Derive factored (it also "factored" the prime numbers
1(19) and 1(23)) most numbers "instantaneously", as indicated by
observation, and its own clock which shows computation time in 0.1
sec. Exceptions were:
1(17), 0.1 sec, a product of a 7- and a 10-digit number
1(34), 0.6 sec, containing a 7-, a 10-, and an 11-digit factor
1(37), 0.2 sec, a product of a 7-, a 9-, and a 22 digit number
1(39), 0.4 sec, containing a 9- and a 24-digit factor
1(40), 0.2 sec, containing a 7- and a 10-digit factor.
1(38) was a remarkable exception: the program ran 4h 25min until I
interrupted it. It is obvious that
11111111111111111111111111111111111111
=1111111111111111111*10000000000000000001.
Derive found instantaneously that the first factor, 1(19) is prime,
and it also found instantaneously that
10000000000000000001=11*909090909090909091. It is surprising that it
would have taken over 4h 25min to combine the two. Even instructing
the program to factor the expression
1111111111111111111*10000000000000000001 did not give a faster result.
Incidentally, many of the factors with an even numer of digits had the
property that the first and the second half added gave a power of 10:
37, 73, 9091, 333667, 909091, 99990001, 999999000001,
909090909090909091, 900900900900990990990991.
Up to 1(16), Maxima also factored practically instantaneously.
Thereafter, the following differences appeared:
1(17), just less than 1 sec, much more than 0.1 sec, a product of a 7-
and a 10-digit number
1(19), a prime number: I interrupted after 2 min calculation
1(23), a prime number: I interrupted after 2 min calculation
1(26), 130 sec, contains a 10- and a 19-digit factor
1(27), 11 sec, contains a 15-digit factor
1(31), I interrupted after 15 min, contains a 20-didgit factor
1(33), I interrupted after 9 min, a 19-digit factor
1(34), I interrupted after 2.5 min, contains a 7-, a 10-, and an 11-digit factor
1(35), I interrupted after 2 min, contains an 18-digit factor
1(36), <1 sec, but not "instantaneously", the largest factor has 12 digits
1(37), I interrupted after 3 hours, contains a 7-, a 9-, and a
22-digit factor - Derive factored this in 0.2 sec!
1(38), I interrupted after 10 min
1(39), I interrupted after 4 min, contains a 24-digit factor
1(40), <1 sec, but not instantaneously, the largest factor has 10 digits.
It appears that Maxima and Derive both factor practically
instantaneously if the largest factor has fewer than 10-12 digits
(except if there are more than one "large" factor). With a factor
with more than 12 digits, Maxima is much slower.
I also tried to factor 2^(2^n)+1. Here are the results
n Derive Maxima
5 <0.1 sec instantaneous
6 <0.1 sec 4 sec
7 I interrupted after 15 min 5 min
The value for n=7 is the product of a 17- and a 22-digit prime.
I suspect that these differences were known to the author of the
"Micro introduction into Maxima" (Computing%20Harvard%20Math%).
There, "factor(2^(2^5)+1);" is given as an example of Number theory,
"factor(2^(2^7)+1); c" as an example for Interrupting computation.
In the 1990s, I considered buying Macsyma. I compared a demo version
with Derive 4 and Mathcad 4. Mathcad was slightly slower than Derive,
but Macsyma was dramatically slower - I don't recall exactly, but on
the average it was about 3-10 times. Macsyma support staff explained
that they were aware that they had a slow algorithm, but hoped to have
a better one in a later version.
Of course, the ideal would be to have in Maxima an algorithm as fast
as in Derive. More modest but still useful would be an algorithm
which shows the factors one by one as they are being calculated. That
way, one might have at least some factors when one has to interrupt
the calculation, and could continue at another occasion. I would also
be very useful if there were an indication that the argument is a
prime. Currently it seems to be that one can not distinguish between
a prime number, and a number which has been partially factored, when
one interrupts the process.
Hans Joksch <hjoksch at att.net>