Lucas-Lehmer

[Dougal]

Can someone please explain the test to me because i dont understand it properly.For example M3, works like this, (4^2)-2 mod 7, so thats 14/7=2,no remainder,so its prime

But wikipedia shows this

On the other hand, M11 = 2047 = 23 × 89 is not prime. To show this, we start with s set to 4 and update it 11−2 = 9 times, taking the results mod 2047:

• s ← ((4 × 4) − 2) mod 2047 = 14

What i dont understand is where the 14 comes from

Thanks

[10metreh]

Originally Posted by Dougal

Can someone please explain the test to me because i dont understand it properly.For example M3, works like this, (4^2)-2 mod 7, so thats 14/7=2,no remainder,so its prime

But wikipedia shows this


On the other hand, M11 = 2047 = 23 × 89 is not prime. To show this, we start with s set to 4 and update it 11−2 = 9 times, taking the results mod 2047:

• s ← ((4 × 4) − 2) mod 2047 = 14

What i dont understand is where the 14 comes from

Thanks

((4 x 4) - 2) = 14
(14) mod 2047 = 14

Do you understand what "mod" means? (And it's not "moderator" in this case.)

[Dougal]

i checked it on wikipedia and it said something about A mod N means the remainder of a/n.so what i thought it meant was 2047/14 and the remainder was 14,but that isnt possible,however i understand it now,its (4^2)-2=14,then you do this 11-2 times and when you get that far if,lets say x doesnt divide 2047 evenly then the number isnt prime.would that be right?(if you can make any sense out of my rambling).for mersenne numbers,you start with 4^2-2,how do you get the starting number for the llr test?

Actually i looked further through it and it appears i still dont have a clue

Thanks

[petrw1]

Originally Posted by Dougal

Actually i looked further through it and it appears i still dont have a clue

Thanks

Does George's example here help: http://www.mersenne.org/various/math.php

[Dougal]

Sorry petrw1,doesnt seem to help much,maybe if i understood mod i'd understand it.Thanks anyway.i've done alot of messing about on a calculator and i now understand it.dont understand how you find out what number you start of with for llr.

[Mr. P-1]

Originally Posted by Dougal

i thought it meant was 2047/14 and the remainder was 14

You have it backwards. 14 mod 2047 is the remainder of 14/2047.

[Dougal]

sorry,thats what i meant,i understand it now,just not the riesel version of it.

[cheesehead]

Originally Posted by Dougal

sorry,thats what i meant,i understand it now,just not the riesel version of it.

I advise you, as a beginner, to just skip the parts about Riesel or LLR and not worry about it.

GIMPS is concerned with Mersenne (that's the "M" in "GIMPS"!) numbers. Riesel numbers are something else; some folks in GIMPS may also be interested in Riesel numbers, but there's no "R" in "GIMPS", so it's a side subject.

(There is a connection between Mersenne numbers and Riesel numbers ... but there are connections between all numbers!!)

[Dougal]

Thanks cheesehead(i think).
Well if you think it would be a bit advanced for me then il leave it a while,But if anyones willing to try teach me id appreciate it.

[ATH]

M11:

S₀=4
S₁=(4²-2) mod 2047 = 14 mod 2047 = 14
S₂=(14²-2) mod 2047 = 194 mod 2047 = 194
S₃=(194²-2) mod 2047 = 37634 mod 2047 = 788
S₄=(788²-2) mod 2047 = 620942 mod 2047 = 701
S₅=(701²-2) mod 2047 = 491399 mod 2047 = 119
S₆=(119²-2) mod 2047 = 14159 mod 2047 = 1877
S₇=(1877²-2) mod 2047 = 3523127 mod 2047 = 240
S₈=(240²-2) mod 2047 = 57598 mod 2047 = 282
S₉=(282²-2) mod 2047 = 79522 mod 2047 = 1736

Since S_n-2=S₉ != 0 then M11 is not prime.