Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Lucas-Lehmer Test

  1. Oct 13, 2004 #1

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    I'm trying to come up with a program that works out Mersenne prime numbers, I've successfully managed to get one to work that brute force attacks the problem and gets me up to 2^2281 - 1 as about the highest prime I can get with the computer still running fine.

    I've been reading up and it seems one of the best ways is to use the Lucas-Lehmer Test (http://mathworld.wolfram.com/Lucas-LehmerTest.html) however I am fairly new to matlab and don't quite seem to get it to work. Could anyone give me some points where I am going wrong please.

    (Below is code I have used to test if 2^p - 1 is prime or not)
    (z records the biggest value of p such that 2^p - 1 is prime)
    Code (Text):

    p=sym(2)

    for p=2:100
        if issymprime(p)==sym('true')
            s = 4
            for s=4:(p-2)
                s = mod(s^2 - 2,2^p -1)
            end
            if s==mod(0,2^p-1)
                z=p
            end
        end
    end
     
     
  2. jcsd
  3. Oct 13, 2004 #2

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    O.K just noticed a huge mistake in my programming, but can I leave the thread here for a sec in case it is still horribly wrong?
     
  4. Oct 13, 2004 #3

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Really sorry for the triple post but I've got it to work with a slight problem:

    Code (Text):

    p=sym(2)

    for p=2:40
        if issymprime(p)==sym('true')
            s = 1
            r = 4
            for s=1:(p-2)
                r = mod(r^2 - 2,2^p -1)
            end
            if r==mod(0,2^p-1)
                z=p
            end
        end
    end
     
    That works, up to about 2^19 - 1, however after that it doesn't seem to pick anymore Mersenne prime numbers up. Could someone tell me what to do please.
     
    Last edited: Oct 13, 2004
  5. Oct 14, 2004 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Hi, I think your problem is with how matlab stores data, it uses double precision variables, which are 64-bits and accurate to 15 decimal places or so. When computing your r's for p=31, at one stage you calculate 1416317953^2-2, which has 18 digits, before reducing mod 2^31-1. This is where your program bites it.

    You can probably have it compute 1416317953^2-2 in pieces, reducing mod 2^31-1 each time. There is also an integer type, but I believe it only goes to 32 bits, not enough for you.

    I don't have much experience with large integer operations in matlab, so I don't know if there's a clever way around this. On the other hand, Maple is quite capable of handling things like this.
     
  6. Oct 15, 2004 #5

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Thanks, I thought that was my problem and managed to come up with a maple solution. My lecturer has already made some functions for us that can handle symbolic input including a round() function which seems to work great and does so by using a couple of maple functions :smile:

    Anyway it isn't quite as fast as I hoped but I can probably change that over time when I get to know matlab a bit better.
     
  7. Oct 15, 2004 #6
    Look at GIMPS

    Hi,
    You should have a look at the GIMPS project: http://www.mersenne.org/ .
    You'll find useful information and a very fast program on ia32/Windows machines.
    You could also use the GLucas program for Unix machines. It is multi-threaded.
    About the theory, look at Ribenboim's book: "The little book of bigger primes" or at Williams' book: "Edouard Lucas and Primality Testing".
    Does Mathlab use FFT for multiplying big numbers ?
    Regards,
    Tony
     
  8. Oct 15, 2004 #7

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Thanks, with time I could work a much faster algorithm but I had to submit what I had today.

    Unfortunatly I have little understanding of how MatLab works at the moment, but I will look in to it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Lucas-Lehmer Test
  1. Grading Tests (Replies: 17)

  2. Testing for symmetry (Replies: 9)

  3. Failing tests (Replies: 2)

Loading...