Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1)

[m_f_h]

Originally Posted by T.Rex

I have studied (by program ...) the Digraph produced undex x^2-2 modulo a Wagstaff prime.
The conclusion is that there is no tree, like with Mersenne numbers, which could be used for building a LLT test S(p-2) == 0 (mod W).
There is no tree at all. Only Cycles.

for W(5)=11 :
-1 <- 1 <- +/- 5
?

[T.Rex]

Originally Posted by m_f_h

for W(5)=11 :
-1 <- 1 <- +/- 5?

OK. Cycles with tails of length 1 as a maximum.
T.

[m_f_h]

Originally Posted by T.Rex

OK. Cycles with tails of length 1 as a maximum.
T.

It seems..
(I would call these trees of height 2)

For W(7)=43, in the cycle 4 14 22 9 36,
each element has a small tree attached to it,
2 <- -2 <- 0 is special
the other cycles have only a tree of height 1 (i.e. 1 node) attached

For W(11) and W(13), it looks alike...
eg for W13, cycles of length 11 have small trees, cycles of length 2,3,6,12 dont have.
Conjecture:
for Wp, cycles of length dividing p-1 dont have trees, cycles of length p-2 DO have trees of height 2 attached. (The tree attached to x in a cycle of length L being of the form: x <- -LL^(L-1)(x) <- +/- f(x).)
(The cycle {2}<- -2 <- 0 being excluded from that consideration; to be on the safe side, lets exclude all cycles of length 1.)

[T.Rex]

Originally Posted by T.Rex

Does anyone have any idea for completing my proof of my conjecture of the LLT-like test for Mersenne described at: http://tony.reix.free.fr/Mersenne/Co...esMersenne.pdf ?

I now have a proof for the first part: ConjectureLLTCyclesMersenne2.pdf.
Not so difficult if you think to use the Little Fermat Theorem at the right place ! (thanks to HC Williams for his hint).
Now, I need a proof for the converse. Any idea ?
Regards,
Tony

[m_f_h]

Originally Posted by T.Rex

I now have a proof for the first part: ConjectureLLTCyclesMersenne2.pdf.

I don't understand :

   ... alpha = 1/9 (mod Mq) = (Mq-1)²/9 so that \alpha always is an integer.

I mean, on one hand 1/9 (mod Mq) can mean the multiplicative inverse of 9 in Z/(Mq) (which is a field if Mq is prime).
saying \alpha = x (mod y) either means that \alpha is ANY number in the same class than x (both integers), or that alpha is the same class than x (both elements of Z/(Mq))
The expression (Mq-1)²/9 clearly is not smaller than Mq and thus not a canonical representative.
it's of course a representative of 1/9 (inverse of 9 in Z/Mq)
since (Mq-1)²= (-1)²=1 (mod Mq)
thus (Mq-1)²/9 = 1/9 (mod Mq), however the r.h.s is not an integer.

[T.Rex]

Originally Posted by m_f_h

I mean, on one hand 1/9 (mod Mq) can mean the multiplicative inverse of 9 in Z/(Mq) (which is a field if Mq is prime).

It is. Maybe I'm not saying that with the good notation.

saying \alpha = x (mod y) either means that \alpha is ANY number in the same class than x (both integers), or that alpha is the same class than x (both elements of Z/(Mq))

Agree

The expression (Mq-1)²/9 clearly is not smaller than Mq and thus not a canonical representative.

No. I didn't write it this way. I also forgot the mod Mq. I should have said: ((Mq-1)/3)² mod Mq, in order to find an integer < Mq. Check with PARI/gp : (1/9)%127 = 113 = (((127-1)/3)^2)%127 .
It's just a trick for computing an integer between 0 and Mq-1.
Tony

[m_f_h]

Originally Posted by T.Rex

(1/9)%127 = 113 = (((127-1)/3)^2)%127.

(of course since 127=0 mod 127)

It's just a trick for computing an integer between 0 and Mq-1.

Oh I think I see what you mean. But (Mq-1)/3 not an integer for all primes q. Well, ok, for almost all...
But then again, it's not clear why alpha > 9. At least it's wrong for M3 and M5.

[T.Rex]

Originally Posted by m_f_h

Oh I think I see what you mean. But (Mq-1)/3 not an integer for all primes q. Well, ok, for almost all...

You're right, I should say q>2 here.

But then again, it's not clear why alpha > 9. At least it's wrong for M3 and M5.

You're right again. It's true if q>5. And I need to add a proof.
Thanks,
T.

[T.Rex]

Here is a better version: ConjectureLLTCyclesMersenne.pdf.
T.

[T.Rex]

Last link to version 0.3 was wrong. Here it is: ConjectureLLTCyclesMersenne.pdf.