mersenneforum.org A Universally derided "primality test".
 Register FAQ Search Today's Posts Mark Forums Read

 2020-09-16, 03:25 #23 CRGreathouse     Aug 2006 22×1,483 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?
 2020-09-16, 07:09 #24 RMLabrador     "Roman V. Makarchuk" Aug 2020 Ukraine 1000102 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 2020-09-16 at 07:09 Reason: u
 2020-09-16, 12:57 #25 RMLabrador     "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 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. Last fiddled with by RMLabrador on 2020-09-16 at 13:04
 2020-09-16, 13:42 #26 paulunderwood     Sep 2002 Database er0rr 344610 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==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]] Last fiddled with by paulunderwood on 2020-09-16 at 13:44
2020-09-16, 13:56   #27
Dr Sardonicus

Feb 2017
Nowhere

DF916 Posts

Quote:
 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 Ap 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.

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:
 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?

 2020-09-16, 14:04 #28 RMLabrador     "Roman V. Makarchuk" Aug 2020 Ukraine 428 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 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 Last fiddled with by RMLabrador on 2020-09-16 at 14:06
2020-09-16, 19:18   #29
CRGreathouse

Aug 2006

22×1,483 Posts

Quote:
 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.

 2020-09-17, 03:33 #30 carpetpool     "Sam" Nov 2016 22×79 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) 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 Code: 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: 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 c0 = 1 c1 = 0 c2 = 3*n c3 = 8*n+24 c4 = (9*n^2+17*n)/2 c5 = 24*n^2 - 36*n ... However, degree(cn) ≠ 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(cn) = 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)}$ Last fiddled with by carpetpool on 2020-09-17 at 03:40 Reason: I'm still not used to TeX format here, so I apologize if things don't look as neat.
 2020-09-17, 06:24 #31 RMLabrador     "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(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!
 2020-09-17, 07:04 #32 RMLabrador     "Roman V. Makarchuk" Aug 2020 Ukraine 2·17 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).
 2020-09-17, 12:47 #33 Dr Sardonicus     Feb 2017 Nowhere 72×73 Posts 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. Last fiddled with by Dr Sardonicus on 2020-09-17 at 12:48 Reason: Omit unnecessary words!

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 7 2020-02-11 19:49 a1call Miscellaneous Math 29 2018-12-24 01:42 Trilo Miscellaneous Math 25 2018-03-11 23:20 shawn Miscellaneous Math 5 2007-07-17 17:55 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 02:24.

Wed Oct 28 02:24:52 UTC 2020 up 47 days, 23:35, 2 users, load averages: 2.44, 1.88, 1.83