Lucas-Lehmer Test

[ATH]

Originally Posted by storm5510

2^P - 1, where P is any even number

p stands for prime, so its not even except for p=2. Think of it as:

2^prime-1


Here is the proof that exponent has to be prime for 2^p-1 can be prime:
http://primes.utm.edu/notes/proofs/Theorem2.html

[fivemack]

Originally Posted by storm5510

Be it stupid, or not, here's what I am looking for:

I have an application which I can punch a number into. The purpose is to see if it is a prime number. It doesn't matter what type.

The conventional way is to iterate all the way up to the square root of said number in steps of two, starting at three, while skipping multiples of five.

This can be time consuming if a very large number is entered. Is there a more time-efficient method?

Yes, there are many; some which prove that the number is prime and some which have an incredibly tiny probability of calling some composite numbers prime. All of them define a group whose order is known if the number is prime and then try to demonstrate that the group has the claimed order.

http://www.mersennewiki.org/index.php/Primality_test is probably a good place to start.

Implementing the easy algorithms is straightforward, but the hard ones can get really quite fiddly; fortunately a group at the University of Bordeaux produced pari-gp, where you can type

? isprime(83^57+318)
%4 = 1
? nextprime(10^1000)-10^1000
time = 2,785 ms.
%5 = 453

[TimSorbet]

Also, Wikipedia in general and this template in particular is a great source of info regarding primality tests, etc.
http://en.wikipedia.org/wiki/Templat...tic_algorithms

[R.D. Silverman]

Originally Posted by storm5510

Be it stupid, or not, here's what I am looking for:

I have an application which I can punch a number into. The purpose is to see if it is a prime number. It doesn't matter what type.

The conventional way is to iterate all the way up to the square root of said number in steps of two, starting at three, while skipping multiples of five.

This is NOT the conventional way.

Is doing a google search too much work? There is a LOT of
information available.

[TimSorbet]

Originally Posted by R.D. Silverman

This is NOT the conventional way.

Replace "conventional" with "naive" or "obvious" or "simple" or ...

[R.D. Silverman]

Originally Posted by storm5510

2^P - 1, where P is any even number. Subtract 1 and it becomes odd, then an exponent of 2.

3, 7, 15, 31, 63, 127, 255 .... 2097151, 4194303, so forth, and so on, what not, and what have you.

...

Still clueless, I see. Even after you have been TOLD what a
Mersenne number is, you still haven't gotten it right.

Firstly, you state that P is an even number! then your example:
"3, 7, 15, 31, 63, 127, 255 .... 2097151, 4194303, so forth"

gives instances where P is odd!!! Don't you even know the difference
between odd and even??? One has to be a total moron to state that
a Mersenne number is 2^P-1, where P is EVEN, then to
immediately give a numerical example where P is ODD.


And the expression "Subract 1 and it becomes odd, then an exponent of 2"
is GIBBERISH. The phrase "then an exponent of 2" is NONSENSE.

A Mersenne number is a number of the form 2^p-1, where p is PRIME
(i.e. not even, except for p=2).

And, of course, it is clear that you never learned basic first year
junior high school algebra. 2^(2k) - 1 can NEVER be prime, except for
k = 1. It is the difference of two squares. Where you got the idea
that it might ever be prime, I have no idea.

Give it up. You lack even the basic math background to dabble in this
subject and you appear to be too lazy to do even a simple web search
on "prime algorithms". Go back to grammar school. Come back here
when you are ready to exhibit some scholarly discipline.

[Dougal]

if i make a statement,which is wrong.then give several examples of it which are right,i think you would have to be a moron to think that i gave correct examples without knowing what i was talking about.my statement could of been worded wrong quite easily,and i think his example shows quite clearly what a mersenne number is,even if the statement was worded incorrect,possibly by accident.

[Dougal]

also,one of the definitions of a mersenne number is that p is prime.another is that p is a positive integer.i could easily accuse you of not knowing your definitions.

[R.D. Silverman]

Originally Posted by Dougal

if i make a statement,which is wrong.then give several examples of it which are right,

Also mixed in are clear examples that are wrong. Which basically
shows that what is being written is just random nonsense.

i think you would have to be a moron to think that i gave correct examplse without knowing what i was talking about.my statement could of been worded wrong quite easily,and i think his example shows quite clearly what a mersenne number is,even if the statement was worded incorrect,possibly by accident.

Another imbecile. And you apparently do not know:

(1) Sentences are capitalized.
(2) The word "I" is capitalized.
(3) How to spell.
(4) Basic grammar: "could of been" --> "could have been"
(Although I will give the benefit of the doubt here. English may
not be your first language; If it is your first language, then you
are even dumber than I thought)
(5) Proper names (i.e. Mersenne) are capitalized.


Go away. Come back when you can write cogent sentences above
2nd grade level. Come back when you learn to read. Go back to school.
Study very hard. When your IQ reaches 75, SELL. You will make a profit.

[CRGreathouse]

Originally Posted by R.D. Silverman

(5) Proper names (i.e. Mersenne) are capitalized.

((Insert joke about Abel here))

[T.Rex]

Originally Posted by fivemack

257 is not a number of the form 2^p-1, and the Lucas-Lehmer test is only defined for numbers of that form.

The LLT for Mersenne numbers, you mean to say. But if you use the LLT for Fermat numbers, that works !

Use s=5 as the seed, and do 2^n-2 steps. Since 257=2^8+1=2^(2^3)+1, you need 6 steps :

5 -> 23 -> -> 13 -> 167 -> 131 -> 197 -> 0 BINGO ! it's a prime ! (I knew that... :)

Look at the proof from this page.

Tony