Looking for a "Universal Seed"

[T.Rex]

Hi,

In this post of this (long) thread, we talked about several conjectures, including this one:

Let q be a prime integer and M = (2^q-1).
S(0) = -10/3 and
S(i+1) = S(i)^2 - 2 (mod M) ;
M is prime iff S(q-1) == S(0) .

The seed (also called "initial value") S(0)=-10/3 (same as 3^(2^(q-1)) + 1/3^(2^(q-1)) ) can be replaced by 3^2+1/3^2 , or by 3^(q-1)+1/3^(q-1) or by 3^(q+1)+1/3^(q+1).

This conjecture makes use of cycles of length q-1 under x^2-2 modulo a Mersenne prime.

Now, I'm looking for a universal seed for cycles of length (q-1)/2 .
I mean, I'm looking for a formula, like: +/- A/B , or t^n+1/t^n, or anything else that generates a node belonging to a cycle of length (q-1)/2 under x^2-2 modulo a Mersenne prime for any q such that Mq is prime.

That means that this seed/node (let call it SN), succeeds to the following PARI/gp program for any q prime such that 2^q-1 is a prime and fails for the others:

M=2^q-1
SN=<a value/formula>
N=SN; for(i=1,(q-1)/2, N=(N^2-2)%M; if(N==SN, print("success"))

As an example, here is the code that shows that -10/3 is a universal seed for cycles of length (q-1)/2 (try it with several values for q):

M=2^q-1
SN=(-10/3)%M;
N=SN; for(i=1,q-1, N=(N^2-2)%M; if(N==SN, print("success"))

I've already searched a while and failed.
Now, I need your help.

Any idea ?
The formula could be close to a one already used for finding an appropriate seed for the LLT for numbers of the form: h2^n-1 (see work of O. Rodseth): V(0)=2 , V(1)=P, V(i+1)=P*V(i)-V(i-1) and SN=V(h) . But it is just a guess ...

Regards,

Tony

[maxal]

Originally Posted by T.Rex

That means that this seed/node (let call it SN), succeeds to the following PARI/gp program for any q prime such that 2^q-1 is a prime and fails for the others:

M=2^q-1
SN=<a value/formula>
N=SN; for(i=1,(q-1)/2, N=(N^2-2)%M; if(N==SN, print("success"))

This program will succeed with any cycle of length not exceeding (q-1)/2. Please clarify whether you are happy with
(i) a cycle shorter than (q-1)/2;
(ii) a cycle of length precisely (q-1)/2;
(iii) a cycle of length dividing (q-1)/2.

[T.Rex]

Originally Posted by maxal

This program will succeed with any cycle of length not exceeding (q-1)/2. Please clarify whether you are happy with
(i) a cycle shorter than (q-1)/2;
(ii) a cycle of length precisely (q-1)/2;
(iii) a cycle of length dividing (q-1)/2.

Oops. I made a mistake ! Sorry.
The following code does find a seed leading to a cycle of length (q-1)/2 (if it says "success" and no "wrong" before) .

FindSeed(q,M,SN)=
{
N=SN%M;
for(i=1,(q-1)/2-1, N=(N^2-2)%M; if(N==SN, print("wrong")));
N=(N^2-2)%M;
if(N==SN, print("success"),print("failed"))
}
q=7
M=2^q-1
FindSeed(q,M,("Your formula here!")%M)

Try with FindSeed(7,127,2).

However, I would be very pleased also if someone finds a seed leading to:
(iii) a cycle of length dividing (q-1)/2, but not equal to 1.

But a seed leading to:
(i) a cycle shorter than (q-1)/2, but not dividing (q-1)/2, is not possible, if M is prime.

Thanks for looking at my (wrong) code !

Tony

[m_f_h]

I think it's a good idea to re-activate this topic: finding a
necessary condition taking only half the number of iterations would
double efficiency of the Mersenne hunting.

I'm not sure to find the time to fiddle around with PARI so I just give some telegraph style suggestions:

• It would be less confusing to call your code TestSeed() rather than FindSeed()
• stop scanning when found N=SN (do "break" or "return" instead of "print")
• if # iterations to reach N=SN is a divisor of (q-1)/2 (+/-1 ?) then you get the same value at the end, else not
  (essentially TestSeed() would return the length of the cycle SN is part of, or 0 if it isn't)
• using PARI's Mod(,) type would simplify the code
• one could write a FindSeek() scanning reasonable values for SN (using TestSeek()), for each "Mersenne q" (certainly not SN=1...Mq for large q.... also your suggestion of "2" seems not very promising to me , so I'd rather start with SN >= 3)

PS: why do you call "wrong" if the cycle's length is < q/2 ? Is it known if the LL cycle must be of length q for Mersenne q ? Since we seek only a necessary condition, maybe a unversal seed for a shorter cycle (of length dividing q) would be just as fine ? (Sorry if this comment is completely stupid, I don't remember well what we know about length of cycles...)

[m_f_h]

/* returns length of cycle if SN is part of a cycle of length < q/2, else 0 */
TestSeed( SN /* seed of Mod() type */, q )={ local( cnt=floor(q/2), S=SN );
 while( cnt-- & SN != S=S^2-2, /*print(S)*/ );
 if( cnt, floor(q/2)-cnt /* length of cycle */
 , if( SN == S^2-2, floor(q/2), 0 ))}
 
/* for all pseudoprime 2^q-1, scan all seeds from -sqrt(2^q) .. sqrt(2^q) */
ScanSeed( qMax )={ local(l);
 forprime( q=1, qMax, if( !ispseudoprime(2^q-1), next);
  for( s=ceil(-2^(q/2)),2^(q/2), if( (l=TestSeed( Mod(s,2^q-1), q)) & (q-1)%l==0,
   print("found seed in cycle of length dividing q-1: [S,L,q]=",[s,l,q])
 )));}
 
ScanSeed(60)

found seed in cycle of length dividing q-1: [S,L,q]=[-1, 1, 2]
found seed in cycle of length dividing q-1: [S,L,q]=[2, 1, 2]
found seed in cycle of length dividing q-1: [S,L,q]=[-1, 1, 3]
found seed in cycle of length dividing q-1: [S,L,q]=[2, 1, 3]
found seed in cycle of length dividing q-1: [S,L,q]=[-1, 1, 5]
found seed in cycle of length dividing q-1: [S,L,q]=[2, 1, 5]
found seed in cycle of length dividing q-1: [S,L,q]=[-1, 1, 7]
found seed in cycle of length dividing q-1: [S,L,q]=[2, 1, 7]
found seed in cycle of length dividing q-1: [S,L,q]=[-5, 6, 13]
found seed in cycle of length dividing q-1: [S,L,q]=[-1, 1, 13]
found seed in cycle of length dividing q-1: [S,L,q]=[2, 1, 13]
found seed in cycle of length dividing q-1: [S,L,q]=[23, 6, 13]
found seed in cycle of length dividing q-1: [S,L,q]=[-1, 1, 17]
found seed in cycle of length dividing q-1: [S,L,q]=[2, 1, 17]
found seed in cycle of length dividing q-1: [S,L,q]=[213, 8, 17]
found seed in cycle of length dividing q-1: [S,L,q]=[-1, 1, 19]
found seed in cycle of length dividing q-1: [S,L,q]=[2, 1, 19]
found seed in cycle of length dividing q-1: [S,L,q]=[459, 6, 19]
found seed in cycle of length dividing q-1: [S,L,q]=[632, 9, 19]
found seed in cycle of length dividing q-1: [S,L,q]=[-1, 1, 31]
found seed in cycle of length dividing q-1: [S,L,q]=[2, 1, 31]
found seed in cycle of length dividing q-1: [S,L,q]=[16205, 15, 31]
time = 2,188 ms.

ScanSeed(61) would take a bit longer, so now, the formula is needed...

[maxal]

Originally Posted by T.Rex

But a seed leading to:
(i) a cycle shorter than (q-1)/2, but not dividing (q-1)/2, is not possible, if M is prime.

Take q=13, M=2^13-1=8191, M is prime.
There is a cycle mod M:
2094 -> 2649 -> 5703 -> 5937 -> 2094
of length 4 which shorter than (q-1)/2=6 and does NOT divide 6.

[R.D. Silverman]

Originally Posted by m_f_h

I think it's a good idea to re-activate this topic: finding a
necessary condition taking only half the number of iterations would
double efficiency of the Mersenne hunting.

Damn it! I have said this before, but the message doesn't seem to get
through to people.

It would NOT "take half the iterations". It would only take ONE FEWER
iteration. A cycle of length (p-1)/2 is ONE BIT LESS than a cycle of length
p. The computation requires a number of squarings equal to the BIT SIZE
of the exponent.

Computing a^( (p-1)) takes only ONE MORE multiplication than
computing a^ ( (p-1)/2) ; just square the latter.

To get half the number of iterations you need a cycle of length ~ sqrt(p),
and NOT (p-1)/2

To compute a^1000000 takes only twice the work of a^1000, and not
1000 x the work.

To compute (say) a^83 only takes one more squaring than computing a^41

[R.D. Silverman]

Originally Posted by R.D. Silverman

Damn it! I have said this before, but the message doesn't seem to get
through to people.

It would NOT "take half the iterations". It would only take ONE FEWER
iteration. A cycle of length (p-1)/2 is ONE BIT LESS than a cycle of length
p. The computation requires a number of squarings equal to the BIT SIZE
of the exponent.

Computing a^( (p-1)) takes only ONE MORE multiplication than
computing a^ ( (p-1)/2) ; just square the latter.

To get half the number of iterations you need a cycle of length ~ sqrt(p),
and NOT (p-1)/2

To compute a^1000000 takes only twice the work of a^1000, and not
1000 x the work.

To compute (say) a^83 only takes one more squaring than computing a^41

I went back and took a look at the original question. There is some
confusion about *nomenclature*. The confusion may be mine.

If one reduces the number of *iterations* from p to (p-1)/2, then one *does* indeed cut the number of iterations in half. But this does not cut the
*cycle length* in half. The number of iterations is not the same as the
cycle length. The O.P. was talking about the exponent n for M_n = 2^n-1
while I was taking p to be the Mersenne prime itself, not the exponent.

Let's go back behind the scenes.

One one does an ordinary prp test, one works in a (purported) cyclic
group. One takes an element of Z/NZ* and hopes that the length of its orbit (its cycle length) is indeed N-1. The cycle length is the size of
the group. If the group is cyclic then VOILA: we have a prime

For P = M_p = 2^p-1, the Lucas Lehmer test is actually doing an
exponentiation in the finite field GF(P^2). It is doing this exponentiation
in a disgusied way inside the twisted subgroup of order P+1 = 2^p of this
finite field.

When one does p squarings as S_n = S_n^2 - 2 starting with S_0 = 4,
one is really computing in the orbit of an element of the finite field.
Computing p squarings actually computes a number that is O(4^(2^p)),
i.e. doubly exponential. The cycle length is 2^p, not p. The number
of *iterations* is p, but this is NOT the cycle length. The prior posts
talked about cycle length, which I took to mean the real cycle length,
but the posts were really equating cycle length with number of iterations
when the two are not the same. Reducing the *cycle length* from n
to (n-1)/2 really does only save 1 iteration as I said. But the *cycle length*
is not the same as the number of iterations. The number of iterations is
O(lg(cycle length)) where lg is base-2 log. The confusion arises from
the mixing of the terms "iterations" and "cycle length". Perhaps the confusion
is mine only.

We had confusion over terminology.

I think it unlikely that an element of GF(P^2) [note capital P] exists
that will permit only (p-1)/2 [note small p] iterations. Of course, I could
be wrong; I've been wrong before. In fact, I would be very happy to be
wrong.

The reason I think it unlikely is due to a result of Pomerance (and also
R. Karp) regarding the length of certificates of prime proving algorithms.
The result says that there exist certificates that are of compute length O(log(P)^3). [or O(log(P) M(p)) where M(p) = O(log^2 P) is ordinary
multiplication time while FFT multiplication reduces this to M(p) = O(log p loglog p) ]

Finding a Mersenne Prime test that only takes (p-1)/2 iterations would
substantially lower the implied [multiplicative] constant in the O() estimate.
I would be surprised [pleasantly surprised] if such were possible.

[T.Rex]

Originally Posted by maxal

Take q=13, M=2^13-1=8191, M is prime.
There is a cycle mod M:
2094 -> 2649 -> 5703 -> 5937 -> 2094
of length 4 which shorter than (q-1)/2=6 and does NOT divide 6.

Oops. I meant to say ( q-1 instead of (q-1)/2 ):

But a seed leading to:
(i) a cycle shorter than (q-1)/2, but not dividing q-1, is not possible, if M is prime.

Sorry for my mistake ...
Length of cycles must divide q-1 .

T.

[T.Rex]

Originally Posted by R.D. Silverman

I went back and took a look at the original question.

...

Finding a Mersenne Prime test that only takes (p-1)/2 iterations would
substantially lower the implied [multiplicative] constant in the O() estimate.
I would be surprised [pleasantly surprised] if such were possible.

I used the vocabulary used by Shallit & Vasiga in their paper : cycles are what you can draw with a pencil on a paper. If you need 4 steps of x^2-2 to go from S back to S, then you have drawn a cycle of length 4 . Probably this kind of cycle is different from the one you had in your head first. But my vocabulary is coherent with the paper of Shallit&Vasiga and what you can experiment.

About your last comment about the minimum number of iterations required to prove that a Mersenne is prime, I DO agree with you that it must be around p (or p-1 or p-2) for a Mersenne 2^p-1 .

The goal of my question in this thread is to find a Universal seed (I mean a seed that works for any p such that 2^p-1 is prime) for a cycle (under x^2-2) of length (p-1)/2 .
If we find such a seed and use it with an exponent (so running (p-1)/2 iterations), it is correct that we cannot prove that this Mersenne is prime. For sure.

My conjecture is that, instead of doing the LLT (p-2 iterations), and instead of doing a modified LLT running a cycle of length p-1 (p-1 iterations), we could run TWO cycles of length (p-1)/2 , these 2 cycles being connected by the x^3-3x function (Dickson polynomial).
Then, if the first (p-1)/2 cycle fails, that would mean that the tested Mersenne is not prime.

Then, if the first (p-1)/2 cycle succeeds, we have to run the second cycle of length (p-1)/2.
If this second cycle fails, then the Mersenne is not prime. Otherwise, it is a prime.
So, as a summary, we still have to run p-1 iterations of x^2-2 to prove that a Mersenne is prime. BUT, we could prove that a Mersenne is composite with only (p-1)/2 iterations.
Since there are MUCH more composite Mersennes than prime Mersennes, we win ! (if my conjecture is correct and can be proven,for sure).

Juste notice that you could do the same with any d such that d divides (p-1). So, you would have to run d cycles of length (p-1)/d for proving that the Mersenne is prime. BUT, for a Mersenne composite, I expect that an attempt to run the Nth cycle of length (p-1)/d fails ; and N could be small compared to d, because the number of cycles that obey the rules for a Mersenne composite seems to be much much smaller than expected for a Mersenne prime.

Now, better.
One can prove that a Fermat is prime with the LLT (Lucas, my-self, and others have provided proofs).
Consider F33. It would take about 4000 years to prove it is a prime or a composite on a fast CPU. If my conjecture is true, then - since 2^33-1 = 7*23*89*599479 - we could prove that F33 is prime (or composite) in about 1 year if we could distribute the verification of the 2047 cycles of length (2^33-1)/2047 on 2047 machines with 2 cores, using the version 25.2 of prime95, running in parallel, each running its own (2^33-1)/2047 cycle.

OK. Now, I only have a conjecture and I'm dreaming. But it could be true some day ...

What is your opinion ?

Tony

[cheesehead]

I'm out of my depth here, but I do have one question for which I don't see (or, perhaps, have simply overlooked) the answer:

Originally Posted by T.Rex

My conjecture is that, instead of doing the LLT (p-2 iterations), and instead of doing a modified LLT running a cycle of length p-1 (p-1 iterations), we could run TWO cycles of length (p-1)/2 , these 2 cycles being connected by the x^3-3x function (Dickson polynomial).
Then, if the first (p-1)/2 cycle fails, that would mean that the tested Mersenne is not prime.

How often would one expect that to happen?

IOW, for what fraction of composite Mersennes would the first (p-1)/2 cycle fail? Call this the "failure fraction". If that "failure fraction" is asymptotically tiny, then the practical savings, compared to LL, will be tiny -- right?

you could do the same with any d such that d divides (p-1). So, you would have to run d cycles of length (p-1)/d for proving that the Mersenne is prime. BUT, for a Mersenne composite, I expect that an attempt to run the Nth cycle of length (p-1)/d fails ; and N could be small compared to d, because the number of cycles that obey the rules for a Mersenne composite seems to be much much smaller than expected for a Mersenne prime.

Here, too: What is the expected average of N/d ("failure fraction" = 1 - N/d)? If N/d asymptotically => 1 ("failure fraction" => 0), there won't be much practical savings versus LL.

OK. Now, I only have a conjecture and I'm dreaming. But it could be true some day ...

What is your opinion?

Definitely worth investigating (says he who is out-of-depth)! Even if this conjecture in its current form fails, there could still be something that hints at a related approach.

For instance, the "failure fractions" that I'm asking about -- are there any special cases?

(And, for real silliness -- is there any connection between what I've labelled as "failure fractions" and the failure functions I vaguely recall having been mentioned in other forum threads in a different context?)