OEIS - A050414 - 2^n-3 - LLT-like algorithm for finding PRPs
 

Here are two LLT-like algorithms for finding all PRPs produced by N=2^n-3 .

In short : choose a "good" seed S0, run s(i+1) = s(i)^2-2 modulo N a "good" number f(n) of times.
Then, if s(f(n))==S0, it says that N is a PRP (a PRobable Prime).
s(f(n))==S0 means that the llt x :--> x^2-2 has run in a cycle in the DiGraph modulo N.

The first one deals with PRPs N=2^n-3 where n is not a multiple of 4 (Seed=7, run n-2 iteration) :
[CODE]for(n=2, 1000, N=2^n-3; S0=7; x=S0; for(i=1, n-2, x=Mod(x^2-2,N)); if(x==S0, print1(n,", ")))
2, 3, 5, 6, 9, 10, 14, 22, 29, 94, 122, 150, 174, 213, 221, 233, 266, 545, 689, 694, 850,[/CODE]

This second one deals with PRPs N=2^n-3 where n is a multiple of 4 (Seed=8, run n-1 iteration) :
[CODE]for(n=4, 10000, N=2^n-3; S0=8; x=S0; for(i=1, n-1, x=Mod(x^2-2,N)); if(x==S0, print1(n,", ")))
4, 12, 20, 24, 116, 336, 452, 1736[/CODE]

These 2 algorithms seem to produce all elements of: A050414 :
[URL="https://oeis.org/A050414"]https://oeis.org/A050414 [/URL]
[CODE]3, 4, 5, 6, 9, 10, 12, 14, 20, 22, 24, 29, 94, 116, 122, 150, 174, 213, 221, 233, 266, 336, 452, 545, 689, 694, 850, 1736, 2321, 3237, ...
[/CODE]

As I said in another thread, the idea is to show that the LLT-like algorithm using a cycle instead of the tree can be used for much more numbers than for Mersenne and Fermat numbers. However, for Mersenne and Fermat numbers, there are proofs stating that the LLT finds Primes. However, for Wagstaff numbers ( (2^q+1)/3 ), only one part of the proof has been found (if W is prime, then the LLT cycle exists). For the numbers I have opened threads recently (2^n+3, 2^n+5 n odd, (2^n+5)/3 n even), and for this new one, there is no proof yet that the LLT-like algorithms I have found find Primes, rather there are only experiment facts showing that the algorithms find no false positive and no false negative compared to what we know. Thus, these algorithms COULD be a specific way for proving that these numbers are prime, once someone has provided a proof... ;) So, read Hugh C. Williams book about Edouard Lucas work, read my papers, and ... try to build a prrof ! And, if someone takes time to implement the algorithms in a fast tool (like Jean Penné did for Reix-Vrba algorithm for Wagstaff numbers), these algorithms could find big PRPs.

[B]Your mission is[/B]: check my algorithms independently and then use bigger n and check that my algorithms continue to provide good results.

[QUOTE=T.Rex;409047]
[B]Your mission is[/B]: check my algorithms independently and then use bigger n and check that my algorithms continue to provide good results.[/QUOTE]

No, this is NOT the mission of others.

(1) Please define what you mean by "good" results. QUANTIFY IT. (Hint: Grantham provided a probability bound)
(2) We already KNOW that these are just special instances of Grantham's Frobenius tests. We do not NEED
to perform computations so that they "continue to provide good results".

If people want to pursue prime numbers of special form because it is fun, then GO FOR IT. A approve. (not that
you need my approval)

But stop pretending that such computations will further validate "your algorithms".

And it is sheer arrogance on your part to claim them as your own. Other people found them well
before you did.

[QUOTE=T.Rex;409047]
[B]Your mission is[/B]: check my algorithms independently and then use bigger n and check that my algorithms continue to provide good results.[/QUOTE]

Tony, testing something that is growing exponentially with a Fermat/Lucas/Frobenius PRP test will not get you very far. It is like testing 2^p-1 is a 3-PRP. Contrast this with...

:direction:

I have tested x^2-2 as a 2-PRP implies primality and is (probably) good for odd x<10^13. Yet this grows only quadratically :smile:

[QUOTE=R.D. Silverman;409070](not that you need my approval)[/QUOTE]

Exactly.

Here are links to some Math papers that provide information about DiGraph under x^2-2 modulo N and how it can be used for building primality proofs using the LLT algorithm.

