mersenneforum.org Amazing 6
 Register FAQ Search Today's Posts Mark Forums Read

 2020-09-17, 15:28 #89 carpetpool     "Sam" Nov 2016 5×67 Posts I think the 1-2^r test is better (a generalization to any arbitrary base b should hold). If there are two integers r, s, which pass this test, in particular we have (WLOG): 1 - b^r kronecker(1-b^r,n)==-1 Mod(1-b^r,n)^((n-1)/2)==-1 Mod(Mod(1,n)*x,x^2-2*x+b^r)^(n+1)==b^r gcd(b^(r-s) - 1, n) = 1 n is a probable prime. If this test were accurate, we could obtain some fixed pairs of integers 1-b^r and 1-b^s to be used in the test as long as the Jacobi symbol requirements are met.
 2020-09-17, 16:41 #90 paulunderwood     Sep 2002 Database er0rr 22×1,063 Posts Your idea seems right. I ran some of this: Code: { forstep(n=30169231,30169231,2, if(!ispseudoprime(n)&&!issquare(n), for(b=1,n,if(gcd(b,n)==1,z=znorder(Mod(b,n)); for(r=1,z,A=Mod(b,n)^r; if(kronecker(1-lift(A),n)==-1&&(1-A)^((n-1)/2)==-1&& Mod(x,x^2-2*x+A)^(n+1)==A, for(s=r+1,z,B=Mod(b,n)^s; if(kronecker(1-lift(B),n)==-1&&(1-B)^((n-1)/2)==-1&& Mod(x,x^2-2*x+B)^(n+1)==B, print([n,b,r,s,gcd(Mod(b,n)^(s-r)-1,n)])))))))))} (I am sorry for not writing functional code.) Can you provide any example n not in the list: Code: [2047, 2, 2047, 1] [42799, 2, 42799, 1] [90751, 2, 90751, 1] [256999, 2, 256999, 1] [271951, 2, 271951, 1] [476971, 2, 476971, 1] [514447, 2, 514447, 1] [741751, 2, 741751, 1] [877099, 2, 877099, 1] [916327, 2, 916327, 1] [1302451, 2, 1302451, 1] [1325843, 2, 1325843, 1] [1397419, 2, 1397419, 1] [1441091, 2, 1441091, 1] [1507963, 2, 1507963, 1] [1530787, 2, 1530787, 1] [1907851, 2, 1907851, 1] [2004403, 2, 2004403, 1] [2205967, 2, 2205967, 1] [2304167, 2, 2304167, 1] [2748023, 2, 2748023, 1] [2811271, 2, 2811271, 1] [2953711, 2, 2953711, 1] [2976487, 2, 2976487, 1] [3090091, 2, 3090091, 1] [3116107, 2, 3116107, 1] [4469471, 2, 4469471, 1] [4863127, 2, 4863127, 1] [5016191, 2, 5016191, 1] [5173601, 4, 1, 5173601] [5256091, 2, 5256091, 1] [5919187, 2, 5919187, 1] [6334351, 2, 6334351, 1] [6787327, 2, 6787327, 1] [7674967, 2, 7674967, 1] [7883731, 2, 7883731, 1] [8095447, 2, 8095447, 1] [8388607, 2, 8388607, 1] [8510347, 3465127, 27721, 1] [8727391, 2, 8727391, 1] [9371251, 2, 9371251, 1] [9588151, 2, 9588151, 1] [9995671, 2, 9995671, 1] [10425511, 2, 10425511, 1] [10610063, 2, 10610063, 1] [11081459, 2, 11081459, 1] [11541307, 2, 11541307, 1] [11777599, 2, 11777599, 1] [12263131, 2, 12263131, 1] [13057787, 2, 13057787, 1] [13338371, 2, 13338371, 1] [15139199, 2, 15139199, 1] [15220951, 2, 15220951, 1] [15603391, 2, 15603391, 1] [15698431, 2, 15698431, 1] [15698431, 8389600, 511, 1] [15976747, 2, 15976747, 1] [15978007, 2, 15978007, 1] [16070429, 4, 1, 16070429] [17134043, 2, 17134043, 1] [18740971, 2, 18740971, 1] [19404139, 2, 19404139, 1] [20261251, 2, 20261251, 1] [20417311, 2, 20417311, 1] [21303343, 2, 21303343, 1] [21417991, 2, 21417991, 1] [21623659, 2, 21623659, 1] [22075579, 2, 22075579, 1] [24214051, 2, 24214051, 1] [27271151, 2, 27271151, 1] [27380831, 2, 27380831, 1] [27808463, 2, 27808463, 1] [30169231, 26747980, 311023, 1] [30576151, 2, 30576151, 1] [30881551, 2, 30881551, 1] [30894307, 2, 30894307, 1] [31166803, 2, 31166803, 1] [31436123, 2, 31436123, 1] [34856167, 2, 34856167, 1] [35576599, 2, 35576599, 1] [37109467, 2, 37109467, 1] [37769887, 2, 37769887, 1] [37769887, 35557427, 158033, 1] [37769887, 21808556, 158033, 1] [38010307, 2, 38010307, 1] [38118763, 2, 38118763, 1] [38210323, 2, 38210323, 1] [38342071, 2, 38342071, 1] [39465091, 2, 39465091, 1] [42485119, 2, 42485119, 1] [43397551, 2, 43397551, 1] [46256489, 4, 1, 46256489] [47220367, 2, 47220367, 1] [48369727, 2, 48369727, 1] [51340807, 2, 51340807, 1] [53675623, 2, 53675623, 1] [54029741, 4, 1, 54029741] [54449431, 2, 54449431, 1] [58449847, 2, 58449847, 1] [59631211, 2, 59631211, 1] [60547831, 2, 60547831, 1] [60566431, 2, 60566431, 1] [61755751, 2, 61755751, 1] [63167743, 2, 63167743, 1] [63346999, 2, 63346999, 1]
 2020-09-19, 08:35 #91 carpetpool     "Sam" Nov 2016 5·67 Posts I retract my original claim (but perhaps something better could be turned out of it). Here are some counterexamples I just found using specific parameters b = 2, r = 1, s = 2. Trivially, gcd(2^(1-1)-1,n)=1. Code: (00:41) gp > for(n=1,10^10, if(n%12==11 & isprime(n)==0 & Mod(3,n)^((n-1)/2)==1 & Mod(Mod(1,n)*x,x^2+2*x+2)^(n+1)==2 & Mod(Mod(1,n)*x,x^2+2*x+4)^(n+1)==4, print(n))) 3028586471 3056100623 *** at top-level: for(n=1,10^10,if(n%12==11&isprime(n)==0&Mod *** ^------------------------ *** user interrupt after 27min, 24,798 ms (01:08) gp > (01:12) gp > znorder(Mod(2,3028586471)) %29 = 7943 (01:12) gp > znorder(Mod(2,3056100623)) %30 = 7979 (01:12) gp > (01:13) gp > znorder(Mod(3,3028586471)) %44 = 7943 (01:13) gp > znorder(Mod(3,3056100623)) %45 = 7979 (01:13) gp > (01:18) gp > n = 3028586471 %40 = 3028586471 (01:18) gp > for(a=1,znorder(Mod(2,n)), if(isprime(n)==0 & Mod(1-2^a,n)^((n-1)/2)==(n-1) & Mod(Mod(1,n)*x,x^2+2*x+2^a)^(n+1)==2^a, print(a))) 1 2 (01:18) gp > n = 3056100623 %42 = 3056100623 (01:18) gp > for(a=1,znorder(Mod(2,n)), if(isprime(n)==0 & Mod(1-2^a,n)^((n-1)/2)==(n-1) & Mod(Mod(1,n)*x,x^2+2*x+2^a)^(n+1)==2^a, print(a))) 1 2 (01:18) gp > Both counterexamples have "period" length 2, while all other known counterexamples only have length 1. (example, n = 2047 for length 1). Code: (01:32) gp > for(a=1,znorder(Mod(2,n)), if(isprime(n)==0 & Mod(1-2^a,n)^((n-1)/2)==(n-1) & Mod(Mod(1,n)*x,x^2+2*x+2^a)^(n+1)==2^a, print(a))) 1 So all a ∈ Z/nZ with a = 2^k form a cyclic group (and thus subset of Zn/Z, accounting for a fraction of all possible counterexamples), so maybe something along the lines of multiple subgroups would work i.e. (2^k, 3^k, 4^k, 5^k, etc.). One of these b is bound to generate a large subgroup of Z/nZ. Recall that (Z/nZ) can't be cyclic if n is composite, so the order is limited to the Carmichael function of n.
 2020-09-19, 09:04 #92 paulunderwood     Sep 2002 Database er0rr 22×1,063 Posts Letting r=1 is trivial as the Euler part becomes Mod(-1)^((n-1)/2). Also it is specified gcd(2-2^r,n)==1 because of x^2-(2^2/2^r-2)*x+1 r=2 does not pass gcd(4-2^r,n)==1. This comes from gcd(2^2/2^r-1,n)!=1 not being allowed. Thanks for the Carmichael link. I will study the content. Note there is no need to check cyclotomy for gcd(2^2/2^r-3,n)!=1 as divisors should be 6k+1 not 6k-1 ??? Last fiddled with by paulunderwood on 2020-09-19 at 10:18
 2020-09-19, 17:44 #93 paulunderwood     Sep 2002 Database er0rr 102348 Posts A variation on the theme I have been considering x^2-2*x+2^r=0 and have been taking n+1 powers of x over it. I can also take n+1 powers over x^2-(4/2^r-2)+1 and expect the answer to be 1. This gives rise to (yet) another test for odd non-square n where a=2^r: r>2 -- this is practical up to znorder(Mod(2,n)) gcd(a-2,n)==1 kronecker(1-a,n)==-1 Mod(1-a,n)^((n-1)/2)==-1 Mod(2,n)^(n-1)==1 Mod(Mod(x,n),x^2-(4/a-2)*x+1)^(n+1)==1 Verification of this test is fast because I can use a list of PSP-2s and check (n-1)%znorder(Mod(2,n)==0. There is no counterexample for n<10^12. For a practical test start r at 3 and keep on incrementing if kronecker(1-a,n)!=-1. Last fiddled with by paulunderwood on 2020-09-22 at 04:53
