mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-09-17, 13:24   #34
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2×17 Posts
Default

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]
RMLabrador is offline   Reply With Quote
Old 2020-09-17, 15:42   #35
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

173216 Posts
Default

Has anyone coded this in PARI/GP so we can test various ranges?
CRGreathouse is offline   Reply With Quote
Old 2020-09-17, 15:57   #36
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×53 Posts
Post

Quote:
Originally Posted by RMLabrador View Post
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?
carpetpool is offline   Reply With Quote
Old 2020-09-19, 08:04   #37
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2·17 Posts
Default

(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
RMLabrador is offline   Reply With Quote
Old 2020-09-19, 12:19   #38
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

19×199 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2020-09-22, 09:29   #39
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2·17 Posts
Default

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
)
)}
RMLabrador is offline   Reply With Quote
Old 2020-09-22, 16:26   #40
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×3×7×109 Posts
Default 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 View Post
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 View Post
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)?
Batalov is offline   Reply With Quote
Old 2020-09-22, 18:09   #41
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

Quote:
Originally Posted by Batalov View Post
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)
CRGreathouse is offline   Reply With Quote
Old 2020-09-23, 08:34   #42
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2·17 Posts
Default

Someone even quietly, without notice, changed the name of the topic)))))
He's an asshole, proven by themselves.
RMLabrador is offline   Reply With Quote
Old 2020-09-23, 08:59   #43
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3·13·229 Posts
Default

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".

Last fiddled with by LaurV on 2020-09-23 at 09:00
LaurV is offline   Reply With Quote
Old 2020-09-23, 12:04   #44
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

73058 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
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.
Dr Sardonicus is offline   Reply With Quote
Reply

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 2020-02-11 19:49
+/- 6 Primality Test a1call Miscellaneous Math 29 2018-12-24 01:42
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
there is another way to test the primality of a no shawn Miscellaneous Math 5 2007-07-17 17:55
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 16:17.

Tue Nov 24 16:17:25 UTC 2020 up 75 days, 13:28, 4 users, load averages: 1.89, 1.89, 1.79

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.