mersenneforum.org Can the subtraction in the lucal lehmer test ever return a negative value?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2020-03-18, 14:35   #45
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by BrainStone 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.

2020-03-18, 14:47   #46
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by kuratkull 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.

 2020-03-18, 15:04 #47 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 3·112·17 Posts 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.
2020-03-18, 15:41   #48
paulunderwood

Sep 2002
Database er0rr

71608 Posts

Quote:
 Originally Posted by retina 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")

2020-03-18, 15:58   #49
BrainStone

Nov 2017
Karlsruhe, Germany

31 Posts

Quote:
 Originally Posted by R.D. Silverman 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}$$

2020-03-18, 17:19   #50
paulunderwood

Sep 2002
Database er0rr

24·3·7·11 Posts

Quote:
 Originally Posted by BrainStone 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

2020-03-18, 17:23   #51
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

29E416 Posts

Quote:
 Originally Posted by BrainStone 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 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.

2020-03-18, 17:59   #52
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by BrainStone 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 carpetpool Miscellaneous Math 2 2017-07-30 09:21 Mathsgirl Information & Answers 23 2014-12-10 16:25 storm5510 Math 22 2009-09-24 22:32 BMgf Programming 23 2003-12-09 08:52

All times are UTC. The time now is 00:35.

Tue Jun 15 00:35:56 UTC 2021 up 17 days, 22:23, 0 users, load averages: 1.33, 1.71, 1.66