2020-09-20, 00:04   #94
carpetpool

"Sam"
Nov 2016

5178 Posts

Quote:
 Originally Posted by paulunderwood Letting r=1 is trivial as the Euler part becomes Mod(-1)^((n-1)/2). Also it is specified gcd(2-2^r,n)==1 because of x^2-(2^2/2^r-2)*x+1 r=2 does not pass gcd(4-2^r,n)==1. This comes from gcd(2^2/2^r-1,n)!=1 not being allowed. Thanks for the Carmichael link. I will study the content. Note there is no need to check cyclotomy for gcd(2^2/2^r-3,n)!=1 as divisors should be 6k+1 not 6k-1 ???

The pseudoprimes associated with r=1 are just those 2-SPRPs congruent to 3 mod 4. We need some way to avoid trivial cases. As you suggest, gcd(2^r-2,n)=1 is a good requirement. Whether my claim could still possibly hold is unclear.

(BTW, I got your program you emailed me a few days ago to work successfully!).

Edit: The code you posted with n = 30169231, so far it seems like we have

gcd(Mod(b,n)^(s-r)-1,n) = Mod(0,127). The fact that they are all divisible by the same prime should be a good indicator of something.

Last fiddled with by carpetpool on 2020-09-20 at 00:07

2020-09-22, 17:02   #95
paulunderwood

