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

[BrainStone]

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

Yes there was. This wasn't a question about programming but rather about certain edge cases. The programming part was merely providing context as to why I was interested in it.

Originally Posted by LaurV

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)

I fail to see the relevance. My goal is not to create a fast implementation. My goal is to create the fastest implementation under some restrictions. Which in this case are using the BigInteger library in Java.
I never claimed that it would make sense to do so. I am doing it because I enjoy playing with numbers. And also because I want to practise optimizing things in Java. Because that's part of my job.

And all those things are irrelevant to the underlying math question.

Originally Posted by LaurV

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

In summary I wasn't aware of the fast mod. So I tried optimizing the small things as those were the obvious things to try. And my obsession with -2 comes from the fact that I'd like to make sure that the implementations are 100% correct. Hence I'd like to make sure they pass edge cases. And \(S(n) = 1\) would be such an edge case.

But in turn let me ask you this:
What is your (all) obsession with essentially telling me I'm not allowed to (or shouldn't) do things I enjoy for the sake of doing them? I mean think about it. The entire premisse of this forum is based on a futile matter. Finding Mersenne Primes has no merrit to it other than creating utterly obscure knowledge that most likely will never be relevant. And why do people do that? Because they enjoy doing it or because they are curious. The exact same applies to what I am doing.
Now you might say things like "But math is math. Every bit of knowledge is valuable. And one day it might be important". And to that I say "Rightfully so. And knowing which way to implement LL using Java's BigInteger is the fastest is exactly the same." Or "While doing so many important things have been discovered along the way". And my response would be that the same applies to my case. Even if only I learn doing it.

And regarding R.D. Silverman's answer:
I asked a yes-no question (does such a case exist). And the reply was a mathematical explanation that I don't understand. So while this may be answer to you, it isn't to me. I can't tell if their answer means "Yes, such cases are possible" or "No. No such cases are possible". Though if I had to guess, it's a yes and that we haven't found any such cases so far.

But I get it. Uneducated people are not welcome here and neither are people that enjoy doing "futile" things for the sake of it.

[axn]

Originally Posted by BrainStone

But I get it. Uneducated people are not welcome here and neither are people that enjoy doing "futile" things for the sake of it.

So you got criticized. Doesn't mean you or your ideas are unwelcome. But doesn't mean your ideas get a free pass either. You are free to choose which criticisms you take to heart and which you ignore.

Anyway, do you want to know what's funny about your concerns with encountering negative numbers? It doesn't matter! Java biginteger uses signed integers, and so even if you run into negative numbers, the squaring operation in the next iteration will still give you correct value! Try it.

One thing that bugs me though. You said that S.multiply(S).mod(M_p).subtract(2).mod(M_p) benchmarked a little bit faster than S.multiply(S).mod(M_p).subtract(2). Since the former does strictly more operations than the latter, I have to assume that perhaps your benchmarking is somehow flawed. Maybe they're close enough that you're measuring statistical variation, but I can't believe that the first one can ever be faster than the second.

[kuratkull]

Doing some back-of-the-napkin math here, which might not be correct - I am not a mathematician, but a software engineer.
We have N=2^n-1. Let's assume n "tries" to get 1 as a result of the mod operation.
The result can be 0..N.. So every single try has 1/N chance of being 1. (I am leaving out the fact that the result first has to reach N)
So the chance of a candidate becoming 1 is roughly: 1/(2^n)*n
This chance becomes miniscule very quickly, eg. n=64 is circa 10^-18. n=128 is circa 10^-37
So it's practically impossible to hit that condition. Am I right?

[BrainStone]

Originally Posted by axn

So you got criticized. Doesn't mean you or your ideas are unwelcome. But doesn't mean your ideas get a free pass either. You are free to choose which criticisms you take to heart and which you ignore.

We're well past critizism. We're at the point that I quite frankly feel ridiculed. And most of the thread has been critizism of futile points and things not related to the question.
There's a saying that if you don't have anything nice or constructive to say, don't say anything. And critizing me for using an inefficient (in the grand scheme of things) method of doing things when absolute efficiency isn't a concern of mine is not constructive. And said point has been repeated numerous times already.

Originally Posted by axn

Anyway, do you want to know what's funny about your concerns with encountering negative numbers? It doesn't matter! Java biginteger uses signed integers, and so even if you run into negative numbers, the squaring operation in the next iteration will still give you correct value! Try it.

At this point I agree. I know that it is a signed type. My initial concerns were that hitting a negative value might result in false negatives. Though since hitting a negative value will always result in a loop there can't be any false negatives.
And while I initially doubted that it could matter at all, I wasn't sure initially, so I wanted to have test cases that covered it.

So I am aware that this discussion only has a pure mathematical value left, which is makes me disagree even more with the decision to merge the threads and move it into Programming, where it now is severely misplaced.

Originally Posted by axn

One thing that bugs me though. You said that S.multiply(S).mod(M_p).subtract(2).mod(M_p) benchmarked a little bit faster than S.multiply(S).mod(M_p).subtract(2). Since the former does strictly more operations than the latter, I have to assume that perhaps your benchmarking is somehow flawed. Maybe they're close enough that you're measuring statistical variation, but I can't believe that the first one can ever be faster than the second.

It's very well possible that that's the case. Though since it is Java and Java handles memory in a strange way it could be that through memory schenanigans it does weird stuff.

[R.D. Silverman]

Originally Posted by kuratkull

Doing some back-of-the-napkin math here, which might not be correct - I am not a mathematician, but a software engineer.
We have N=2^n-1. Let's assume n "tries" to get 1 as a result of the mod operation. (I am leaving out the fact that the result first has to reach N)
The result can be 0..N.. So every single try has 1/N chance of being 1.

