mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2020-03-17, 16:00   #23
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

62068 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This is supposed to be the math subforum.
I am moving thread to "Programming".

Last fiddled with by paulunderwood on 2020-03-17 at 16:05
paulunderwood is offline   Reply With Quote
Old 2020-03-17, 16:08   #24
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

I'm perfectly happy have the programming part of this discussion moved somewhere else.

Though I do believe the question if \(\exists S \left( n \right) \equiv 1 \mod M_p\) belongs here.
BrainStone is offline   Reply With Quote
Old 2020-03-17, 16:12   #25
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

23×32×103 Posts
Default

Quote:
Originally Posted by BrainStone View Post
I'm perfectly happy have the programming part of this discussion moved somewhere else.

Though I do believe the question if \(\exists S \left( n \right) \equiv 1 \mod M_p\) belongs here.
It does. And I answered. Look up Lagrange's Theorem. In GF(q^2) 4 is a generator
of the full twisted group iff q is prime. Otherwise, 4 generates a subgroup of the
full twisted group.
R.D. Silverman is offline   Reply With Quote
Old 2020-03-17, 16:18   #26
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×7×229 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It does. And I answered. Look up Lagrange's Theorem. In GF(q^2) 4 is a generator
of the full twisted group iff q is prime. Otherwise, 4 generates a subgroup of the
full twisted group.
I will move it back and leave it up to another mod to pick apart the Java aspects.
paulunderwood is offline   Reply With Quote
Old 2020-03-17, 16:26   #27
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I will move it back and leave it up to another mod to pick apart the Java aspects.

Don't worry. I'll open a new thread myself there soon.
BrainStone is offline   Reply With Quote
Old 2020-03-17, 22:26   #28
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

1F16 Posts
Default Continuation of: Can the subtraction in the lucal lehmer test ever return a negative value?

The original topic which was about certain edge cases in the Lucas-Lehmer-Test derailed fairly quickly and I'd like to continue the programming discussion here.

So @axn, any idea what seems to be wrong with your code?

And in Java & is the bitwise AND operator @paulunderwood. And so is the and method here.
BrainStone is offline   Reply With Quote
Old 2020-03-17, 22:27   #29
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It does. And I answered. Look up Lagrange's Theorem. In GF(q^2) 4 is a generator
of the full twisted group iff q is prime. Otherwise, 4 generates a subgroup of the
full twisted group.
That is a fair bit above my knowledge. Could you elaborate?

Also @bearnol would you putting your doubts about his statements into words here too?

The programming discussion may continue here: https://www.mersenneforum.org/showthread.php?p=539988

Last fiddled with by BrainStone on 2020-03-17 at 22:28
BrainStone is offline   Reply With Quote
Old 2020-03-17, 22:44   #30
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

23·32·103 Posts
Default

Quote:
Originally Posted by BrainStone View Post
That is a fair bit above my knowledge. Could you elaborate?
An full explanation would require quite a bit of prerequisite knowledge; At least a semester
of group theory and another semester of studying finite fields. Perhaps the best source
for the latter is Lidl & Niederreiter's book on finite fields.
R.D. Silverman is offline   Reply With Quote
Old 2020-03-17, 22:49   #31
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

C8616 Posts
Default

Code:
p=13;n=2^p-1;S=4;
for(k=3,p,S=S^2-2;
S=bitand(S,n)+(S>>p);if(S>=n,S-=n);
print([p,S]))
Gives the require output:
Code:
[13, 14]
[13, 194]
[13, 4870]
[13, 3953]
[13, 5970]
[13, 1857]
[13, 36]
[13, 1294]
[13, 3470]
[13, 128]
[13, 0]

Last fiddled with by paulunderwood on 2020-03-17 at 22:50
paulunderwood is offline   Reply With Quote
Old 2020-03-17, 23:39   #32
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Code:
f(S>=n,S-=n);

That fixed it. Now the only thing is making benchmarks. Thank you
BrainStone is offline   Reply With Quote
Old 2020-03-18, 06:50   #33
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2·17·251 Posts
Default

Threads merged and moved to programming.

There was no reason to split threads, the initial thread already gave all the answers, including from RDS, who was actually quite right. The fact you don't like the answers is not a reason to clutter.

You are using java (terrible slow, interpreted, not compiled, no FFT multiplication, which translates to thousands of times slower than a "normal" gmp or gwnum implementation, and it is limited for integer size to 40k bytes or so, therefore completely futile to test any reasonable exponent), but in the same time you seem to be quite nitpicking on subtracting 2 before or after taking the modular from the square. People gave you already a better way to avoid division taking advantage of the binary form of the modulus, which would double the speed (not in pari, bitand is terrible slow there), with or without subtracting 2, and you are still fixed on that subtracting 2. C'mon man, it is like racing a tractor against a ferrary and trying to make your tractor faster by changing the position of the mirror or something, to avoid "catching the wind", or throwing out the knob of the handbrake because "it is too heavy".

Listen to these guys, they know what they are talking.

Last fiddled with by LaurV on 2020-03-18 at 06:55
LaurV 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 08:24.

Thu May 28 08:24:29 UTC 2020 up 64 days, 5:57, 1 user, load averages: 2.16, 1.98, 1.92

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.