Amazing 6

[carpetpool]

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.

[paulunderwood]

Your idea seems right. I ran some of this:

{
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:

[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]

[carpetpool]

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.

(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).

(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.

[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 ???

[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.

[carpetpool]

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.

[paulunderwood]

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.

[tuckerkao]

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

[kruoli]

You'd have to mention that you are not talking about a widely used base here... 6² = 36 in decimal (etc.).

[paulunderwood]

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!

[paulunderwood]

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.)