"Benny.VanHoudt" <[EMAIL PROTECTED]> asks
> I was looking at the LL-test and thought of the following:
> To succeed a LL-test the final value (mod 2^p - 1) has to be zero.
> To be able to get this there has to be a number x (between 0 and 2^p - 2)
> such that x^2 = 2. This because in the final step of the
> LL test the value is squared and substracted by two.
>
> In some cases for example 15 = 2^4 - 1 (this cannot be prime because
> four isn't but that's not the point) such a value does not exist:
>
> 0^2 = 0, 1^2 = 1, 2^2 = 4, 3^2 = 9, 4^2 = 1, 5^2 = 10, 6^2 = 6, 7^2 = 4,
> 8^2 = 4, 9^2 = 6, 10^2 = 10, 11^2 = 1, 12^2 = 9, 13^2 = 4 and 14^2 = 1.
>
> Of course in this case p = 4 is not prime so we would never do a LL-test
> anyway. My question is whether anyone knows if such an x always exists if p
> is indeed a prime ? Perhaps this is only true for a subset of all primes,
> and this would allow us to focus on this subset only (if it can be
> determined more easily) ?
>
If p = 2k + 1 is odd, then x = 2^(k+1) satisfies x^2 = 2 + 2*(2^p - 1).
As far as I know, we don't know how to predict whether the next-to-last
term will be 2^((p+1)/2) or -2^((p+1)/2) in the LL-sequence. For example,
modulo 31, the backwards sequence might go
0
/ \
/ \
8 23
/ | |\
/ | | \
14 17 5 26
/| | \ |\ \
/ | | \ | \ |\
4 27 9 22 10 21 11 20
The left upward sequence (4 -> 14 -> 8 -> 0) is of course the
proper sequence. But with everything having two ancestors,
how do we predict that? Modulo 127 the sequence
4 -> 14 -> 67 -> 42 -> 111 -> 0 has 111 == -16 preceding the zero.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
