Am 12 Feb 2007 um 21:14 hat RalfGesellensetter geschrieben:
> ifactors(2^216091-1);
>
> I suppose that this Mersenne prime of 65,050 digits was just too huge.
Yes, Ralf,
Maxma isn't the right tool for hunting big Mersenne primes.
Calling ifactors with a prime argument is the same as doing a test for primality, which is
primep. primep performs by default 25 strong-pseudoprime-tests (miller-rabin) followed by
one lucas-pseudoprime-test. These tests are quite fast for primes of a size up to a few
thousand bits, suitable for applications like RSA, but nothing more.
You can be 10 times faster if you screw the (undocumented) variable
primep_number_of_tests down to 1. Then primep is doing just one miller-rabin and one
lucas-test, which might be enough, because AFAIK there is no non-prime known, which
passes both tests. But nevertheless this doesn't help, if you which to find a new Mersenne
number.
Mersenne primes are so absolutely big, because they can be found by a simple, fast and
very special algorithm, known as lucas-lehmer-test. I add here a possible Maxima
implementation, which I tested on my 1,6 GHz notebook. Mersenne no 31 was proved within
one hour.
I have never tried it, but I suppose, that a C++-based bignum-library like GMP will be a
faster tool to go further on. Or directly google for GIMPS.
Hope it helps
Volker van Nek
(%i17) to_lisp();
Type (to-maxima) to restart, ($quit) to quit Maxima.
MAXIMA> (defun $mersennep (n)
(if (integerp n)
(cond
((= n 2) t)
((and (> n 2) (primep n))
(let ((m (1- (expt 2 n)))
(v 4))
(do ((k 1 (1+ k)))
((= k (1- n)) (= 0 v))
(setq v (mod (- (* v v) 2) m)) ))))
(merror "Non-integer argument to `mersennep'.") ))
$MERSENNEP
MAXIMA> (compile '$mersennep)
Compiling C:/DOKUME~1/VOLKER~1/LOKALE~1/Temp/gazonk_364_0.lsp.
End of Pass 1.
End of Pass 2.
OPTIMIZE levels: Safety=2, Space=3, Speed=2
Finished compiling C:/DOKUME~1/VOLKER~1/LOKALE~1/Temp/gazonk_364_0.lsp.
#<compiled-function $MERSENNEP>
MAXIMA> (to-maxima)
Returning to Maxima
(%o17) true
(%i18) mersennep(132049);
(%o18) true
(%i19) time(%o18);
(%o19) [3700.82]