A Universally derided "primality test".

[RMLabrador]

AKS, i'm aware about) Symmetry is much better. Currently, I'm going on to the proof that not exist even false (from modulo flaw) symmetry break in the form of [u,p-1;p-1,u]

[CRGreathouse]

Has anyone coded this in PARI/GP so we can test various ranges?

[carpetpool]

Originally Posted by RMLabrador

The symmetry is the key to build test.I'm the only one here who sees symmetry???
check this.Attachment 23343
in this form, no counterexamples, no one pseudoprime will pass this test. Problem in computation of this numerical.

We need an easy computational method to compute b(u) (if deg(b(u)) = p, then forget it, it's practically impossible to compute ). Anyone?

[RMLabrador]

(10:14) gp > { n=5; A=[1,1;1,u];P=[1,1;1,n-u+2];A=P^n-A^n; P=[0,1;1,0];A*=P; print((trace(A)))}
-60*u^3 + 630*u^2 - 3170*u + 5950
(10:15) gp > { n=5; A=[1,1;1,u];P=[1,1;1,n-u+2];A=P^n-A^n; P=[0,1;1,0];A*=P; b=factor(trace(A));print(b)}
[2*u - 7, 1; 3*u^2 - 21*u + 85, 1]
(10:15) gp > { n=5; A=[1,1;1,u];P=[1,1;1,n-u+2];A=P^n-A^n; P=[0,1;1,0];A*=P; b=factor(trace(A)/2);print(b)}
[2*u - 7, 1; 3*u^2 - 21*u + 85, 1]
(10:16) gp >

Greting! This Pari/GP bug, or i miss something in factor() parameters?
If not, PG eat a factor, clearly from first row to last.

Test with almost done, for some numbers symmetry is "broken" for some p, and some u, n-u+2, in form [u,p-1;p-1,1] opposite Carmichael numbers [1,1;1;u] I show you later, with proof of course, that happens only for those that have this at u=0, u=2 values
{forstep(p=1,100000000,2,if(isprime(p),,
A=Mod([1,1;1,0],p)^p;B=[0,p-1;p-1,1]; T=lift(lift(A))%p;
if(T==B,A=Mod([1,1;1,2],p)^p;B=[2,p-1;p-1,1];T=lift(lift(A))%p;
if(T==B,print([p,lift(lift(A))];)))))}
[5777, [2, 5776; 5776, 1]]
[10877, [2, 10876; 10876, 1]]
[75077, [2, 75076; 75076, 1]]
[80189, [2, 80188; 80188, 1]]
[100127, [2, 100126; 100126, 1]]
[113573, [2, 113572; 113572, 1]]

So for proof this (i post full PG code later) stupid test IS correst for all numbers, we must only proof that only Carmichael and this numbers is broke the symmetry in modulo computation
This is stupid, as far as i have the proof. that only prime numbers posses the symmetry u <-> n-u+2.
first thing first - what with Pari/GP factoring?
Other math system work well,

[Dr Sardonicus]

Here is one proof that b(u) == b(p-u+2) (mod p) if p is prime. [I replace 2+p-u by 2-u since the two are identical (mod p).]

The characteristic polynomial x^2 - (u+1)*x + u-1 of the matrix A has discriminant Δ = (u-1)^2 + 4, which is invariant under the substitution u <-- 2 - u. Therefore, the quadratic character the (Δ/p) remains the same under the substitution, so for p prime the off-diagnal entries of A^p (mod p), which by formula are 1,-1, or 0 (mod p) for u in Z/pZ^x, remain invariant also. Therefore, if b(u) is the off-diagonal polynomial in A^p, b(u) = b(2-u) has at least p-1 roots (mod p). Since b(u) has degree p-1, the two polynomials are identical (mod p), so their difference is identically 0 (mod p).

I haven't looked at the claim that b(u) is an irreducible polynomial when p is prime. I do know that if m divides n then b(m) divides b(n), so b(n) is not irreducible if n is composite.

I don't have a convenient formula for the coefficients of b(u). I therefore also don't know whether (a) computing them can be done as conveniently as the binomial coefficients, or (b) whether anything like the method used in the proof of AKS can be applied to the polynomials b(u).

EDIT: My proof as stated isn't quite right. Two polynomials which evaluate the same for as many argument values as their degree need not be identical. This is easily seen for degree 1: two lines can have 1 point in common without being the same line.

The simplest correction is to add the hypothesis (satisfied by b(u) and b(2-u) (mod p) if p is prime) that the two polynomials have the same leading coefficient. Then their difference is a polynomial in F_p[x] with more zeroes than its degree, which is, ipso facto, identically zero. Another correction would be to show that b(u) and b(2 - u) are equal for all p values of u (mod p).

Note that, if n is composite, the integers mod n do not form a field, so the above argument does not apply.

[RMLabrador]

Very well! we can easy compute the b(u) value, numerical value
and it seems to be ok.
1) lets try to proof, that only 2 types of pseoudoprimes break a symmetry in the modulo case and
a) Carmichael numbers. they have [1,1;1,u] - [1,1;1,n-u+2] "break" for some u and can not have a [u,p-1;p-1,1] case at all.
b) pseudoprimes in form n^2+1, that have more than one form a^2+b^2,
they have very interesting symmetry when factored as Gaussian prime
they always have [u,p-1;p-1,1] at u=0,2 and do not have [1,1;1,u] form at all
I.e. no one of "exception" have no posses the both
types of symmetry,

