Looking for a "Universal Seed"
 

Hi,

In this [URL="http://www.mersenneforum.org/showpost.php?p=81270&postcount=39"]post[/URL] of this (long) [URL="http://www.mersenneforum.org/showthread.php?t=5935"]thread[/URL], 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:

[code]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"))[/code]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):

[code]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"))[/code]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

[SIZE=1][/SIZE]

[QUOTE=T.Rex;103767]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:

[code]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"))[/code][/quote]
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.

Better code
 

[QUOTE=maxal;103831]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.[/QUOTE]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) .
[CODE]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)
[/CODE]
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

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:[LIST][*]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 :wink: , so I'd rather start with SN >= 3)[/LIST]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...)

[code]/* 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)
[/code]
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...

[QUOTE=T.Rex;103901]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.[/QUOTE]
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.

[QUOTE=m_f_h;103958]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.

[/QUOTE]

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

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

[QUOTE=R.D. Silverman;104028]Damn it! I have said this before, but the message doesn't seem to get
through to people. :furious: :devil: :bob: :bob:

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[/QUOTE]

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.

[QUOTE=maxal;104022]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.[/QUOTE]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.

[QUOTE=R.D. Silverman;104033]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.[/QUOTE]
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

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:

[quote=T.Rex;104039]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.[/quote]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?

[quote]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.[/quote]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.

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

What is your opinion?[/quote]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 [I]failure functions[/I] I vaguely recall having been mentioned in other forum threads in a different context?)