A Universally derided "primality test".

[CRGreathouse]

I'm not sure what there is to understand. You posted a test which looked like a probable prime test. On examination, it seems like primes pass it, most composites fail, and some composites pass. This is exactly what we'd expect of a probable prime test. Are we missing something?

[RMLabrador]

Yes it is. There is my fault. If we look what exactly the last test doing - do the analytical result of powering matrix and computing spur, the result is polynomial of u with integer, positive and negative coefficients, that depend only on testing value of p.
In case p is prime, everyone of this coefficient is divided by p - > have p as factor, i.e.
the result is in form G(u)=p*g(u) (1)
so G(u)==0 (mod p) (2)
Ok? This is true ONLY for prime numbers, and certainly is is profitable!!! I have the marvelous proof) and i'm sure most of mathematicians can write the proof.
In (1) notation, test will be 100% accurate. No pseudoprimes pass the test in this form, do You understand this?

But here, we in the not good situation. We use notation (2).
Let me explain a bit further. When p is not prime, we can be in the situation, when for some not prime p, G(u) do not have p as factor, but instead the value G(u) for some u is divided by p so G(u) ==0 (mod p) and we stuck with our beloved f@cked pseodoprimes forever))) Time to time, test to test, nothing changes

[RMLabrador]

Until now!
Do You Listen to the wind of changes?))

As i can see, this is u-independent test, u do not needed at least in theory, and can be =0.
At this place, i can easy do the wrong statement,
mainly because i see other way to final step.

In spite of that, this lookalike to be final or final-1 iteration))))



P/S/ u is needed for be honest(and correct). I'm talk about oscillation for small u, when we compute modulo AFTER power.

[paulunderwood]

Once again it is meaningless to talk about "u>log(p)^2" when working with modular arithmetic. Also it makes absolutely no difference where you apply modulo operations. It is a "multiplicative operation" -- powering is repeated multiplication.

Composite example:

{forstep(n=7,1000000000,2,if(!ispseudoprime(n),
for(u=0,n,A=Mod(Mod([i+1,1;1,u],n),i^2+1)^(n);
Tr=lift(lift(trace(A)))%i;Ti=lift(lift(trace(A*i)))%i;F=Mod(u,n)^n+1;
if(Tr==F&&(Ti==1||Ti==n-1),
print([n,u,lift(lift(A))]);break(2)))))}
[861, 783, [493*i + 616, 492*i + 1; 492*i + 1, 369*i + 168]]

[Dr Sardonicus]

Originally Posted by RMLabrador

Yes it is. There is my fault. If we look what exactly the last test doing - do the analytical result of powering matrix and computing spur, the result is polynomial of u with integer, positive and negative coefficients, that depend only on testing value of p.
In case p is prime, everyone of this coefficient is divided by p - > have p as factor, i.e.
the result is in form G(u)=p*g(u) (1)
so G(u)==0 (mod p) (2)
Ok?

No. This isn't what your paper says (it does give a result about the off-diagonal entry of A^p however). The trace polynomials are monic, with constant terms given by Lucas numbers. For prime index, the other coefficients appear to be divisible by p for p prime. I'm too lazy to check.

? A=[1,1;1,u];P=[1,0;0,1];for(i=1,13,P*=A;if(isprime(i),print(i" "trace(P))))
2 u^2 + 3
3 u^3 + 3*u + 4
5 u^5 + 5*u^3 + 5*u^2 + 10*u + 11
7 u^7 + 7*u^5 + 7*u^4 + 21*u^3 + 28*u^2 + 35*u + 29
11 u^11 + 11*u^9 + 11*u^8 + 55*u^7 + 88*u^6 + 187*u^5 + 286*u^4 + 396*u^3 + 440*u^2 + 374*u + 199
13 u^13 + 13*u^11 + 13*u^10 + 78*u^9 + 130*u^8 + 325*u^7 + 559*u^6 + 936*u^5 + 1313*u^4 + 1586*u^3 + 1560*u^2 + 1157*u + 521