Sep 2002
Database er0rr

22×1,063 Posts

Quote:
 Originally Posted by paulunderwood I have been considering x^2-2*x+2^r=0 and have been taking n+1 powers of x over it. I can also take n+1 powers over x^2-(4/2^r-2)+1 and expect the answer to be 1. This gives rise to (yet) another test for odd non-square n where a=2^r: r>2 -- this is practical up to znorder(Mod(2,n)) gcd(a-2,n)==1 kronecker(1-a,n)==-1 Mod(1-a,n)^((n-1)/2)==-1 Mod(2,n)^(n-1)==1 Mod(Mod(x,n),x^2-(4/a-2)*x+1)^(n+1)==1 Verification of this test is fast because I can use a list of PSP-2s and check (n-1)%znorder(Mod(2,n)==0. There is no counterexample for n<10^12. For a practical test start r at 3 and keep on incrementing if kronecker(1-a,n)!=-1.
I can tighten things up by doing the following test (for any a=2^r):
• gcd(a-2,n)==1
• gcd(a-4,n)==1
• kronecker(1-a,n)==-1
• Mod(1-a,n)^((n-1)/2)==-1
• Mod(2,n)^((n-1)/2)==kronecker(2,n)
• Mod(Mod(x,n),x^2-(4/a-2)*x+1)^((n+1)/2)==kronecker(a,n)

Reaching 10^15 should be doable over time and by dedicating enough cores to it; It took just over 2 days to get to 10^12 using Pari/GP on a single core. Rewriting in GMP+pari will speed up computation.

Last fiddled with by paulunderwood on 2020-09-22 at 17:05

 2020-09-23, 20:50 #96 tuckerkao   "Tucker Kao" Jan 2020 Head Base M168202123 75010 Posts I enjoy to power up the 6 because it's an easy number for me keep times by itself - MOD: Poster uses base 12, but does not say so. 6^2 = 30 6^3 = 160 6^4 = 900 6^5 = 4,600 6^6 = 23,000 6^7 = 116,000 6^8 = 690,000 6^9 = 3,460,000 6^Ӿ = 18,300,000 6^Ɛ = Ӿ1,600,000 6^10 = 509,000,000 Last fiddled with by VBCurtis on 2020-09-23 at 21:19
 2020-09-23, 20:52 #97 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 20778 Posts You'd have to mention that you are not talking about a widely used base here... 62 = 36 in decimal (etc.). Last fiddled with by kruoli on 2020-09-23 at 20:52 Reason: And more!
 2020-09-23, 22:20 #98 paulunderwood     Sep 2002 Database er0rr 109C16 Posts This thread is supposed to be about PRP tests using bases over restricted domains, as the content (up until now) shows. It is not really about base changes or coloured balls! Please keep your tripe in their own threads without leaking sewerage into other threads!
2020-09-23, 22:50   #99
paulunderwood

Sep 2002
Database er0rr

22·1,063 Posts
Paper + Program

Here is a "flawless" replacement paper to a previous paper.

I have also attached the GMP program used to log cases where GCDs were required, and the log.

Attached Files
 Euler-Frobenius_Probable_Prime_Test.pdf (42.3 KB, 122 views) 2_r_Euler-Frobenius.c (3.6 KB, 118 views) 2_r_Euler-Frobenius.dat.txt (4 Bytes, 125 views) 2_r_Euler-Frobenius.log.txt (6.7 KB, 116 views)

Last fiddled with by paulunderwood on 2020-09-24 at 08:08

 Similar Threads Thread Thread Starter Forum Replies Last Post Uncwilly Astronomy 6 2018-02-01 05:40 Miszka Information & Answers 2 2014-07-04 17:11 Xyzzy Lounge 6 2012-03-25 22:57 R.D. Silverman Factoring 5 2006-01-26 09:14 clowns789 Hardware 1 2003-12-27 16:57

All times are UTC. The time now is 15:25.

Sat Aug 13 15:25:29 UTC 2022 up 37 days, 10:12, 2 users, load averages: 1.11, 0.99, 0.96