> >> B: Cycling before the P-1th iteration is unlikely in its own right.
> > I thought we had more or less worked out (not formally proved - but a
> > solid argument)
> At the time, Chris Nash said:
Who, me? I did a lot of hand-waving... Peter-Lawrence Montgomery followed up
with a couple of excellent worked examples that showed exactly what's going
on with this, and how it could be calculated where a recurrence occurs
(answer, a *very* long time after you finish the calculation!).
> "The odds of a recurrence occurring make the odds of finding a prime seem
> positively good!"
> Brian J Beesley said that he had a "sneaky suspicion," that they would
> recurr only in composite remainders, but there weren't any arguments to
> support this.
> I agree that this should be put in the FAQ, so that we don't have to
> go through this every 1-2 months...
Peter's explanation ought to stop the question without a shadow of a doubt,
and perhaps should go in the FAQ. Brian pretty well hammered home the fact
that your number would have to be pretty special indeed for this to
happen...
*sigh* Hopefully for the last time here's a potted explanation:
- To primality prove, you basically prove the size of a group is as big as
possible. Elements with common factors with N aren't in the group, so "big
as possible" implies "N prime".
- The simplest proof comes from Fermat's little theorem, a^(p-1)=1 mod p for
a prime p. So if you could show (p-1) was the smallest solution to a^x=1 mod
p, for some a, then p would be a prime, the sequence wouldn't repeat within
those p-1 steps, all the values would be distinct, group as large as
possible, etc....
- The idea behind Lucas sequences is we work with A+B.sqrt(D) mod p, for
some value D, and try to prove that group has p^2-1 elements. Different
group, but the same principle.
- It's sufficient to find a special sort of sequence that doesn't exhibit
repetition until the p+1'st element.
- If it doesn't repeat exactly there, then the number is composite (and it
repeats, or degenerates) sometime sooner. All things being equal, the
repetition or degeneration point occurs practically anywhere, we wouldn't
know exactly where without either knowing all the factors of N, or looking
directly at the right spot.
- You don't need to calculate every value in the sequence, there's efficient
algorithms involving squaring, to determine that the repetition point
*isn't* at p+1. Since p+1 is a nice power of 2 for a Mersenne number, the LL
test becomes quite simple. You square and subract, positively fly through
the underlying sequence, and only look at n-2 values, not 2^n values.
- So you're looking at an absolutely tiny sample of a sequence that could
repeat practically anywhere. The chances you'd ever 'see' the repetition are
beyond human comprehension, even for quite small numbers.
- 2^6 million and something is not a small number, even if you subtract 1.
- My guess is, you have less chance of spotting a repetition than you have
of every molecule of air on this planet suddenly deciding to simultaneously
move to New Jersey. Not a physical impossibility, but a
within-the-lifetime-of-the-universe improbability.
Apologies for the flippancy. Let's put Peter's well-crafted reasoning in the
FAQ.
Chris
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