This is true ONLY for prime numbers, and certainly is is profitable!!!

Just out of curiosity, how does the amount of computation required to produce these polynomials compare to the amount required to test p by Wilson's Theorem?

[RMLabrador]

No need to compute them all. Answer in the symmetry of this polynoms/
Just try compare their value modulo p for u and then for p-u+2 when p is prime
Here http:\\romanvm-prime.com this is theorem 2
in this form, there only Charmicael numbers look like the one, that pass the test. and even for them this is coincedence
they do not have a factor

[CRGreathouse]

Originally Posted by RMLabrador

in this form, there only Charmicael numbers look like the one, that pass the test. and even for them this is coincedence
they do not have a factor

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

[carpetpool]

I agree with CRGreathouse. Seems like a pseudoprime (PRP) test. The test can be generalized to higher level matrices. With 2 x 2 matrix test:

For any integer n, if we have (gp):

lift(trace(Mod([a,b; c,d],n)^n)) == (a^n + d^n)

then n is prime. The binomial theorem provides a proof of this

\((a + d)^{n} \equiv a^{n} + d^{n} \pmod n\)

Then

\((a + d)^{n} = \sum_{i = 0}^{n} \binom{n}{i} a^{n-i}d^{i}\)

The expansion of this shows all coefficients except the last two are divisible by n, so the congruence will hold. They form Pascal's triangle:

\(1\)
\(1, 1\)
\(1, 2, 1\)
\(1, 3, 3, 1\)
\(1, 4, 6, 4, 1\)
\(1, 5, 10, 10, 5 1\)
\(1, 6, 15, 20, 15, 6, 1\)
\(1, 7, 21, 35, 35, 21, 7, 1\)
\(...\)

These coefficients appear in the expansion of

lift(trace([a,b; c,d])^n)

So it is clear that the only terms on the n-th row not divisible by n are the first and last terms.

The sequences for polynomial functions of integers in the k-th column are given by:

\(c_0 = 1\)
\(c_1 = n\)
\(c_2 = \frac{n^{2} - n}{2}\)
\(c_3 = \frac{n^{3} - 3n^{2} + 2n}{6}\)
\(c_4 = \frac{n^{4} - 6n^{3} + 11n^{2} - 6n}{24}\)
\(c_5 = \frac{n^{5} - 10n^{4} + 35n^{3} - 50n^{2} + 24n}{120}\)
...
\[c_n = \frac{\prod_{i=0}^{k-1}{n-i}}{k!}\]

Here are a few such generalizations I had in mind involving a 4 x 4 matrix:

(20:11) gp > for(n=j,16, print(lift(trace(([0,1,1,1; 1,1,1,1; 1,1,1,1; 1,1,1,x])^n))))
x + 2
x^2 + 14
x^3 + 9*x + 44
x^4 + 12*x^2 + 32*x + 162
x^5 + 15*x^3 + 40*x^2 + 155*x + 572
x^6 + 18*x^4 + 48*x^3 + 213*x^2 + 648*x + 2042
x^7 + 21*x^5 + 56*x^4 + 280*x^3 + 924*x^2 + 2709*x + 7268
x^8 + 24*x^6 + 64*x^5 + 356*x^4 + 1248*x^3 + 4096*x^2 + 11008*x + 25890
x^9 + 27*x^7 + 72*x^6 + 441*x^5 + 1620*x^4 + 5814*x^3 + 17532*x^2 + 44127*x + 92204
x^10 + 30*x^8 + 80*x^7 + 535*x^6 + 2040*x^5 + 7890*x^4 + 25920*x^3 + 74085*x^2 + 174600*x + 328394
x^11 + 33*x^9 + 88*x^8 + 638*x^7 + 2508*x^6 + 10351*x^5 + 36388*x^4 + 114235*x^3 + 308352*x^2 + 684057*x + 1169588
x^12 + 36*x^10 + 96*x^9 + 750*x^8 + 3024*x^7 + 13224*x^6 + 49152*x^5 + 166233*x^4 + 494816*x^3 + 1268796*x^2 + 2657760*x + 4165554
x^13 + 39*x^11 + 104*x^10 + 871*x^9 + 3588*x^8 + 16536*x^7 + 64428*x^6 + 231816*x^5 + 744692*x^4 + 2116569*x^3 + 5167968*x^2 + 10254595*x + 14835836
x^14 + 42*x^12 + 112*x^11 + 1001*x^10 + 4200*x^9 + 20314*x^8 + 82432*x^7 + 312802*x^6 + 1069544*x^5 + 3291792*x^4 + 8949360*x^3 + 20867581*x^2 + 39331656*x + 52838618
x^15 + 45*x^13 + 120*x^12 + 1140*x^11 + 4860*x^10 + 24585*x^9 + 103380*x^8 + 411090*x^7 + 1481800*x^6 + 4866414*x^5 + 14366100*x^4 + 37465250*x^3 + 83619540*x^2 + 150087645*x + 188187524
x^16 + 48*x^14 + 128*x^13 + 1288*x^12 + 5568*x^11 + 29376*x^10 + 127488*x^9 + 528660*x^8 + 1994752*x^7 + 6920160*x^6 + 21837312*x^5 + 62013936*x^4 + 155458880*x^3 + 332828064*x^2 + 570181376*x + 670239810

