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

2020-03-17, 16:00   #23
paulunderwood

Sep 2002
Database er0rr

62068 Posts

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

 2020-03-17, 16:08 #24 BrainStone     Nov 2017 Karlsruhe, Germany 31 Posts 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.
2020-03-17, 16:12   #25
R.D. Silverman

Nov 2003

23×32×103 Posts

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

2020-03-17, 16:18   #26
paulunderwood

Sep 2002
Database er0rr

2×7×229 Posts

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

2020-03-17, 16:26   #27
BrainStone

Nov 2017
Karlsruhe, Germany

31 Posts

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

 2020-03-17, 22:26 #28 BrainStone     Nov 2017 Karlsruhe, Germany 1F16 Posts 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.
2020-03-17, 22:27   #29
BrainStone

Nov 2017
Karlsruhe, Germany

31 Posts

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

2020-03-17, 22:44   #30
R.D. Silverman

Nov 2003

23·32·103 Posts

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

 2020-03-17, 22:49 #31 paulunderwood     Sep 2002 Database er0rr C8616 Posts 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
2020-03-17, 23:39   #32
BrainStone

Nov 2017
Karlsruhe, Germany

31 Posts

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

That fixed it. Now the only thing is making benchmarks. Thank you

 2020-03-18, 06:50 #33 LaurV Romulan Interpreter     Jun 2011 Thailand 2·17·251 Posts 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

 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 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