mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-09-17, 15:28   #89
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

1001111002 Posts
Post

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.
carpetpool is offline   Reply With Quote
Old 2020-09-17, 16:41   #90
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,723 Posts
Default

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]
paulunderwood is offline   Reply With Quote
Old 2020-09-19, 08:35   #91
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

4748 Posts
Default

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.
carpetpool is offline   Reply With Quote
Old 2020-09-19, 09:04   #92
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D7616 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2020-09-19, 17:44   #93
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,723 Posts
Cool 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
paulunderwood is offline   Reply With Quote
Old 2020-09-20, 00:04   #94
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22×79 Posts
Post

Quote:
Originally Posted by paulunderwood View Post
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
carpetpool is offline   Reply With Quote
Old 2020-09-22, 17:02   #95
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,723 Posts
Cool

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote
Old 2020-09-23, 20:50   #96
tuckerkao
 
Jan 2020

1708 Posts
Default

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
tuckerkao is offline   Reply With Quote
Old 2020-09-23, 20:52   #97
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

32×37 Posts
Default

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!
kruoli is offline   Reply With Quote
Old 2020-09-23, 22:20   #98
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

344610 Posts
Thumbs down

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 is offline   Reply With Quote
Old 2020-09-23, 22:50   #99
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101011101102 Posts
Thumbs up 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.)
Attached Files
File Type: pdf Euler-Frobenius_Probable_Prime_Test.pdf (42.3 KB, 19 views)
File Type: c 2_r_Euler-Frobenius.c (3.6 KB, 12 views)
File Type: txt 2_r_Euler-Frobenius.dat.txt (4 Bytes, 11 views)
File Type: txt 2_r_Euler-Frobenius.log.txt (6.7 KB, 11 views)

Last fiddled with by paulunderwood on 2020-09-24 at 08:08
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 00:06.

Thu Oct 29 00:06:02 UTC 2020 up 48 days, 21:17, 1 user, load averages: 1.29, 1.77, 1.82

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.