20200916, 03:25  #23 
Aug 2006
1011100110010_{2} Posts 
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?

20200916, 07:09  #24 
"Roman V. Makarchuk"
Aug 2020
Ukraine
2×17 Posts 
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 Last fiddled with by RMLabrador on 20200916 at 07:09 Reason: u 
20200916, 12:57  #25 
"Roman V. Makarchuk"
Aug 2020
Ukraine
2·17 Posts 
Until now!
Do You Listen to the wind of changes?)) As i can see, this is uindependent 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 final1 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. Last fiddled with by RMLabrador on 20200916 at 13:04 
20200916, 13:42  #26 
Sep 2002
Database er0rr
2·17·103 Posts 
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: Code:
{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==1Ti==n1), print([n,u,lift(lift(A))]);break(2)))))} [861, 783, [493*i + 616, 492*i + 1; 492*i + 1, 369*i + 168]] Last fiddled with by paulunderwood on 20200916 at 13:44 
20200916, 13:56  #27  
Feb 2017
Nowhere
37·103 Posts 
Quote:
Code:
? 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 Quote:


20200916, 14:04  #28 
"Roman V. Makarchuk"
Aug 2020
Ukraine
2·17 Posts 
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 pu+2 when p is prime Here http:\\romanvmprime.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 Last fiddled with by RMLabrador on 20200916 at 14:06 
20200916, 19:18  #29 
Aug 2006
13462_{8} Posts 

20200917, 03:33  #30 
"Sam"
Nov 2016
2·3·53 Posts 
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): Code:
lift(trace(Mod([a,b; c,d],n)^n)) == (a^n + d^n) \((a + d)^{n} \equiv a^{n} + d^{n} \pmod n\) Then \((a + d)^{n} = \sum_{i = 0}^{n} \binom{n}{i} a^{ni}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 Code:
lift(trace([a,b; c,d])^n) The sequences for polynomial functions of integers in the kth 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}^{k1}{ni}}{k!}\] Here are a few such generalizations I had in mind involving a 4 x 4 matrix: Code:
(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_{0} = 1 c_{1} = 0 c_{2} = 3*n c_{3} = 8*n+24 c_{4} = (9*n^2+17*n)/2 c_{5} = 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}^{k1}{nP(i)}}{P_{k}}\] where \[P_{k} = \prod_{i=0}^{k1}{P(i)}\] Last fiddled with by carpetpool on 20200917 at 03:40 Reason: I'm still not used to TeX format here, so I apologize if things don't look as neat. 
20200917, 06:24  #31 
"Roman V. Makarchuk"
Aug 2020
Ukraine
2·17 Posts 
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(pu+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 Googlecrutch, and even for myself, hard to understand some point after Googletranslate) We need the test! 
20200917, 07:04  #32 
"Roman V. Makarchuk"
Aug 2020
Ukraine
22_{16} Posts 
Ще один спосіб  вивести формулу для коеффіцієнтів поліному 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). 
20200917, 12:47  #33 
Feb 2017
Nowhere
37·103 Posts 
Regarding the use of polynomial coefficients to prove primality, there is already a wellknown deterministic test, the AKS primality test. See the following 2004 paper for more details.
Last fiddled with by Dr Sardonicus on 20200917 at 12:48 Reason: Omit unnecessary words! 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
I found the primality test, there seems to be no composite numbers that pass the test  sweety439  sweety439  7  20200211 19:49 
+/ 6 Primality Test  a1call  Miscellaneous Math  29  20181224 01:42 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
there is another way to test the primality of a no  shawn  Miscellaneous Math  5  20070717 17:55 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 