mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-07-22, 02:08   #67
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

64078 Posts
Red face two parameter test

Let f=x^2-2^r*x+b=0 with solutions 2*x = 2^r +- sqrt(4^r-4*b). Test Frobenius(2x) w.r.t. f and Euler-PRP(4^r-4*b) = -1 (all mod n), with the provisos kronecker(4^r -4*b,n)==-1 and gcd(4^r-2*b,n)==1 and gcd(4^r-b,n)==1 and not b|n.

The Forbenius test can be broken into a 2-PRP test and a Frobenius test on x.

Here is the test. For any non-square n find r and b:
  • b%n!=0
  • gcd(4^r-b,n)==1
  • gcd(4^r-2*b,n)==1
  • kronecker(4^r-4*b,n)==-1
and test:
  • Mod(2,.n)^(n-1)==1
  • Mod(4^r-4*b,n)^((n-1)/2)==-1
  • Mod(Mod(1,n)*x,x^2-2^r*x+b)^(n+1)==b

Edit: I changed gcd(4^r-b^2,n) to gcd(4^r-b,n).

Edit2: I think gcd(4^r-b)==1 can be replaced by:
(gcd(b-1,n)==1&&gcd(4^r-1,n)==1)||(gcd(b+1,n)==1&&gcd(4^r+1,n)==1)

Last fiddled with by paulunderwood on 2020-07-23 at 22:44
paulunderwood is offline   Reply With Quote
Old 2020-07-27, 10:15   #68
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

333510 Posts
Default most general test

Let x^2-a*x+b=0. The solutions are x=a/2 +- sqrt(a^2-4*b)/2.

The test is:
  • b%n!=0
  • !issquare(n)
  • gcd(a^2-b,n)==1
  • gcd(a^2-2*b,n)==1
  • kronecker(a^2-4*b,n)==-1
  • Mod(a^2/4-b,n)^((n-1)/2)==-1
  • Mod(a/2,n)^(n-1)==1
  • Mod(Mod(1,n)*x,x^2-a*x+b)^(n+1)==b
paulunderwood is offline   Reply With Quote
Old 2020-07-27, 11:51   #69
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·23·29 Posts
Default

To fool 2-PSPs and Carmichael numbers lists gcd(a^2-3*b,n)==1 is also required.
paulunderwood is offline   Reply With Quote
Old 2020-07-27, 14:23   #70
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101000001112 Posts
Cool most general test (revised)

I found some counterexamples to the above.

The revised test:
  • b%n!=0
  • !issquare(n)
  • gcd(a^2-b,n)==1
  • gcd(a^2-2*b,n)==1
  • gcd(a^2-3*a,n)==1
  • kronecker(a^2-4*b,n)==-1
  • Mod(a^2/4-b,n)^((n-1)/2)==-1 //Euler PRP
  • Mod(a/2,n)^((n-1)/2)==konecker(lift(Mod(a/2,n)),n) //Euler PRP
  • Mod(Mod(1,n)*x,x^2-a*x+b)^(n+1)==b //Frobenius PRP

Further testing is ongoing.

A little bit of theory...

Let f = x^2-a*x+b=0 (which has roots x = a/2 +- sqrt(a^2-4*b)/2).

a = x+b/x mod f if kronecker(a^2-4*b,n)==-1.

a^2-2*b = x^2+b^2/x^2 mod f

(a^2-2*b)^2-2*b^2 = x^4+b^4/x^4 mod f

If gcd((a^2-2*b)^2-2*b^2,n)!=1 then d | R.H.S. and we can use Gaussian Elimination on the co-efficient of x and the term without x. This is complicated, but early calculations show that the GCDs given in the test above are sufficient and that there is no need to consider further recursions,

Here is a counterexample: [n,a,b]=[1894955311, 1756017110, 1]. Back to the drawing board; znlog(a,Mod(2,n)) == []

