mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2020-03-18, 14:35   #45
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

745610 Posts
Default

Quote:
Originally Posted by BrainStone View Post
Do I understand correctly that there are cases that consequently allow it to become 1?
Please. This is a math discussion. Learn to state exactly what you mean.

When you say "consequently", the obvious reply is "consequently to what?".


State mathematically what condition you mean. Math is not "casual English".

Do you not know what "order of an element [in a group]" means? It is a fundamental
concept that you need to learn. And you also need to learn Lagrange's Theorem
if you want to continue further.
R.D. Silverman is offline   Reply With Quote
Old 2020-03-18, 14:47   #46
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

745610 Posts
Default

Quote:
Originally Posted by kuratkull View Post
R.D. Silverman - I think you mixed me up with the OP. I am not trying to implement anything, I already did: https://github.com/dkull/rpt
Most of the stuff you commented on was left out/ignored for brevity. It bears no significant weight on the magnitude of the final calculation.
I think starting with a disclaimer and ending with a question about correctness leaves little room for arrogance.
Mea culpa if I confused you with someone else. My apology. Yet you made some clearly
incorrect mathematical statements.
R.D. Silverman is offline   Reply With Quote
Old 2020-03-18, 15:04   #47
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

126428 Posts
Default

In the spirit of this thread I also want to write an HLL version of the the LL test. Why not? Following is some awesome python code. And as a bonus it also does a PRP test.
Code:
for p in range(3, 1280, 2):
 mp, s = pow(2, p) - 1, 4
 for i in range(2, p): s = (s * s - 2) % mp
 if s == 0: print("2^{}-1 is prime".format(p))
 if pow(3, mp + 1, mp) == 9: print("2^{}-1 is PRP".format(p))
Can some help me to optimise it? I need it to run really really fast.
retina is online now   Reply With Quote
Old 2020-03-18, 15:41   #48
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

328210 Posts
Default

Quote:
Originally Posted by retina View Post
In the spirit of this thread I also want to write an HLL version of the the LL test. Why not? Following is some awesome python code. And as a bonus it also does a PRP test.
Code:
for p in range(3, 1280, 2):
 mp, s = pow(2, p) - 1, 4
 for i in range(2, p): s = (s * s - 2) % mp
 if s == 0: print("2^{}-1 is prime".format(p))
 if pow(3, mp + 1, mp) == 9: print("2^{}-1 is PRP".format(p))
Can some help me to optimise it? I need it to run really really fast.
print("3 5 7 13 17 19 31 61 89 107 127 521 607 1279")
paulunderwood is online now   Reply With Quote
Old 2020-03-18, 15:58   #49
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Please. This is a math discussion. Learn to state exactly what you mean.

When you say "consequently", the obvious reply is "consequently to what?".


State mathematically what condition you mean. Math is not "casual English".

Do you not know what "order of an element [in a group]" means? It is a fundamental
concept that you need to learn. And you also need to learn Lagrange's Theorem
if you want to continue further.
Is it possible that \(\exists S \left( n \right) \equiv 1 \mod M_p\), where
\(S \left( 1 \right) = 4 \\
S \left( n + 1 \right) = {S \left( n \right)}^2 - 2 \\
M_p = 2^p - 1 \\
n < p, n \in \mathbb{N}, p \in \mathbb{P}\)
BrainStone is offline   Reply With Quote
Old 2020-03-18, 17:19   #50
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×3×547 Posts
Default

Quote:
Originally Posted by BrainStone View Post
Is it possible that \(\exists S \left( n \right) \equiv 1 \mod M_p\), where
\(S \left( 1 \right) = 4 \\
S \left( n + 1 \right) = {S \left( n \right)}^2 - 2 \\
M_p = 2^p - 1 \\
n < p, n \in \mathbb{N}, p \in \mathbb{P}\)
M_2 = 3: S_1 is 4 == 1 mod 3.

If S_k^2-2 == 1 mod M_p would imply S_k^2 == 3 mod M_p, but 3 is a QNR over M_p for all prime p>2. Proof?

Last fiddled with by paulunderwood on 2020-03-18 at 17:23
paulunderwood is online now   Reply With Quote
Old 2020-03-18, 17:23   #51
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

2×712 Posts
Default

Quote:
Originally Posted by BrainStone View Post
What error did I do?
One error you have just made is to ignore the second and third options in my list. To jog your memory they werre "naivety" and "whatever".

Naivety is both inevitable and forgivable*; everyone is naive in any specific field until they learn not to be. Your naivety (in my opinion, others may differ) is in assuming that mathematicians invariably tolerate sloppy language when used to describe a problem which can be described precisely. Inherent in that sloppiness is a failure to distinguish clearly between the result of operators in programming languages and the mathematical concept of an equivalence class.

"Whatever" is harder to characterize. One thing in your favour is your adherence to one of the laws of optimization: First get it right, then get it fast. Perhaps if you had stated this up-front your post may have had a different outcome.

Quote:
Originally Posted by BrainStone View Post
That's just being rude and inappropriate.
Very likely so. Not everyone is polite.

---

* I've been getting all sorts of since I joined Twitter because my Asperger's makes it difficult for me to read sub-texts in tweets from neurotypicals. I have been trying hard to learn and I believe that I'm improving but it still trips me up all too often.
xilman is offline   Reply With Quote
Old 2020-03-18, 17:59   #52
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25·233 Posts
Default

Quote:
Originally Posted by BrainStone View Post
Is it possible that \(\exists S \left( n \right) \equiv 1 \mod M_p\), where
\(S \left( 1 \right) = 4 \\
S \left( n + 1 \right) = {S \left( n \right)}^2 - 2 \\
M_p = 2^p - 1 \\
n < p, n \in \mathbb{N}, p \in \mathbb{P}\)
Not if M_p is prime. If M_p is composite then 4 can generate a subgroup.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
A second proof for the Lucas-Lehmer Test carpetpool Miscellaneous Math 2 2017-07-30 09:21
Lucas-Lehmer test Mathsgirl Information & Answers 23 2014-12-10 16:25
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas Lehmer test question? BMgf Programming 23 2003-12-09 08:52

All times are UTC. The time now is 12:31.

Sat Jul 11 12:31:56 UTC 2020 up 108 days, 10:04, 0 users, load averages: 1.17, 1.31, 1.35

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.