Conjectured compositeness tests for N=k⋅2n±c by Predrag

[T.Rex]

Originally Posted by axn

The s variable is a Mod() object. All operations with it will automatically work modulo N.

I should read again the documentation of PARI/gp... ;) However, I'm now involved with porting Ruby and Python3, and then Go, on AIX, so I'm fed up reading language documentation. So, I know very basic things about PARI/gp. Some time, when I have time, I'll read more ! ;) Anyway, thanks to help me understand. For now, I do not care about performance of PARI/gp programs.

[paulunderwood]

Is there any need to run verification now "mathlove" has proved this composite test?

Does it produce fewer pseudoprimes than base-a Fermat PRP tests?

[T.Rex]

About proving the sufficiency, I think that an issue (as I already said) is that s can be equal to sn before i==n-1 .
Finding s(n-1)==sn only after n-1 iterations and not before is important I think.
I think that it is important to add a check s!=sn after the computation of s from i=1,n-2 .

[science_man_88]

Originally Posted by T.Rex

About proving the sufficiency, I think that an issue (as I already said) is that s can be equal to sn before i==n-1 .
Finding s(n-1)==sn only after n-1 iterations and not before is important I think.
I think that it is important to add a check s!=sn after the computation of s from i=1,n-2 .

if it loops multiple times it should in theory loop at multiples of a divisor of n-2 if it's going to have the final result match, but of course that would mean n = all multiples of that divisor +2, should give prime N.

[T.Rex]

Originally Posted by paulunderwood

Does it produce fewer pseudoprimes than base-a Fermat PRP tests?

If we use the test as-is: ( if(s==sn && ! isprime(N) ), it produces pseudoprimes, like: 1*2^3+1 or 98*2^79+17 .

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : produces 34 pseudoprimes.

But, if we check that no S(i) is equal to S(sn-1) with i=1...n-2 , there are less.

... z=0; forstep(i=n,3,-1, s=sqr(s)-2; if(s==sn, z=1;break));
s=sqr(s)-2;
if(z==0 && s==sn && ! isprime(N), print("k: ",k," c: ",c," n: ",n)))

? for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : there are only 13.
k: 1 c: 1 n: 3
k: 15 c: 1 n: 3
k: 33 c: 25 n: 79
k: 35 c: 17 n: 83
k: 37 c: 17 n: 92
k: 45 c: 1 n: 3
k: 49 c: 17 n: 80
k: 66 c: 25 n: 78
k: 70 c: 17 n: 82
k: 74 c: 17 n: 91
k: 95 c: 17 n: 77
k: 97 c: 17 n: 48
k: 98 c: 17 n: 79

With c=1, 17, or 25 only, within the limits used for k, c and n.
However, there are others, like: 16*2^121+33 .

Up to now, for c>0, they all seem to appear when c = 1 mod 8 : 1, 17, 25, 33, 41, 73 .

For c<0, it seems to appear only with: c= 5, 29 , like: 8*2^158-29 or 11*2^232-5 .

[T.Rex]

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : there are only 13 pseudoprimes out of 5588 numbers verifying the test; including 5575 primes: 0.23% of pseudoprimes. Out of a total of 125,000 numbers N tested.

For c<0, there are 1.22% of pseudoprimes (72 out of 5866 numbers verifying the test, including 5794 primes). Out of a total of 125,000 numbers N tested.

[T.Rex]

Originally Posted by T.Rex

Up to now, for c>0, they all seem to appear when c = 1 mod 8 : 1, 17, 25, 33, 41, 73 .

There are also pseudo primes for c=89, but not with 81, 87, 105, with the following bounds:
for(k=1,300,CEk2c(k,89,300)) :
133*2^262+89
221*2^291+89
266*2^261+89

[Batalov]

