mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Programming (https://www.mersenneforum.org/forumdisplay.php?f=29)
-   -   Can the subtraction in the lucal lehmer test ever return a negative value? (https://www.mersenneforum.org/showthread.php?t=25373)

 R.D. Silverman 2020-03-18 14:35

[QUOTE=BrainStone;540043]Do I understand correctly that there are cases that consequently allow it to become 1?[/QUOTE]

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 2020-03-18 14:47

[QUOTE=kuratkull;540046]R.D. Silverman - I think you mixed me up with the OP. I am not trying to implement anything, I already did: [url]https://github.com/dkull/rpt[/url]
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.[/QUOTE]

Mea culpa if I confused you with someone else. My apology. Yet you made some clearly
incorrect mathematical statements.

 retina 2020-03-18 15:04

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))[/code]Can some help me to optimise it? I need it to run really really fast.

 paulunderwood 2020-03-18 15:41

[QUOTE=retina;540056]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))[/code]Can some help me to optimise it? I need it to run really really fast.[/QUOTE]

:lol: print("3 5 7 13 17 19 31 61 89 107 127 521 607 1279")

 BrainStone 2020-03-18 15:58

[QUOTE=R.D. Silverman;540050]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.[/QUOTE]

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}[/$]

 paulunderwood 2020-03-18 17:19

[QUOTE=BrainStone;540060]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}[/$][/QUOTE]

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?

 xilman 2020-03-18 17:23

[QUOTE=BrainStone;540048]What error did I do?[/QUOTE]
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[SUP]*[/SUP]; 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=BrainStone;540048]That's just being rude and inappropriate.[/QUOTE]Very likely so. Not everyone is polite.

--- :paul:

* I've been getting all sorts of :poop: 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.

 R.D. Silverman 2020-03-18 17:59

[QUOTE=BrainStone;540060]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}[/$][/QUOTE]

Not if M_p is prime. If M_p is composite then 4 can generate a subgroup.

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