mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-05-07, 10:24   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

71608 Posts
Cool Divertimento

Based on the Frobenius tests over:

x^2-a*x+a==0 with kronecker(a^2-4*a,n)==-1
x^2-a*x-a==0 with kronecker(a^2+4*a,n)==-1

which can be transformed into

a^((n-1)/2)==kronecker(a,n) (mod n)
x^((n+1)/2)==kronecker(a,n) (mod n, x^2-(a-2)*x+1)
x^((n+1)/2)==kronecker(-a,n) (mod n, x^2+(a+2)*x+1)

I have tested up to n<10^6 with gcd(a^2-1,n)==1 without finding a counterexample pseudoprime.


Last fiddled with by paulunderwood on 2021-05-15 at 04:09
paulunderwood is offline   Reply With Quote
Old 2021-05-15, 04:04   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24·3·7·11 Posts
Default

  • kronecker(a^2-4*a,n)==-1
  • kronecker(a^2+4*a,n)==-1
  • a^((n-1)/2)==kronecker(a,n) (mod n)
  • x^((n+1)/2)==kronecker(a,n) (mod n, x^2-(a-2)*x+1)
  • x^((n+1)/2)==kronecker(-a,n) (mod n, x^2+(a+2)*x+1)
  • gcd(a^2-1,n)==1
Those n below 4*10^6 requiring gcd(a^2-1,n) are so few I can list them here:

Code:
[5777, 1854, 5777]                                                            
[17261, 420, 421]                                                             
[17261, 843, 421]
[17261, 3790, 421]
[17261, 5053, 421]
[113573, 48910, 113573]
[120581, 2942, 2941]
[120581, 5881, 2941]
[120581, 21453, 2941]
[120581, 26468, 2941]
[120581, 30276, 2941]
[120581, 35291, 2941]
[120581, 50863, 2941]
[120581, 59686, 2941]
[1033997, 317611, 1033997]
[1729331, 422433, 13201]
[1842581, 269647, 44941]
[1842581, 449411, 44941]
[1842581, 539291, 44941]
[1842581, 584232, 44941]
[3774377, 1256294, 3774377]
[3900797, 1544479, 3900797]

Last fiddled with by paulunderwood on 2021-05-15 at 04:15
paulunderwood is offline   Reply With Quote
Old 2021-05-21, 14:16   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24·3·7·11 Posts
Default

Let's turn the above into Pari/GP code:

Code:
{
tst(n,a)=
kronecker(a^2-4*a,n)==-1&&
kronecker(a^2+4*a,n)==-1&&
Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
Mod(Mod(x,n),x^2-(a-2)*x+1)^((n+1)/2)==kronecker(a,n)&&
Mod(Mod(x,n),x^2+(a+2)*x+1)^((n+1)/2)==kronecker(-a,n);
}
In the example above, I did not trivially test tst(n,1).

If I do test tst(n,1) and a gcd(a^2-1,n) is required I can loop over the rest of the a's (up to (n-1)/2 because of symmetry) and check for gcd(a^2-1,n).

What I see for such a is that GCD(gcd(ai^2-1,n),gcd(aj^2-1,n)) is always greater than 1 (so far). Furthermore, all gcd(a^2-1,n) have so far been 1 mod 4.

Last fiddled with by paulunderwood on 2021-05-21 at 15:45
paulunderwood is offline   Reply With Quote
Old 2021-05-23, 13:35   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24·3·7·11 Posts
Default fooled

tst(10627*148793, 479362525) fools!
paulunderwood is offline   Reply With Quote
Old 2021-05-25, 05:47   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24·3·7·11 Posts
Default New quest

With my observations about GCDs, I now have a new quest to fool:
Code:
tstab(n,a,b)=tst(n,a)&&tst(n,b)&&gcd(a^2-b^2,n)==1;
paulunderwood is offline   Reply With Quote
Old 2021-06-06, 10:53   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24·3·7·11 Posts
Default

I have not yet found a counterexample to the previous test.

I now propose a more general test:

{
tst(n,P,Q_i,Q_j)=
kronecker(P^2-4*Q_i)==-1&&
kronecker(P^2+4*Q_i)==-1&&
kronecker(P^2-4*Q_j)==-1&&
kronecker(P^2+4*Q_j)==-1&&
Mod(Mod(x,n),x^-P*x+Q_i)^(n+1)==Q_i&&
Mod(Mod(x,n),x^-P*x-Q_i)^(n+1)==-Q_i&&
Mod(Mod(x,n),x^-P*x+Q_j)^(n+1)==Q_j&&
Mod(Mod(x,n),x^-P*x-Q_j)^(n+1)==-Q_j&&
gcd(Q_i^2-Q_j^2,n)==1;
}

