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

 2020-09-17, 13:24 #34 RMLabrador     "Roman V. Makarchuk" Aug 2020 Ukraine 2×17 Posts 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]
 2020-09-17, 15:42 #35 CRGreathouse     Aug 2006 2×2,969 Posts Has anyone coded this in PARI/GP so we can test various ranges?
2020-09-17, 15:57   #36
carpetpool

"Sam"
Nov 2016

26×5 Posts

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

 2020-09-19, 08:04 #37 RMLabrador     "Roman V. Makarchuk" Aug 2020 Ukraine 1000102 Posts (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, Last fiddled with by RMLabrador on 2020-09-19 at 08:49
 2020-09-19, 12:19 #38 Dr Sardonicus     Feb 2017 Nowhere 132·23 Posts 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 Ap (mod p), which by formula are 1,-1, or 0 (mod p) for u in Z/pZx, remain invariant also. Therefore, if b(u) is the off-diagonal polynomial in Ap, 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 Fp[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. Last fiddled with by Dr Sardonicus on 2020-09-23 at 11:10
 2020-09-22, 09:29 #39 RMLabrador     "Roman V. Makarchuk" Aug 2020 Ukraine 2×17 Posts 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 ) )}
2020-09-22, 16:26   #40
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts
not a "Universal primality test" so far, by a mile

You asked if there was a proof for "if p prime, <bla>". That proof exists.
Quote:
 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,
Quote:
 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)?

2020-09-22, 18:09   #41
CRGreathouse

Aug 2006

2×2,969 Posts

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

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

 2020-09-23, 08:34 #42 RMLabrador     "Roman V. Makarchuk" Aug 2020 Ukraine 1000102 Posts Someone even quietly, without notice, changed the name of the topic))))) He's an asshole, proven by themselves.
 2020-09-23, 08:59 #43 LaurV Romulan Interpreter     Jun 2011 Thailand 230216 Posts 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 then p is prime". Last fiddled with by LaurV on 2020-09-23 at 09:00
2020-09-23, 12:04   #44
Dr Sardonicus

Feb 2017
Nowhere

F2F16 Posts

Quote:
 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(An) are the analogs of the Lucas polynomials, which are defined for the polynomial x^2 - u*x - 1. Here we have

L0 = 2, L1 = u+1, Lk+2 = (u+1)*Lk+1 - (u-1)*Lk, k = 0, 1, 2, etc

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

F0 = 0, F1 = 1, Fk+2 = (u+1)*Fk+1 - (u-1)*Fk, k = 0, 1, 2, etc

These polynomials satisfy the identity

Ln2 - Δ*Fn2 = 4*(u-1)n 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.

 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 17:29.

Thu Dec 3 17:29:49 UTC 2020 up 13:41, 1 user, load averages: 1.58, 1.67, 1.66