[EMAIL PROTECTED] writes:
> We can illustrate working modulo M23 = 8388607 = 47 * 178481.
>3 is a quadratic reside modulo 47 (e.g, 12^2 == 3 mod 47),
>so 2 + sqrt(3) is in the base field of order 47.
>The multiplicative order of 2 + sqrt(3) divides 47-1, and turns out to be 23.
>
> 3 is a quadratic nonresidue modulo q = 178481. The order of 2 + sqrt(3)
>divides q + 1 = 178482 = 2 * 3 * 151 * 197 and turns out to be 178482.
>
> The least common multiple of these orders is
>2 * 3 * 23 * 151 * 197. So L(2 * 3 * 23 * 151 * 197) == L(0) mod M23.
>
> For the L sequence, we need two powers of 2 whose difference is
>divisible by 2 * 3 * 23 * 151 * 197.
>The orders of 2 modulo 3, 23, 151, 197 are 2, 11, 15, 196, respectively.
>The order of 2 modulo 3 * 23 * 151 * 197 is the least common multiple
>of these orders, namely 2^2 * 3 * 5 * 7^2 * 11 = 32340.
>To include a factor of 2, we need L(2^32341) == L(2^1) mod M23.
>That is, S(32341) == S(1) mod M23.
>This is far more than 23 LL steps before the sequence repeats.
>
> EXERCISE: Repeat this analysis modulo M11 = 23 * 89.
> Find the period modulo M29 = 233 * 1103 * 2089, after getting
> the individual periods for each prime factor.
Yes - the result for M29 is quite interesting due to the "unexpected" short
period of 60. (I feel after a week I'm not spoiling it for anyone by giving
the result away...)
Incidentally the first repeating remainder for _all_ the non-prime Mersenne
numbers with prime exponents is S(1) = 14.
I was interested to see what would happen for larger exponents, in particular
if the first repeating remainder would always be 14. Unfortunately this is
not true, the first repeating remainder for M37 is S(5) = S(516929). Finding
this took a fair bit of CPU time as, to start with, I more or less assumed
that the remainder would eventually go back to 14 (Peter's impeccable logic
seemed to suggest this to my inadequate maths!) so I had to run through
2^37-1 calculations to be sure that 14 never recurred, and even then I wasn't
sure I wasn't fighting a program bug.
Now I have a _much_ faster way of checking, assuming that the first repeating
remainder will be one of the first few in the (S) sequence. But is this true?
Instinctively one feels that it ought to be, but can one construct an example
where the the index n of the first repeating remainder S(n) is large compared
with the period? My math is totally inadequate to investigate this... (I'm
only interested in the case p prime, M(p) composite. Of course when M(p) is
prime then n=p and the period is 1)
Also, Peter's logic seems to depend on knowing the factors. Would it be
possible to "reverse engineer" at least one of the factors of M(p) (or at
least be in a much-improved position to find them) if one knew the repeat
period and/or the first repeating remainder in the S sequence for M(p)?
The reason I ask is that my "experimental" method of finding the period &
remainder does not depend on _any_ knowledge of the factorization of M(p),
and I reckon I could get the values for, say, M727 with the expenditure of
a great deal less computer time than completing the search to B1=44*10^6
using ECM would take.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
