mersenneforum.org

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)

paulunderwood 2020-03-17 16:00

[QUOTE=R.D. Silverman;539950]This is supposed to be the [b]math[/b] subforum.[/quote]

I am moving thread to "Programming".

BrainStone 2020-03-17 16:08

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 2020-03-17 16:12

[QUOTE=BrainStone;539953]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.[/QUOTE]

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 2020-03-17 16:18

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

I will move it back :raman: and leave it up to another mod to pick apart the Java aspects.

BrainStone 2020-03-17 16:26

[QUOTE=paulunderwood;539956]I will move it back :raman: and leave it up to another mod to pick apart the Java aspects.[/QUOTE]


Don't worry. I'll open a new thread myself there soon.

BrainStone 2020-03-17 22:26

Continuation of: Can the subtraction in the lucal lehmer test ever return a negative value?
 
The original [URL="https://www.mersenneforum.org/showthread.php?t=25373"]topic[/URL] 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 [C]&[/C] is the bitwise AND operator @paulunderwood. And so is the [C]and[/C] method here.

BrainStone 2020-03-17 22:27

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

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: [url]https://www.mersenneforum.org/showthread.php?p=539988[/url]

R.D. Silverman 2020-03-17 22:44

[QUOTE=BrainStone;539989]That is a fair bit above my knowledge. Could you elaborate?
[/QUOTE]

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 2020-03-17 22:49

[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]))
[/CODE]

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]
[/CODE]

BrainStone 2020-03-17 23:39

[QUOTE=paulunderwood;539995][CODE]f(S>=n,S-=n);[/CODE][/QUOTE]


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

LaurV 2020-03-18 06:50

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 [B]thousands of times slower[/B] 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". :razz:

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


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.