Running LL test from both ends of the sequence?

[ppo]

Originally Posted by MS63

One should NEVER ask a question unless one already knows the answer.

Seems to make this forum entirely pointless.

No, it is not like that. IFF you suspect that I am willfully lazy for not doing a little bit of work, you are authorized to jump on me. IF NOT, you have the choice to ignore my question or to try helping me.
That is how this forum should work, and I have seen many examples of that in previous posts, even from Bob Silverman.

[xilman]

Originally Posted by MS63

Oh simple, foolish one.

One would have thought that a forum such as this was exactly the place to ask ANY questions and be provided with a RELEVANT answer, but no: According to 'Lord Bob' 1) is not permitted, 2) is mandatory, 3) is tantamount to a criminal offence, 4) is outlawed, and all are reasons to NOT ask one's question. One should NEVER ask a question unless one already knows the answer.

Seems to make this forum entirely pointless.

Ignorance is curable. Even Bob, especially Bob, is clear about that. He is just as ignorant as anyone on some subjects, and freely admits it. The difference between him and some people is that he very rarely, if ever, makes pronouncements on subjects where he knows he is ignorant. He asks questions in an attempt to learn and he performs background reading so he knows how to ask sensible questions.

Ask Bob a sensible question and he will give a sensible answer. I suggest that you read through his responses to people who have asked sensible questions earlier.

And yes, I do mean "sensible" and not "advanced". He has answered questions before now that required only very simple mathematical concepts to answer.

Asking stupid questions, on the other hand, is guaranteed to annoy Bob (and irritate many other people, for that matter). Being able to distinguish between sensible and stupid questions becomes much easier if you've done your homework.


Paul

[drew]

Originally Posted by ppo

I understand that the all exercise is pointless, but I am curious, and this is probably my opportunity to be jumped on by Bob, or by all of you, for
1) being ignorant
2) not having done my homework
3) being lazy
4) asking stupid questions
but I am still unable to work backward starting from 0.
Would some kind soul walk me through an example with a very small exponent?

Hey PPO,

Don't let Bob get to you. Hopefully someday he'll recognize that there's more value to a person than how little they know about his particular field of interest, and develop some people skills.

Let's use the previously quoted example of 2^7-1, which is 127.

To do the forward test, start out with S0=4. Each successive iteration is the square of the previous minus 2, mod 127.

S1 = S0*S0-2 = 4*4-2 = 14
S2 = 14*14 - 2 = 194 = 67 mod 127

Since we're interested only in modulus 127, which is the remainder of a division by 127, we get 67 (194/127 = 1 remainder 67)

S3 = 67*67 - 2 = 4487 = 42 mod 127
S4 = 42*42 - 2 = 1762 = 111 mod 127
S5 = 111*111 - 2 = 12319 = 0 mod 127

When we get to 5, which is n-2, we stop. If it's zero, then the number is prime. Yipee!

Now, assuming we start by assuming S5 = 0, how can we work backwards to get S4? Well, we solve for S4:

S5 = S4^2 - 2
S4 = sqrt(S5 + 2) = sqrt(2)

We need to know the square root of 2 using the mod 127 field. In this field, 2 can have any of the following values:

2
127+2=129
127*2+2=256
127*3+2=383
127*4+2=510
.
.
.
127*125+2 = 15877

So there are many values which can be possible square roots. We're only interested in the above values that are perfect squares, since our number field contains only integers. In the set defined above, the values 256 and 12319 are both perfect squares of 16 and 111. I created a spreadsheet to work that out, and the computation for this is much more involved than the squaring and subtracting used for the forward step.

What's more is that you end up with two answers! The backward step is not deterministic. You need to consider both of these possibilities as being potential S4 values, which leaves exponentially more possibile values as you go a given number of steps backward.

The simple fact is that by the time you perform even 1 backwards iteration, you could solve the entire problem using the forward steps. Heck, with numbers as large as we're testing, I don't think the universe is old enough to have perform one iteration. We'd need to evaluate over 2^10000000 square roots.

Drew

[ppo]

Originally Posted by drew

Don't let Bob get to you.

Thanks for yours detailed and helpful answer, very good.
By the way I think that Bob is only jumping on people when he has some evidence that they are not doing at least some effort to think to the problem before posting..and I WAS indeed lazy, so please everyone jump hard on me...
(PPO, write one hundrede times, I was lazy, I was lazy, I was... )
Let me explain: Being lazy as I am, tonight I decided to work on an example starting from the smallest exponent: 3, and working backward, I reached
immediately an S0 value of 3, not 4, so I suddenly realized that, let aside computational difficulties, there is a more compelling reason why the
meet somewere in between method cannot work: since there are different starting values for the LL sequence, all leading to an ending value of 0 for a Mersenne prime, there is an high probability that the forward and the backward methods will never meet. That should have been evident to me days ago, but , as I admit, I was too lazy to think...

[T.Rex]

Originally Posted by ppo

... since there are different starting values for the LL sequence ...

This is well known since a long time. But I do not know of a nice paper describing and proving it.
The paper of Vasiga/Shallit (see: LLT DiGraph in Mersenne wiki for details and links) gives information about the tree and the loops, but not about the starting values.
Who can add something about these "starting values" in the wiki ?
Tony

[maxal]

See sequence A018844 in OEIS.

[T.Rex]

Originally Posted by maxal

See sequence A018844 in OEIS.

Thanks. I did not think to look there. But it does not really help, since the link "Herb Savage et al., Re: Mersenne: starting values for LL-test" is broken and there is no link to a paper providing a proof. Also, there is not a word about the fact that this Sequence of starting values can be built by: .
And MathWorld does not say a word about these starting values. The same in "The Little Book of Bigger Primes" of Ribenboim.

Could someone (with better Number Theory skills than me) could propose MathWorld to add information about these starting values ? with links to papers and proofs !

Tony

[maxal]

Originally Posted by T.Rex

the link "Herb Savage et al., Re: Mersenne: starting values for LL-test" is broken

It was archived here.