mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2020-03-17, 10:50   #1
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

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

I am currently working on this lovely project: https://github.com/BrainStone/MersennePrime-Benchmark
And naturally I'd like to make sure that my LL implementations are correct. Now I've been worrying about whether the subtraction part in the LL test can ever return -1 or -2.

What I'm talking about specifically is that for potential optimizations of the calculation, I take the mod after the multiplication but not after the subtraction (as that shouldn't really matter how many times I mod or not). So essentially like that: \(S\left(k+1\right) \equiv \left(S\left(k\right)^2 mod M_p\right) - 2\)

Why am I interested in those cases? Simply because I want to test for edge cases as I will use the remainder method which is like mod but can return negative values. And I just want to make sure that those implementations also pass these edge cases.

From my preliminary search it didn't seem like there were any such cases. So my question is if that could even happen at all.
And if it can happen, are there known cases for both Mersenne Primes and Mersenne Numbers that aren't primes (don't want false positives, not false negatives)?

Last fiddled with by BrainStone on 2020-03-17 at 10:54
BrainStone is offline   Reply With Quote
Old 2020-03-17, 11:02   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

124728 Posts
Default

1 is a quadratic residue mod p, so I'd say yes, you might see a value of 1 during the LL test. But it goes into loop 1,1,1,1 etc.

Last fiddled with by retina on 2020-03-17 at 11:05
retina is online now   Reply With Quote
Old 2020-03-17, 11:13   #3
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

378 Posts
Default

Quote:
Originally Posted by retina View Post
1 is a quadratic residue mod p, so I'd say yes, you might see a value of 1 during the LL test. But it goes into loop 1,1,1,1 etc.

I'm performing a LL test. So there's always the subtraction before the next squaring.
BrainStone is offline   Reply With Quote
Old 2020-03-17, 12:03   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2·11·13·19 Posts
Default

Quote:
Originally Posted by BrainStone View Post
I'm performing a LL test. So there's always the subtraction before the next squaring.
Yes, I know.

1 - 2 = -1
(-1)^2 = 1
retina is online now   Reply With Quote
Old 2020-03-17, 12:16   #5
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

I feel stupid now...


In any case I'm wondering if that value of 1 (or -1) could ever be reached in the first place, as a search with primes up to around 7000 hadn't resulted in any of such cases
BrainStone is offline   Reply With Quote
Old 2020-03-17, 12:25   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

23·32·103 Posts
Default

Quote:
Originally Posted by BrainStone View Post
I am currently working on this lovely project: https://github.com/BrainStone/MersennePrime-Benchmark
And naturally I'd like to make sure that my LL implementations are correct. Now I've been worrying about whether the subtraction part in the LL test can ever return -1 or -2.

What I'm talking about specifically is that for potential optimizations of the calculation, I take the mod after the multiplication but not after the subtraction (as that shouldn't really matter how many times I mod or not).
Huh? This last statement makes no sense. One computes the remainder once per
iteration. More than that only slows the computation [dramatically!] And if using a DWT
one does not explicitly compute a remainder at each iteration.


Quote:
So essentially like that: \(S\left(k+1\right) \equiv \left(S\left(k\right)^2 mod M_p\right) - 2\)

Why am I interested in those cases? Simply because I want to test for edge cases as I will use the remainder method which is like mod but can return negative values. And I just want to make sure that those implementations also pass these edge cases.

From my preliminary search it didn't seem like there were any such cases. So my question is if that could even happen at all.
And if it can happen, are there known cases for both Mersenne Primes and Mersenne Numbers that aren't primes (don't want false positives, not false negatives)?
May I suggest that before going any further you need to learn how modular
arithmetic works and also get a correct statement of how the LL test works?? You
also need to study modular multiplication in detail.

No offense, but you should study the underlying arithmetic before writing code.

You seem to be confused.

(1) The iteration is S_{n+1} = [(S_n)^2 - 2] mod M_p.

(2) Do you understand that whether negative numbers exist when doing modular
arithmetic depends on the representation that you choose? Arithmetic mod N
can use a representation: [0, N-1] or it can use a representation [-(N-1)/2, (N-1)/2]]
(for odd N). A number such as -2 mod N can use the -2 representation or it can use
N-2. You should also learn that numbers mod N fall into equivalence classes.
Most people erroneously believe that the expression (c = a mod N) means c equals the
remainder when a is divided by N. But this is not the correct mathematical definition.
The correct definition is that (c = a mod N) only means that (c-a) is divisible by N.
Numbers mod N fall into equivalence classes. Thus, (c = a mod N) is not an
equation. It is an equivalence relation.

