Mersenne primes, was: factor



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]