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

2×3×54 Posts
Cool Divertimento -- Four Lucas Tests

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 online now   Reply With Quote
Old 2021-05-15, 04:04   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×3×54 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 online now   Reply With Quote
Old 2021-05-21, 14:16   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·54 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 online now   Reply With Quote
Old 2021-05-23, 13:35   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×3×54 Posts
Default fooled

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

2·3·54 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 online now   Reply With Quote
Old 2021-06-06, 10:53   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·54 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 online now   Reply With Quote
Old 2021-06-07, 07:35   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

EA616 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 online now   Reply With Quote
Old 2021-06-08, 00:13   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·54 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 online now   Reply With Quote
Old 2021-06-10, 20:57   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×3×54 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 online now   Reply With Quote
Old 2021-06-11, 23:15   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·54 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 online now   Reply With Quote
Old 2021-06-19, 08:02   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×3×54 Posts
Default Restricted domain variation

Here I test over

x^2-x+2^r where kronecker(1-4*2^r,n)==-1
x^2-x-2^r where kronecker(1+4*2^r,n)==-1

If r is even this is the same as:

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

if r is odd:

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

If r==0 we have:

x^((n+1)/2)==kronecker(-1,n) (mod n, x^2+3*x+1) where kronecker(5,n)==-1 and kronecker(-3,n)==-1.

and this has pseudoprimes: [5777, ... ] and consequently checking gcd(2^(2*r)-1,n)==1 is wise.

To make the Lucas PRP tests more efficient we can instead calculate over x^2-x+-1/2^r and use small r.

Last fiddled with by paulunderwood on 2021-06-19 at 23:33 Reason: Fixed the Lucas PRP tests expressions and exponents thereof. Plus, added pseudoprimes
paulunderwood is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucas and Fibonacci primes Batalov And now for something completely different 9 2017-06-28 16:56
Lucas Table R.D. Silverman Factoring 19 2012-09-07 17:24
Need help with Lucas Sequences... WraithX Programming 11 2010-09-23 23:22
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas-Lehmer Dougal Information & Answers 9 2009-02-06 10:25

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


Fri Jul 23 17:59:19 UTC 2021 up 12:28, 1 user, load averages: 3.20, 3.14, 3.33

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.