....

The coefficients are

c₀ = 1
c₁ = 0
c₂ = 3*n
c₃ = 8*n+24
c₄ = (9*n^2+17*n)/2
c₅ = 24*n^2 - 36*n
...

However, degree(c_n) ≠ n. This appears to be significantly weaker than the original 2 x 2 matrix test (Fermat's Little Theorem). I suppose there could be a way to construct a series of coefficients with degree(c_n) = n which Carmichael Numbers could potentially fail. If I had more time, I would probably search for a better example, but at least you get the point now.


My second idea involves using coefficents of the form

\[c_n = \frac{\prod_{i=0}^{k-1}{n-P(i)}}{P_{k}}\]

where

\[P_{k} = \prod_{i=0}^{k-1}{P(i)}\]

[RMLabrador]

The symmetry is the key to build test.I'm the only one here who sees symmetry???
check this.
in this form, no counterexamples, no one pseudoprime will pass this test. Problem in computation of this numerical.
You can do this analytically and see the difference with numerical computation - Carmichael numbers pass the test if we use modulo form
i/e/ b(u)-b(p-u+2) == 0 (mod p) but in reality, they do not have the p as factor.

And next step is to show or proof that is we have "exception" for some u in form [u,-1;-1,1]
(see the very beginning of this tread)
this "exception" do not break the symmetry if we (unavoidable) using modulo computation.
i'm relay on the Google-crutch, and even for myself, hard to understand some point after Google-translate)
We need the test!

[RMLabrador]

Ще один спосіб - вивести формулу для коеффіцієнтів поліному b(u). Звичайно, перевіряти подільність кожного з них на число p буде досить маразматично, однак цілком можливо, що така формула дасть можливість винести p за дужки, без виконання занадто громіздких за об'ємом обчислень, тобто аналітично. А можливо і навпаки - отримаємо аналог теореми Вільсона, тільки з купою факторіалів та біноміальних коєффіцієнтів.
Імовірно, для суми коеффіцієнтів така формула буде точно існувати, однак тест у такій формі все ж буде імовірнісним (PRP).

Another way is to derive a formula for the coefficients of the polynomial b (u). Of course, to check the divisibility of each of them by the number p will be quite marasmic, but it is possible that such a formula will make it possible to make p in parentheses, without performing too cumbersome calculations, ie analytically. And perhaps vice versa - we get an analogue of Wilson's theorem, only with a bunch of factorials and binomial coefficients.
It is likely that such a formula will exist for the sum of the coefficients, but the test in this form will still be probabilistic (PRP).

[Dr Sardonicus]

Regarding the use of polynomial coefficients to prove primality, there is already a well-known deterministic test, the AKS primality test. See the following 2004 paper for more details.