You are not listening. And despite your claim, it is clear that you do not understand
modular arithmetic. In particular you did not listen to my discussion about
representations.

Arithmetic mod N can never yield a result that is in [0,.....N] because N is not part of
the representation. It can be [0,....N-1]. Because, trivially N mod N equals 0.
When working mod N the expression [0,....N] is not a set. It is a multi-set.

Secondly, your assertion that "The result can be 0..N.. So every single try has 1/N
chance of being 1." is also wrong. There are N+1 elements in 0,....N , not
N. Your statement also assumes a uniform pdf which assuredly it is NOT.

You are a software engineer trying to implement an algorithm whose correct
implementation requires knowing a lot of math. Multiple people have told you that
the "-2" is irrelevant to the run-time. Yet you continue to argue with them.

So the chance of a candidate becoming 1 is roughly: 1/(2^n)*n

I will assume that by the word "becoming" you mean "becoming before reaching the last
iteration".

Your assertion is totally wrong. If N = 2^p-1 is prime the probability is zero. If N is
composite the probability depends on the factors of N+1 and the structure of the
subgroups of the twisted group, i.e. it depends on the number of elements whose order
is r for r less than the full order. The values of r depend on the factors of N+1.

This chance becomes miniscule very quickly, eg. n=64 is circa 10^-18. n=128 is circa 10^-37
So it's practically impossible to hit that condition. Am I right?

You are not. It is totally impossible to hit it if N is prime. If N is composite see above.

You state that you are not a mathematician, yet you make mathematical pronouncements
when you don't know the math. I call that arrogant.

Stop making pronouncements and start listening. You will need to learn some
modern algebra, some number theory, and some statistical theory.

[BrainStone]

Originally Posted by kuratkull

Doing some back-of-the-napkin math here, which might not be correct - I am not a mathematician, but a software engineer.
We have N=2^n-1. Let's assume n "tries" to get 1 as a result of the mod operation.
The result can be 0..N.. So every single try has 1/N chance of being 1. (I am leaving out the fact that the result first has to reach N)
So the chance of a candidate becoming 1 is roughly: 1/(2^n)*n
This chance becomes miniscule very quickly, eg. n=64 is circa 10^-18. n=128 is circa 10^-37
So it's practically impossible to hit that condition. Am I right?

I fully agree with your reasoning (Turns out that was wrong. That's why I like to ask knowledgable people ;) ). But practically impossible doesn't mean impossible. I mean Mersenne Primes become increasingly less likely but there most likely are more and it's certainly beneficial to consider rare edge cases.

Though as pointed out, programmically speaking it's a non concern. So now I'm just genuinely curious as to whether or not those cases might exist.

[BrainStone]

Originally Posted by R.D. Silverman

If N is
composite the probability depends on the factors of N+1 and the structure of the
subgroups of the twisted group, i.e. it depends on the number of elements whose order
is r for r less than the full order. The values of r depend on the factors of N+1.

Do I understand correctly that there are cases that consequently allow it to become 1?

[xilman]

Originally Posted by BrainStone

We're well past critizism. We're at the point that I quite frankly feel ridiculed.

Chill. Everyone here who posts more than few times gets ridiculed eventually. And I mean everyone.

Learn from it by not repeating your error / naivety / whatever and any cases which can be easily deduced from the reaction to it.

[R.D. Silverman]

Originally Posted by BrainStone

We're well past critizism. We're at the point that I quite frankly feel ridiculed. And most of the thread has been critizism of futile points and things not related to the question.
There's a saying that if you don't have anything nice or constructive to say, don't say anything. And critizing me for using an inefficient (in the grand scheme of things) method of doing things when absolute efficiency isn't a concern of mine is not constructive. And said point has been repeated numerous times already.

I gave a complete (expressed in elementary terms) mathematical explanation.
A mature person who did not understand it, yet still desiring to do this work would take
the time to go learn the math. Yes, it takes a lot of time. One can't correctly
implement a mathematical algorithm without understanding the math.

The first question you should have asked was "What do I need to learn in order to
correctly implement this algorithm".

At this point I agree. I know that it is a signed type. My initial concerns were that hitting a negative value might result in false negatives.

Yet, you did not ask that question. And you personally were not being criticized. Your
statements were. If you can't stand to have your discussion criticized then you
need to find another venue.

[kuratkull]

R.D. Silverman - I think you mixed me up with the OP. I am not trying to implement anything, I already did: https://github.com/dkull/rpt
Most of the stuff you commented on was left out/ignored for brevity. It bears no significant weight on the magnitude of the final calculation.
I think starting with a disclaimer and ending with a question about correctness leaves little room for arrogance.

[BrainStone]

Originally Posted by xilman

Chill. Everyone here who posts more than few times gets ridiculed eventually. And I mean everyone.

Learn from it by not repeating your error / naivety / whatever and any cases which can be easily deduced from the reaction to it.

What error did I do? I was upfront about that I know that what I'm doing isn't productive after my choice of programming language and library was (correctly) critizised the first time. I've then provided my motivation and justification to use it, which prompted unwarrented ridicule.

It's like saying I want to race with a tractor (to pick up on a previous analogy). Then being critizised that that is a bad choice (which is correct). I proceeded to explain that I enjoy racing with tractors and that I don't want to anything but race tractors. Which then resulted people continuing to critize my choice of vehicle, even though it was clear that I was fully aware of the downsides and was chosing for very different reasons.
That's just being rude and inappropriate.