(3) When performing an LL test you should also understand that you are actually
computing an exponentiation in the twisted subgroup of the finite field GF(q^2)
where q = M_p. It is quite similar to doing ordinary modular exponentiation in the
unit group of Z/NZ. You are simply working in a different group. The test is really
analogous to validating the order of an element in a unit group. Whereas an
ordinary PRP test checks that the order is q-1 in the unit group, the LL test checks that
the order is q+1 in the twisted subgroup. You should also study Lagrange's theorem.

[understanding this last part is necessary only if you want to learn how/why the test
works].
R.D. Silverman is offline   Reply With Quote
Old 2020-03-17, 12:25   #7
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

124728 Posts
Default

BrainStone: It doesn't matter. When you do the subtraction, if you get an overflow then adjust it to within range, if you don't, then do nothing. I don't see the big deal, it might never overflow and then it costs you nothing. Then it will work for ALL values; rather than praying, hoping and guessing that it might work.

Premature optimisation?

Last fiddled with by retina on 2020-03-17 at 13:13
retina is online now   Reply With Quote
Old 2020-03-17, 12:28   #8
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

22·3·11 Posts
Default

This interests me too because I implemented the LLR test (for Riesel primes, but works on Mersenne primes too, just set k=1 )[ https://github.com/dkull/rpt/ ] and thought about this myself. The test is very similar to the LL test. Something is gnawing in me and saying that it can't become one... though I am really interested in someones educated opinion.


You probably won't find a case by brute force, because the modulus gets really large really fast and thus the chance (assuming basically random chance - and if it's even possible) of landing on 1 after the mod operation would become practically nonexistent.


EDIT: I wouldn't be the least surprised if it actually can become one

Last fiddled with by kuratkull on 2020-03-17 at 12:36
kuratkull is offline   Reply With Quote
Old 2020-03-17, 13:06   #9
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

111112 Posts
Default

R.D. Silverman, I have a fair understanding of modulus and equivalence classes.
And I do know that the iteration is \(S \left( n + 1 \right) \equiv \left( {S \left( n \right)}^2 - 2 \right) mod M_p\). The math here is pretty clear.

However in terms of optimization we are in the realms of programming and computer science. And while they are inherently linked there are some differences.

Now you mentioned that I should only do one modulus per iteration as else it will cost a lost of performance. Before my testings I would have agreed. But what you think is fastest is not always the fastest and that's why I want to benchmark it.

Now I'm fully aware that Java's BigInteger class is terribly slow. I'm using it regardless because it is a built in and I'm more or less just playing around. Another thing about that class is that all values are immutable. So any arethmetic operation creates a new instance (makes the 2 mods vs 1 mod per iteration problem sound like it's even clearer that you should only mod once, right?).

So among others I tried these 3 iteration steps:
  • S.multiply(S).subtract(2).mod(M_p)
  • S.multiply(S).mod(M_p).subtract(2)
  • S.multiply(S).mod(M_p).subtract(2).mod(M_p)
My current benchmarks indicate that the last is the fastest, the second only marginally slower and the first is noticable slower than the other two. Which was quite surpising.

But I digress.

Now onto the real issue and why even I brought up negative numbers.

In many C-like languages there is a modulus/remainder operator: %
It works great, but it has one flaw: -1 % 10 -> -1
Or put in words, if the left operand is negative, the result is negative too. Forcing a postive result is computationally more expensive.

Now in the above case the mod function behaves like the mathematical modulus and only ever returns positive values. But there's also the remainder function. Which behaves like the % operator. Now since my guess is that that function is faster I want to test that function too. However I also want to make sure that the implementation is correct, so I have some test cases set up. And to be sure that the implementation handles negative numbers correctly I was looking for either known cases or interested to find out if it could actually happen.

Does it make more sense now?

Last fiddled with by BrainStone on 2020-03-17 at 13:09
BrainStone is offline   Reply With Quote
Old 2020-03-17, 13:15   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×11×13×19 Posts
Default

You are using Java, and you feel the need to optimise it! That is dumb. You don't optimise Java, you rewrite it some other language, like assembly, and then optimise once you have it working.
retina is online now   Reply With Quote
Old 2020-03-17, 13:21   #11
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by retina View Post
You are using Java, and you feel the need to optimise it! That is dumb. You don't optimise Java, you rewrite it some other language, like assembly, and then optimise once you have it working.

I never claimed it was a good choice.
My concerns about negative numbers are independent of that hower because calculating the modulus like I described is fairly common in computer science. And I've seen my fair share of big int libraries that calculate their mod like that.


And yes there is a need. Because between the best and worst method I've tested so far, the fastest is roughly twice as fast as the slowest.

Last fiddled with by BrainStone on 2020-03-17 at 13:22
BrainStone 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 04:54.

Sun May 31 04:54:21 UTC 2020 up 67 days, 2:27, 1 user, load averages: 2.18, 2.13, 1.97

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.