mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2016-09-15, 05:46   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

26·31 Posts
Default Can you make mew understand the LLR Test?

Hi,
I am not too lazy to Google for a proof.
I am however too busy to decipher it to see why it works.
I figure if anyone can put it in layman's terms that I could comprehend, then she/he is got to be a member here.
Any insights as to why the LLR Test works would be greatly appreciated.

Thanks in advance.

ETA the swipes keyboard topped "new" instead of "me" in the title.

Last fiddled with by a1call on 2016-09-15 at 05:49
a1call is offline   Reply With Quote
Old 2016-09-15, 11:29   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·2,909 Posts
Default

I would try to understand the LL test first.
henryzz is online now   Reply With Quote
Old 2016-09-15, 11:45   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

37·97 Posts
Default

http://primes.utm.edu/prove/index.html is a good starting point

Last fiddled with by paulunderwood on 2016-09-15 at 11:47
paulunderwood is offline   Reply With Quote
Old 2016-09-15, 12:17   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by a1call View Post
Hi,
I am not too lazy to Google for a proof.
I am however too busy to decipher it to see why it works.
I figure if anyone can put it in layman's terms that I could comprehend, then she/he is got to be a member here.
Any insights as to why the LLR Test works would be greatly appreciated.

Thanks in advance.

ETA the swipes keyboard topped "new" instead of "me" in the title.
it's not that people here couldn't most likely but without a basic understanding of the context involved the wording would have to get almost arbitrarily large.

for example the wikipedia talks about groups do you know what these are if not they are a set along with a binary relation, satisfying specific axioms. what's a binary relation you ask well it's a operation between two things. what are axioms ? and which of them does it have to fit ? and wikipedia on how it works talks about orders of a group what is the order of a group ? without knowing the how it's potentially impossible to have a good grasp on the why.
science_man_88 is offline   Reply With Quote
Old 2016-09-15, 12:56   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5·17·109 Posts
Default

Quote:
Originally Posted by henryzz View Post
I would try to understand the LL test first.
Yes. And reading about Lucas Sequences and divisibility sequences in general, may help.
LaurV is offline   Reply With Quote
Old 2016-09-15, 19:02   #6
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

24×101 Posts
Default

Another good reference is Bas Jansen's PhD thesis:
http://www.math.leidenuniv.nl/scripties/PhDJansen.pdf

Note: it begins with a summary in Dutch, but the main body of the document is in English.
Nick is online now   Reply With Quote
Old 2016-09-15, 22:45   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

26×31 Posts
Default

Thank you very much for all the expert and undoubtedly excellent insights and links.
I will be working straight through the weekend, but I am watching this thread.
Others with the same question and phrasing will end up here as well by googling, so thanks to all.
a1call is offline   Reply With Quote
Old 2016-09-18, 18:53   #8
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

Quote:
Originally Posted by a1call View Post
Hi,
I am not too lazy to Google for a proof.
I am however too busy to decipher it to see why it works.
I figure if anyone can put it in layman's terms that I could comprehend, then she/he is got to be a member here.
Any insights as to why the LLR Test works would be greatly appreciated.

Thanks in advance.

ETA the swipes keyboard topped "new" instead of "me" in the title.
"Lucasian Criteria for the Primality of N = h.2n-1" by Hans Riesel

Quote:
Originally Posted by Raman
LUCAS LEHMER RIESEL TEST

The Lucas Lehmer Test can be extended further to prove that numbers of the form
p = h.2n-1 are prime, where h < 2n. It depends upon choosing a clever value for S1.

If h = 1, then S1 = 4 will hold for all odd values of n, and S1 = 3 will hold for all n ≡ 3 (mod 4)

If h = 3, then S1 = 5778 can be used for all n ≡ 0, 3 (mod 4)

If h = 6k ± 1, k is an integer, then S1 = (2 + √3)h + (2 - √3)h can be used for all the values

of n. Note that, here we use the value of P = 4 and Q = 1 and calculate the value of Vh.

Otherwise, we are left with the case where h is a multiple of 3, and we have to be more

careful in choosing the value of S1.

Try with v1 values starting from 3, and let D be the square free part of v12 - 4.

Let v1 = α + α-1, and so v1 satisfies the equation α2 - v1α + 1 = 0.

Now, that the values of a and r are obtained from the following equations:

a = (a + b√D)2/r and r = |a2 - b2D|, b = 1 .

Let k = √[(v12 - 4)/D]. Then, α = [v1 + √(v12 - 4)]/2 = [v1 + k√D]/2.

This corresponds to [(a2 + b2D) + 2ab√D]/r. So, that now we can now easily solve for a

and r. These should satisfy the following equations:

(D/N) = -1, (r/N)(a2 - b2D)/r = -1. If not choose a different value for v1.

Then, the starting value S1 is taken to be αh + α-h, that is Vh with P = V1 and Q = 1,
satisfying the Lucas equation x2 - Px + Q = 0. The value of Vh can be calculated by using
the following recurrence equations.
V0 = 2, V1 = P, Vn = PVn-1 - QVn-2 for all n ≥ 2. V2n = Vn2 - 2Qn, V2n-1 = VnVn-1 - PQn-1.
Raman is offline   Reply With Quote
Old 2016-09-20, 21:10   #9
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

26·31 Posts
Default

"Can you make mew"
Very funny Batalov.
That actually put a smile on my face after a long day.

Last fiddled with by a1call on 2016-09-20 at 21:13
a1call is offline   Reply With Quote
Old 2016-09-20, 23:04   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·32·7·37 Posts
Default

I guess my swipes keyboard topps oneders, two!
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Make sound with on Error (Stress Test) Zerowalker Software 7 2017-12-22 00:53
Don't understand this mfaktc behavior Chuck GPU Computing 2 2011-06-18 17:24
Finally I understand EVERYTHING! Flatlander Lounge 2 2010-10-10 14:30
Don't understand instructions for upgrading to v25 John S Software 22 2008-11-10 21:20
I just don't understand this kuratkull Sierpinski/Riesel Base 5 2 2007-03-12 21:02

All times are UTC. The time now is 14:41.

Thu Feb 25 14:41:01 UTC 2021 up 84 days, 10:52, 0 users, load averages: 2.01, 3.19, 3.64

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.