[URL="https://trex58.files.wordpress.com/2009/01/newvasiga.pdf"]On the iteration of certain quadratic maps over GF(p)[/URL] by Troy Vasiga Jeffrey Shallit
[URL="http://www.genomine.org/papers/fdqmmp.pdf"]FUNCTION DIGRAPHS OF QUADRATIC MAPS MODULO p[/URL] by Gilbert and al. See page 12 about x^2-2 .
[URL="http://tony.reix.free.fr/Mersenne/LoopsUnderLLTmodMersennePrime.pdf"]On Digraphs under x^2 and x^2-2 modulo a Mersenne Prime[/URL]
[URL="http://robert.gerbicz.googlepages.com/Fermatnumbers.pdf"]A LLT-like test for proving the primality of Fermat numbers.[/URL] by Gerbicz
[URL="http://arxiv.org/PS_cache/arxiv/pdf/0705/0705.3664v1.pdf"]A LLT-like test for proving the primality of Fermat numbers.[/URL]
[URL="http://tony.reix.free.fr/Mersenne/ConjectureLLTCyclesMersenne.pdf"]A LLT-like test for Mersenne numbers, based on cycles of the Digraph under x^2-2 modulo a Mersenne prime[/URL] A conjecture needing a complete proof.
[URL="http://www.ejpam.com/index.php/ejpam/article/viewArticle/245"]Equivalence of Pepin's and the Lucas-Lehmer tests[/URL] by John H. Jaroma


About Mersennes, the « Lucas-Lehmer Test for Mersenne numbers » (LLT in short) is the most efficient primality test ever built for any number.

About Fermats, the Pépin test is usually used ; however I’ve produced in 2004 a primality test for Fermats that makes use of a LLT with 5 as seed, and I’ve recently discovered that Kustaa Inkeri provided in 1960 a proof of such a LLT with 8 as seed. In 2009, John H. Jaroma provided a new proof in 2009.

About Wagstaff numbers, no efficient primality test is known yet. However, there exist tests that can show that a Wagstaff number is a PRP (Probable Prime), or not.

Using the LLT means that we travel from a seed (4 for Mersennes ; 5 or 8 for Fermats) to 0 after q-2 steps for a Mersenne and 2^n-2 steps for a Fermat. There are many possible seeds that can be used ; but only a small number of universal (independent of q or n) seeds are known. All the possible seeds and the intermediate values that are crossed build a Tree (2 branches lead to 1). The complete graph is called a DiGraph under x^2-2 modulo a prime number (see Shallit & Vasiga work). Such a DiGraph is made of Trees and Cycles. Often, small trees are attached to cycles.

About Mersenne and Fermat numbers, the DiGraph is made of one unique big Tree and of many Cycles, with length dividing q-1.

About Wagstaff numbers, there are only Cycles ; so the LLT does not work here. For a Wagstaff number, it could be possible of « proving » (once the conjecture is proven…) that it is a prime only thanks to a Cycle (this is called a modified LLT) : instead of reaching 0 after a number of steps, the iterations S_j = S_{j-1}^2 - 2 return to the seed S_0.

[QUOTE=R.D. Silverman;409070]
(2) We already KNOW that these are just special instances of Grantham's Frobenius tests.[/QUOTE]

I've read his paper and I see nothing dealing with modified LLT algorithm and with DiGraph under x^2-2 mod N.
Moreover, he talks about pseudoprimes that fake to be prime when using some property (N prime ==> property is true). He does not talk about algorithms that fake to find all primes of a kind of numbers.

All the numbers in [url]https://oeis.org/A050414[/url] gives a positive. No false positive up to 26k.

[url]https://oeis.org/A050414[/url] says "prime" but some of those listed are not [I]proven[/I] prime. How do you know there is not a coincidental LLT pseudoprime and a pseudoprime to whatever test was used for A050414? :smile:

[QUOTE=T.Rex;409112]He does not talk about algorithms that fake to find all primes of a kind of numbers.[/QUOTE]Why should we care about these? We can do a very simple and fast 2PRP test to find all primes (and some other numbers, but [U]no prime[/U] will be missed). And it can be applied to anything, regardless of form.

The real challenge is to separate the PRPs in primes and pseudoprimes.

[QUOTE=R.D. Silverman;409070]And it is sheer arrogance on your part to claim them as your own. Other people found them well before you did.[/QUOTE]
I never said explicitely: "Hey ! I've found something that [B]no one[/B] has found before me !"
AFAIK, people started to look at using cycles of a DiGraph under x^2-2 modulo N for primality testing only AFTER Vrba and I produced our algorithm for Wagstaff numbers. Before us, people were only using a recurrence ending at 0 mod N.
Anyway, I may be wrong and I may not be the first guy to find them. But you have to prove it.
So, it is sheer arrogance on your part to claim [B]without providing evidence[/B] that I'm not the first to find these results.

[QUOTE=LaurV;409164]Why should we care about these? We can do a very simple and fast 2PRP test to find all primes (and some other numbers, but [U]no prime[/U] will be missed). [B]And it can be applied to anything, regardless of form[/B].
The [B]real challenge[/B] is to separate the PRPs in primes and pseudoprimes.[/QUOTE]
Using a LLT is specific to a sequence of numbers. And the conjecture is that it is not a test for PRPs, but a property of the primes of this sequence. It is like LLT for Mersennes: we use it to find primes, not PRPs. The conjecture is that these modified LLTs, which provide for now only PRPs, could be turned into a theorem some day. Unless, for sure, it is not a theorem ! ;) However, these cycles have the same kind of magic that the classic LLT has. The challenge is to find a Math proof for these modified LLT conjectures. Or to provide pseudopromes for these modified LLTs, showing that I'm all wrong.