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, 10:50 #1 BrainStone     Nov 2017 Karlsruhe, Germany 3110 Posts 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
 2020-03-17, 11:02 #2 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 3·2,087 Posts 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
2020-03-17, 11:13   #3
BrainStone

Nov 2017
Karlsruhe, Germany

3110 Posts

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

2020-03-17, 12:03   #4
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

3·2,087 Posts

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

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

Nov 2003

164448 Posts

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

 2020-03-17, 12:25 #7 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 3·2,087 Posts 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
 2020-03-17, 12:28 #8 kuratkull     Mar 2007 Estonia 24·32 Posts 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
 2020-03-17, 13:06 #9 BrainStone     Nov 2017 Karlsruhe, Germany 31 Posts 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
 2020-03-17, 13:15 #10 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 11000011101012 Posts 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.
2020-03-17, 13:21   #11
BrainStone

Nov 2017
Karlsruhe, Germany

3110 Posts

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

 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 16:46.

Tue Sep 21 16:46:24 UTC 2021 up 60 days, 11:15, 0 users, load averages: 1.49, 1.64, 1.59