A few trivial things about Chebyshev polynomials replace all that "mathlove" wrote in pages of scribbles in a simple way.
One has to admire how he repeated copy-pasted pages of similar arguments in each of the primus' questions (of which there are scores and the all look the same, only maybe with different values of c, or base). Do these guys ever get tired of typing?! I think not. Everyone gets their kicks of it. mathlove gets a load of stackexchange's "credits" (like PrimeGrid's, but slightly more useful perhaps) for answering the same question 20 times. Hats off to his/her stamina.

Ponder these:
1. https://en.wikipedia.org/wiki/Lissajous_curve :
2. Lissajous figures where a=1, b=N (with N a natural number) and are Chebyshev polynomials
3. Chebyshev polynomial (one of the definitions)
4. Using renormalized ; in particular {n times}.

So, the whole iterated calculation is a calculation of T_{k*2^n}(a) and comparing it to T_c(a) with some a value like . Because of periodicity of cos, the result is obvious. In a way, this is a "Fermat" test z^N = z ("mod" N) in complex plane and with irrational complex with imaginary half of calculations swept under the carpet, projected on real axis only. (A Frobenius PRP test?)

primus has been boring people with these trivialities for years now. Search this forum. And always it was "A new conjectured primality test bla-bla-bla" .
Only in 2015, he finally settled down for them as PRP tests, which they are; but as such, they are trivial!

All you need to realize is the property 4, which makes the purpose of iterations painfully obvious: you are calculating the , because N-c = k*b^n, then compare that the. Of course it is!

[T.Rex]

Originally Posted by Batalov

A few trivial things about... .... "A new conjectured primality test bla-bla-bla" .
O.... they are trivial!
.... Of course it is!

Hummm Sometimes, I'm saying myself that I should go back to photography and forget Maths, where I was not so good even before I forgot so many things !

Anyway, thanks for the explanations !

So, you transformed something mysterious into something nearly obvious... I'm sad ! But that's the (Math) rule/law.

Anyway, what is surprising me is that, with some modification of his algorithm, I no more can find pseudoprimes (which does NOT mean that there are no more, for sure).

In a previous post, I said that, with c>0, pseudoprimes seem to be only N=k*2^n+c where c = 1 mod 8.
If you eliminate Ns such that S(i)==S(n-1) with i<n-1, and then if you eliminate Ns such that N= 0 mod(2*c-1) , I no more find pseudoprimes. Last check means that remaining numbers Ns only have 2*c-1 as simple factor. The examples I have factored do confirm: they have a unic small factor (never prime) and a very big prime factor.

Examples (where N passes the test before my last filter and are pseudoprimes):
N=171*2^379+145 = 0 mod 17^2 , and 17^2=2*145-1 .
factor(171*2^379+145) : 17^2 * 728562182048384077130159586626790436923511614970760313605012778127813410783523249843408253631630684967337087623537

N=307*2^319+105 = 0 mod 11*19 and 11*19 = 2*105-1
factor(307*2^319+105) : 11*19 * 1568775167530429175347539865536010763595766240104048804721870271773735540226451313055142011218969

N=471*2^393+73 = 0 mod 5*29 and 5*29 = 2*73-1
factor(471*2^393+73): 5*29 * 65530155850158078972410448815378156940155788169319195826683219662211477907862726436991538868262118459391723814610133049

N=17*2^399+137 = 0 mod 3*7*13 and 3*7*13 = 2*137-1
factor(17*2^399+137): 3*7*13 * 80399721478896421289653161033060809274001828714463003146742141137712471747777106792498115395169126619799183010140489721

The same for a dozen of other similar pseudoprimes.

In short, the 2 filters I have added seem to remove all pseudoprimes (which are of a special form and could be used for finding other big primes).

That may hide something obvious, for sure. But, the algorithm below no more finds PRPs/pseudoprimes (or I haven't tested with large-enough numbers, for sure. Or my code is wrong.).
Would you mind explaining why it seems to work ?

CEk2c(k,c,g)=
{
a=6;
h=a/2;
if(c>0,s=1,s=-1;c*=-1);
for(n=c<<1+1,g,
N=k<<n+s*c;
e=c%4;
if(e==1,,e=-1);
d=((c-e)%8)/4;
f=((-1)^d);
B=f*s;
A=(c-B)/2;
s0=Mod(polchebyshev(k,1,h)<<1,N);
sn=Mod(f*polchebyshev(A,1,h)<<1,N);
my(s=s0);
z=0;
forstep(i=n,3,-1,s=sqr(s)-2;if(s==sn,z=1;break));
s=sqr(s)-2;
if(z==0 && s==sn, y=Mod(N,2*c-1);if(!isprime(N)&&y!=0, print(k,"*2^",n,"+",c)))
);
}

for(k=1,100,for(c=0,100,CEk2c(k,2*c+1,200)))
for(k=1,100,for(c=101,200,CEk2c(2*k+1,2*c+1,800)))

[Batalov]

Originally Posted by T.Rex

...If you eliminate Ns such that <<...>>, and then if you eliminate Ns such that <<...>>, I no more find pseudoprimes.

If you eliminate more and more, finally you simply get yourself in an illusory environment when you can no longer find counterexamples, -- and so what? It simply means that no one is willing to find them, but they are still there, only larger.

Compare it with the way this thread went,
and on to http://www.mersenneforum.org/showthr...943#post380943

This is long ago and well described by A.A. Milne as the character of Tigger.
Tigger first claims: 'Tiggers eat evertyhing'.
After being presented with honey, he "improves" his theory to 'Tiggers eat evertyhing except honey'.
After being presented with acorns, he further "improves" his theory to 'Tiggers eat evertyhing except honey and acorns'.
Can you blame anyone for not taking him all too seriously after that?

[T.Rex]

Originally Posted by Batalov

If you eliminate more and more, finally you simply get yourself in an illusory environment when you can no longer find counterexamples, -- and so what? It simply means that no one is willing to find them, but they are still there, only larger.
....
After being presented with acorns, he further "improves" his theory to 'Tiggers eat evertyhing except honey and acorns'.
Can you blame anyone for not taking him all too seriously after that?

Hummmmm I understand your point.
However, don't you think that there are other ways for finding new stuff than using pure Math proof ? Is there a place for experimenting ? Years ago, before computers were there, many mathematicians used pen, paper, and figures, for exploring something that looked weird for them at first, before they search for a math proof. Now, we have computers. Remember S. Ramanujan: he never used more than a slate since he was unable to pay for note-books and paper at first and because he had a wrong idea about what "good" maths are: find a property and PROVE it ; however his findings were remarkable and mathematicians are still studying his findings. However, there was only 1 Srinivasa...

Now, back to what I did:
- primus published 4 conjectures about a property of primes
- I generalized the conjectures into one
- someone proved the conjecture and, as you explained, it was not so difficult to prove and it is simply another way to present something already known
- however, what about pseudoprimes ?
- I found a limited number of pseudoprimes
- I used the idea: not only S(n-1) must have a special value Sn, but S(i) must not be equal to S(n) when i<n-1, because some Sn values are a dead-end, like 2 : 2^2-2=2 , and because we must not enter a cycle with length smaller than n-1, with the idea that a minimum of n-1 different steps are required for showing a prime, as for Mersenne/Fermat LLT. The other idea is that, for very simple numbers like Mersenne and Fermat, so close to 2^n, about n iterations of X^2-2 mod N is enough, though for numbers moving away from pure 2^n more steps should be required, which are the P_k and P(c) functions that add more steps before and after the (s^2-2 mod N) part. The idea is that there must be a minimum of steps to run in order to have something that can be a prime test. A number N being a prime creates a symmetric structure ; running a minimum number of steps in the structure of a number is required in order to discover if the symmetry is broken due to a factor of N. What is magic with LLT for Mersenne/Fermat is this: you run n-1 steps in the digraph, from a starting point to a ending point, and bingo! it is a prime. This should work, under more complex conditions, for other numbers, where starting and ending points are more difficult to define since they depend on other characteristics of the number than the power of n : k and c in addition, like primus did.
- then, I found that ALL the remaining pseudoprimes I can find (c>0) share the same characteristics: c= 1 mod 8 , and N=0 mod (2*c-1) .
- and then I shown that ALL these remaining pseudoprimes look strange: only 1 small factor (2c-1) and a big prime. They do NOT look like random factors as expected for random exceptions in the theory. They share a property, probably showing something deep and interesting to look at.
- and, at the end, filtering this unique class of pseudoprimes, I cannot find more pseudoprimes (up to the limits of my computer).

For sure, that does NOT provides a proof.
That is only showing "strange" properties that seem to exist with very big numbers and with a very big number of numbers tried.
And, as you say, after honey and acorns, there could be ants and mushrooms. Or not.

I remember an example from a book of JP Delahaye, where 2 sequences A(n) and B(n) generate coprime numbers ... up to n being very very big where an exception occured.

But, in our case, we are using methods that are well known and have already provided good results, like LLT for Mersenne numbers and LLT for Fermat numbers, which are true prime tests.
So, we have the expectation to find something that works, under strict conditions.

So, I have only used 2 filters.

Remind also that, for c<0, I found that all pseudoprimes I've found have the same structure.

For sure, there could be another kind of pseudoprimes with much higher values for: k, n, or c . And, in that case, the conjecture will be the Tiger you are talking about.