or

{tst1(n,P,Q)=kronecker(P^2-4*Q,n)==-1&&Mod(Mod(x,n),x^-P*x+Q)^(n+1)==Q;}

{tst2(n,P,Q)=tst1(n,P,Q)&&tst1(n,P,-Q);}

{tst4(n,P,Q_i,Q_j)=tst2(n,P,Q_i)&&tst2(n,P,Q_j)&&gcd(Q_i^2-Q_j^2,n)==1;}


Last fiddled with by paulunderwood on 2021-06-06 at 12:33
paulunderwood is offline   Reply With Quote
Old 2021-06-07, 07:35   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24·3·7·11 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I
{tst1(n,P,Q)=kronecker(P^2-4*Q,n)==-1&&Mod(Mod(x,n),x^-P*x+Q)^(n+1)==Q;}

{tst2(n,P,Q)=tst1(n,P,Q)&&tst1(n,P,-Q);}

{tst4(n,P,Q_i,Q_j)=tst2(n,P,Q_i)&&tst2(n,P,Q_j)&&gcd(Q_i^2-Q_j^2,n)==1;}
tst4(9809, 577, 27, 171) fails, but if I add the remedy gcd(P,n)==1 all is good.

Last fiddled with by paulunderwood on 2021-06-07 at 08:10
paulunderwood is offline   Reply With Quote
Old 2021-06-08, 00:13   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24×3×7×11 Posts
Default

What is wrong with this argument?

Let:
x^2-P*x+Q=0
y^2-P*y-Q=0
s^2-P*s+R=0
t^2-P*t-R=0

Then:
x^2+y^2-P*(x+y)=0
s^2+t^2-P*(s+t)=0

Or
P=(x^2+y^2)/(x+y)=(s^2+t^2)/(s+t)

That is since gcd(P,n)=1:
(x^2+y^2)*(s+t)=(s^2+t^2)*(x+y)

And the the following must be true since gcd(x^2+y^2, x+y) is either 1 or 2:
x+y=s+t

And so:
x^2+y^2=(x+y)^2-2*x*y=s^2+t^2=(s+t)^2-2*s*t

So that:x*y=s*t

If a prime p divides x it must divide s or t

Wlog then:
x^2-P*x+Q==x^2-P*x+R

I.e:
p divides Q-R, but a condition is that gcd(Q^2-R^2,n)=1.

QED
paulunderwood is offline   Reply With Quote
Old 2021-06-10, 20:57   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24·3·7·11 Posts
Default

Well that was a lot of BS maths.

Quote:
Originally Posted by paulunderwood View Post

Let:
x^2-P*x+Q=0
y^2-P*y-Q=0
s^2-P*s+R=0
t^2-P*t-R=0
I have tested (with strong kroneckers and gcd(P,n)==1 and gcd(Q^2-R^2,n)==1) for Q=1 up to n < 10^6 and for all Q for n up to 1.8*10^4 with Pari/GP. When I get some free time I will convert to my own C library

Last fiddled with by paulunderwood on 2021-06-11 at 01:05
paulunderwood is offline   Reply With Quote
Old 2021-06-11, 23:15   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24·3·7·11 Posts
Default

[n,P,Q,R]=[1162349, 2335, 1, 2234] fools tst4().

I have now revised the test; I insist that gcd(Q^2-1,n)==1 and gcd(R^2-1,n)==1 as well.

Code:
{tst1(n,P,Q)=kronecker(P^2-4*Q,n)==-1&&gcd(Q^2-1,n)==1&&
Mod(Mod(x,n),x^-P*x+Q)^(n+1)==Q;}

{tst2(n,P,Q)=tst1(n,P,Q)&&tst1(n,P,-Q);}

{tst4(n,P,Q,Rj)=tst2(n,P,Q)&&tst2(n,P,R)&&gcd(Q^2-R^2,n)==1;}
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 05:50.

Sat Jun 19 05:50:43 UTC 2021 up 22 days, 3:37, 0 users, load averages: 1.23, 1.31, 1.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.