piece of the PG code

{forstep(p=23,100000000,2,
if(Mod(p,1000003)==0, "---";print(p));
if(ispseudoprime(p),

f1=0;f2=0;f3=0;
A=Mod([1,1;1,0],p)^p;B=[0,p-1;p-1,1]; C=[1,1;1,0];D=[A[1,1],0;0,A[1,1]];
if(A==B,f2++);if(A==C,f1++);if(A==D,f3++);
if(f1+f2+f3==0,next);
A=Mod([1,1;1,p+2],p)^p;B=[2,p-1;p-1,1]; C=[1,1;1,2];D=[A[1,1],0;0,A[1,1]];
if(A==B,f2++);if(A==C,f1++);if(A==D,f3++);
if(f1+f2+f3<2,next);
A=Mod([1,1;1,2],p)^p;B=[2,p-1;p-1,1]; C=[1,1;1,2];D=[A[1,1],0;0,A[1,1]];
if(A==B,f2++);if(A==C,f1++);if(A==D,f3++);
if(f1+f2+f3<3,next);
A=Mod([1,1;1,p],p)^p;B=[0,p-1;p-1,1]; C=[1,1;1,0];D=[A[1,1],0;0,A[1,1]];
if(A==B,f2++);if(A==C,f1++);if(A==D,f3++);
if(f1+f2+f3<4,next);

k1=f1/4;k2=f2/4;
if(f3>1,next);

f1=0;f2=0;f3=0;a=1;
while(a,
u=2+random((p-1)/2);
A=Mod([1,1;1,u],p)^p;B=[u,p-1;p-1,1]; C=[1,1;1,u];
if(A==B,f2++);if(A==C,f1++);
if(f1+f2+f3==0,break(1));

A=Mod([1,1;1,p-u+2],p)^p;B=[p-u+2,p-1;p-1,1]; C=[1,1;1,p-u+2];
if(A==B,f2++);if(A==C,f1++);
if(f1+f2+f3==0,break(1));

if((k1==0&&f1==2)||(k2==0&&f2==2),break);
\\a=a+1; \\for some prime numbers, a can grow to high values.
\\if(a>10,print(p));
f1=0;f2=0;
);
if(isprime(p),,print(p)); \\the p prime is here
)
)}

[Batalov]

You asked if there was a proof for "if p prime, <bla>". That proof exists.

Originally Posted by Dr Sardonicus

Here is one proof that b(u) == b(p-u+2) (mod p) if p is prime.

Ergo, it is a PRP test, that's fine. Yet another one to add to hundreds of others. And an unmeasuredly slow one, as far as it is presented,

Originally Posted by CRGreathouse

This sounds very much like a pseudoprime test, if I understand your English.

Concur.

Where is the proof, "if <bla>, then p is prime"?
What others helped you check was that the opposite is not easily shown by contradiction/"exception". But that only goes to show that the set of words at least starts to shape into a conjecture. Where is the proof (or at least a path to it)?

[CRGreathouse]

Originally Posted by Batalov

Ergo, it is a PRP test, that's fine. Yet another one to add to hundreds of others. And an unmeasuredly slow one, as far as it is presented

It takes me > 10 minutes to test the composites up to 3000. Perhaps someone else can do better.

th2(p)=my(u='u,b=(Mod([1,1;1,u],p)^p)[1,2]); b==subst(b,u,p-u+2)

[RMLabrador]

Someone even quietly, without notice, changed the name of the topic)))))
He's an asshole, proven by themselves.

[LaurV]

Prove him an asshole, by coming with a proof of the fact that your test is more than a PRP test. Otherwise you are just a crank or (worse) a troll.
As Serge asked, prove us the part "if <bla> then p is prime".

[Dr Sardonicus]

Originally Posted by RMLabrador

Someone even quietly, without notice, changed the name of the topic)))))
He's an asshole, proven by themselves.

Of course it's a pseudoprime test. It involves a 2x2 matrix A, which has characteristic polynomial x^2 - (u+1)*x + u-1. The "if p is prime" results are easily proven using this polynomial, without regard to whether the matrix A is symmetric.

FWIW the polynomials trace(Aⁿ) are the analogs of the Lucas polynomials, which are defined for the polynomial x^2 - u*x - 1. Here we have

L₀ = 2, L₁ = u+1, L_k+2 = (u+1)*L_k+1 - (u-1)*L_k, k = 0, 1, 2, etc

and the off-diagonal polynomials b(u) are the analogs of the Fibonacci polynomials:

F₀ = 0, F₁ = 1, F_k+2 = (u+1)*F_k+1 - (u-1)*F_k, k = 0, 1, 2, etc

These polynomials satisfy the identity

L_n² - Δ*F_n² = 4*(u-1)ⁿ where Δ = (u-1)^2 + 4 is the discriminant of the characteristic polynomial of A.

As to changing thread titles, it's a common occurrence on this forum. It's childish, but acting childishly does not make someone an a.