The default integer factoring algorithm in maxima is just trial
divisions. This works for factors up to about 10 digits. The ifactor
package also implements pollard's rho method and elliptic curve
method. It finds factors up to about 20 digits in reasonable time.
Factoring methods use random variables, so you should really be timing
how much it takes to factor some number on avarage, not just in one
run.
If you set ifactor_verbose variable to true, the algorithm will
display the factors as it finds them (and tell if they are prime).
Andrej
2006/2/1, Robert Dodier <robert.dodier at gmail.com>:
> 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>
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>