Re: U-Tetration-matrix and iterated mersenne-primes (applic. to Lucas-Lehmer-test)

Am 14.01.2009 22:33 schrieb Gottfried Helms:

It was stated, that for p=13 this does not hold; at some h is M°h_13
not (a Mersenne-)prime, but for p=2 (and subsequently p=3,7,127)
this holds and is not known, whether it holds for higher iterations
h.
V(2)~ * Ut = V(3) ~ // 3 = M_2 is prime
V(2)~ * Ut^2 = V(7) ~ // 7 = M_3 is prime
V(2)~ * Ut^3 = V(127) ~ // 127 = M_7 is prime
V(2)~ * Ut^4 = V(M_127) ~ // M_127 is prime
... // prime ???


Well, may be there is indeed some information in this
all, worth to investigate it in more detail and generality.
What I fiddled with was the application of the Lucas-Lehmer-
test for Mersenne-primes in this matrix-framework.
In my other post I introduced the matrix-operator G for
the implementation of the function g(z) which replaces
the "Lucas-Lehmer-function" f(x) = x^2 - 2 by a function
without constant term g(z) = z^2 + 4z with the identity

f(x) = g(z-2) + 2

which holds also for iterates

f(f(x)) = g(g(z-2))+2

and allows to perform the Lucas-Lehmer-test using g(2)
instead of f(4) appropriately iterated depending on the
prime being tested.

The iteration of the function g(2) is expressible by powers
of the associated matrix-operator G. For the test of a prime
p I need p-2 iterations of f(4) or g(2) , or the matrix-
product V(2)~* G^(p-2) and then a test of the result
modulo 2^p-1

Here the significant entries in G^(p-2) reach up to row
2^(p-2), so for p=5 I test, whether with V(2)~*G^3 (mod 31)
the result is zero, using G only up to the indicated row
which is 2^3 = 8.

Now heuristically it seems, that I can assume

G^p == G (mod 2^p-1) // for a certain top-left-segment

up to the rownumber of significant entries in the second
column in G^p, and thus it seems I can use G^-2 for the
Lucas-Lehmer-test for all primes p since

G^-2 == G^(p-2) (mod 2^p-1)

in the relevant truncated size.


Or, in scalar notation, I can use

g°(-2) (2) (mod 2^p -1 )

where I need the powerseries of g(x) only up to the
"significant" exponent 2^(p-2), and g°(-2)(x) can be
determined by series-reversion.

The problem is, that the series inversion needs
2^(p-2) terms which is practical only for relatively
small primes p, so this is still not a full replacement
of the LL test.

On the other hand: the interesting thing is, that

G^-2 (or g°(-2)(2) )

is then one constant for LL-tests of all primes p, and
the problem of required number of iterations of g(2)
(or f(4)) is translated into a problem of summing a
powerseries (modulo 2^p -1) up to a certain index.

Besides its practical limitation I find this an
interesting translation of the LL-test... I'll be
checking later how far I can heuristically go with
this.

Gottfried









.

Relevant Pages