Last fiddled with by paulunderwood on 2020-07-27 at 14:54
paulunderwood is offline   Reply With Quote
Old 2020-07-28, 02:05   #71
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×23×29 Posts
Default A very short paper

Attached Files
File Type: pdf Two_Parameter_Probable_Prime_Test.pdf (40.5 KB, 37 views)

Last fiddled with by paulunderwood on 2020-07-28 at 03:05
paulunderwood is offline   Reply With Quote
Old 2020-07-28, 18:53   #72
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×23×29 Posts
Question Simplification

Recap: The solutions to x^2-2^r*x+b=0 are x=2^(r-1)+-sqrt(4^(r-1)-b).

Let r=1. Then the solutions are to the equation x^2-2*x+b=0 which are x=1+-sqrt(1-b)

We have to have kronecker(1-b,n)==-1, gcd(4-b,n)==1 and gcd(4-2*b,n)==1.

So no Fermat PRP test is needed; Just Frobenius+Euler.

I want to combine these into one test:

(x*(b-1))^((n+1)/2) == sqrt(b)*(b-1)*kronecker(X,n) (mod n, x^2-2*x+b)

where b is quadratic residue. But what is X?

Last fiddled with by paulunderwood on 2020-07-28 at 19:09
paulunderwood is offline   Reply With Quote
Old 2020-07-30, 01:10   #73
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·23·29 Posts
Red face Answer and warning

Apart form the ill-formed question, writing b=s^2 (and found by trial and error) the answer is:

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

Warning: this "fused" Euler and Frobenius test produces pseudoprimes. Testing to date has not found a counterexample when they are applied separately:

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

where kronecker(1-b,n)==-1 and gcd(4-2*b,n)==1 and gcd(4-b,n)==1.

Last fiddled with by paulunderwood on 2020-07-30 at 01:27
paulunderwood is offline   Reply With Quote
Old 2020-08-02, 09:15   #74
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×23×29 Posts
Cool Second draft

Attached Files
File Type: pdf Two_Parameter_Probable_Prime_Test.pdf (39.7 KB, 15 views)
paulunderwood is offline   Reply With Quote
Old 2020-08-03, 14:20   #75
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D0716 Posts
w00t 1+1 selfridges

Here is a 1+1 selfridges algorithm:

Given a non-square n find b:
  • kronecker(b,n)==1
  • kronecker(1-b,n)==-1
  • gcd(4-b,n)==1
  • gcd(4-2*b,n)==1
and test
  • Mod(b,n)^((n-1)/2)==1
  • Mod(1-b,n)^((n-1)/2)==-1

I will try to explain my reasoning later.

Later reason: programming error The argument does not stack up. It was entirely based on the Euler test of post #74 and without the Frobenius part.

Last fiddled with by paulunderwood on 2020-08-03 at 15:49
paulunderwood is offline   Reply With Quote
Old 2020-08-03, 19:36   #76
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×23×29 Posts
Thumbs down House of cards

[n,b] = [79786523, 2982537] is a counterexample to the test given in post #74 where r=1. This was overlooked because of the same programming error indicated in post #75. The only thing to be lifted from the ashes is that b is not minimal.

The cases where |b| =1 (post #71) have no counterexamples for n<5*10^12.

Last fiddled with by paulunderwood on 2020-08-03 at 19:38
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Don't miss this amazing trick that the moon is going to do! Uncwilly Astronomy 6 2018-02-01 05:40
Amazing result in P-1 Miszka Information & Answers 2 2014-07-04 17:11
Amazing academic resource Xyzzy Lounge 6 2012-03-25 22:57
Amazing!!! R.D. Silverman Factoring 5 2006-01-26 09:14
Two Amazing Things clowns789 Hardware 1 2003-12-27 16:57

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

Mon Aug 10 05:43:41 UTC 2020 up 24 days, 1:30, 2 users, load averages: 1.42, 1.34, 1.33

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.