Can the subtraction in the lucal lehmer test ever return a negative value?

[paulunderwood]

Originally Posted by R.D. Silverman

This is supposed to be the math subforum.

I am moving thread to "Programming".

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

[R.D. Silverman]

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.

[paulunderwood]

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.

[BrainStone]

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.

[BrainStone]

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]

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

[R.D. Silverman]

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.

[paulunderwood]

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:

[13, 14]
[13, 194]
[13, 4870]
[13, 3953]
[13, 5970]
[13, 1857]
[13, 36]
[13, 1294]
[13, 3470]
[13, 128]
[13, 0]

[BrainStone]

Originally Posted by paulunderwood

f(S>=n,S-=n);

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

[LaurV]

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.