20200917, 15:28  #89 
"Sam"
Nov 2016
5×67 Posts 
I think the 12^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(1b^r,n)==1 Mod(1b^r,n)^((n1)/2)==1 Mod(Mod(1,n)*x,x^22*x+b^r)^(n+1)==b^r gcd(b^(rs)  1, n) = 1 n is a probable prime. If this test were accurate, we could obtain some fixed pairs of integers 1b^r and 1b^s to be used in the test as long as the Jacobi symbol requirements are met. 
20200917, 16:41  #90 
Sep 2002
Database er0rr
2^{2}×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(1lift(A),n)==1&&(1A)^((n1)/2)==1&& Mod(x,x^22*x+A)^(n+1)==A, for(s=r+1,z,B=Mod(b,n)^s; if(kronecker(1lift(B),n)==1&&(1B)^((n1)/2)==1&& Mod(x,x^22*x+B)^(n+1)==B, print([n,b,r,s,gcd(Mod(b,n)^(sr)1,n)])))))))))} 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] 
20200919, 08:35  #91 
"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^(11)1,n)=1.
Code:
(00:41) gp > for(n=1,10^10, if(n%12==11 & isprime(n)==0 & Mod(3,n)^((n1)/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 toplevel: 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(12^a,n)^((n1)/2)==(n1) & 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(12^a,n)^((n1)/2)==(n1) & Mod(Mod(1,n)*x,x^2+2*x+2^a)^(n+1)==2^a, print(a))) 1 2 (01:18) gp > Code:
(01:32) gp > for(a=1,znorder(Mod(2,n)), if(isprime(n)==0 & Mod(12^a,n)^((n1)/2)==(n1) & Mod(Mod(1,n)*x,x^2+2*x+2^a)^(n+1)==2^a, print(a))) 1 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. 
20200919, 09:04  #92 
Sep 2002
Database er0rr
2^{2}×1,063 Posts 
Letting r=1 is trivial as the Euler part becomes Mod(1)^((n1)/2). Also it is specified gcd(22^r,n)==1 because of x^2(2^2/2^r2)*x+1
r=2 does not pass gcd(42^r,n)==1. This comes from gcd(2^2/2^r1,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^r3,n)!=1 as divisors should be 6k+1 not 6k1 ??? Last fiddled with by paulunderwood on 20200919 at 10:18 
20200919, 17:44  #93 
Sep 2002
Database er0rr
10234_{8} Posts 
A variation on the theme
I have been considering x^22*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^r2)+1 and expect the answer to be 1. This gives rise to (yet) another test for odd nonsquare n where a=2^r:
r>2  this is practical up to znorder(Mod(2,n)) gcd(a2,n)==1 kronecker(1a,n)==1 Mod(1a,n)^((n1)/2)==1 Mod(2,n)^(n1)==1 Mod(Mod(x,n),x^2(4/a2)*x+1)^(n+1)==1 Verification of this test is fast because I can use a list of PSP2s and check (n1)%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(1a,n)!=1. Last fiddled with by paulunderwood on 20200922 at 04:53 
20200920, 00:04  #94  
"Sam"
Nov 2016
517_{8} Posts 
Quote:
The pseudoprimes associated with r=1 are just those 2SPRPs congruent to 3 mod 4. We need some way to avoid trivial cases. As you suggest, gcd(2^r2,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)^(sr)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 20200920 at 00:07 

20200922, 17:02  #95  
Sep 2002
Database er0rr
2^{2}×1,063 Posts 
Quote:
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 20200922 at 17:05 

20200923, 20:50  #96 
"Tucker Kao"
Jan 2020
Head Base M168202123
750_{10} 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 20200923 at 21:19 
20200923, 20:52  #97 
"Oliver"
Sep 2017
Porta Westfalica, DE
2077_{8} Posts 
You'd have to mention that you are not talking about a widely used base here... 6^{2} = 36 in decimal (etc.).
Last fiddled with by kruoli on 20200923 at 20:52 Reason: And more! 
20200923, 22:20  #98 
Sep 2002
Database er0rr
109C_{16} 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!

20200923, 22:50  #99 
Sep 2002
Database er0rr
2^{2}·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. (Remove ".txt" suffix after downloads.) Last fiddled with by paulunderwood on 20200924 at 08:08 
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  20180201 05:40 
Amazing result in P1  Miszka  Information & Answers  2  20140704 17:11 
Amazing academic resource  Xyzzy  Lounge  6  20120325 22:57 
Amazing!!!  R.D. Silverman  Factoring  5  20060126 09:14 
Two Amazing Things  clowns789  Hardware  1  20031227 16:57 