Amazing pattern with -12 (was -3) - Page 4

paulunderwood · 2022-12-18, 17:49

Quote:

Originally Posted by Andrew Usher

How did my last post end up here? It was posted only to the Wagstaff forum, in reply to 'primality test' proposals that apparently dominate that forum.

Still, it seems almost appropriate here, because you also don't seem to appreciate the need for a proof. People generally aren't interested in another PRP test, as we already have adequate ones (for very large numbers, time is the crucial factor, and the simple Fermat (or strong Fermat) test is faster than any other). You can't just hand wave 'this can probably be converted to a deterministic test'; you need to at least try to outline a proof, and no amount of computation gets any closer to doing that.

I aim to please.

Now consider b=3 and b=-3. There are corresponding pseudoprimes:

Code:

{forstep(n=3,10000000,2,
if(!ispseudoprime(n),
forstep(b=-3,3,6,
if(gcd(b,n)==1&&Mod(b,n)^((n-1)/2)==kronecker(b,n),
z=znorder(Mod(b,n));if(z%2==0&&Mod(b,n)^(z/2)==-1,
for(r=1,z/2,
D=lift(Mod(b,n)^(2*r)-4*b);if(kronecker(D,n)==-1&&Mod(Mod(x,n),x^2-(Mod(b,n)^(2*r-1)-2)*x+1)^((n+1)/2)==kronecker(b,n),
g=gcd(r-1,n-1);print([n,b,z,r,g]))))))));}    
[3281, -3, 16, 5, 4]                                                 
[3281, 3, 16, 1, 3280]
[432821, -3, 268, 68, 67]
[432821, 3, 268, 1, 432820]
[973241, -3, 232, 59, 58]
[973241, 3, 232, 1, 973240]
[1551941, -3, 508, 128, 127]
[1551941, 3, 508, 1, 1551940]
[2202257, -3, 112, 29, 28]
[2202257, 3, 112, 1, 2202256]
[2545181, -3, 460, 116, 115]
[2545181, 3, 460, 1, 2545180]
[3020093, -3, 268, 68, 67]
[3020093, 3, 268, 1, 3020092]
[3028133, -3, 268, 68, 67]
[3028133, 3, 268, 1, 3028132]
[4561481, -3, 616, 155, 154]
[4561481, 3, 616, 1, 4561480]
[4923521, -3, 640, 161, 160]
[4923521, 3, 640, 1, 4923520]
[5173601, -3, 928, 233, 232]
[5173601, 3, 928, 1, 5173600]
[5193161, -3, 280, 71, 70]
[5193161, 3, 280, 1, 5193160]
[5774801, -3, 400, 101, 100]
[5774801, 3, 400, 1, 5774800]
[6710177, -3, 352, 89, 88]
[6710177, 3, 352, 1, 6710176]
[9846401, -3, 640, 161, 160]
[9846401, 3, 640, 1, 9846400]

Andrew Usher · 2022-12-18, 19:09

As this clearly isn't an attempt at a proof, I'm going to ignore you like everyone else does.

paulunderwood · 2022-12-19, 00:06

Quote:

Originally Posted by Andrew Usher

As this clearly isn't an attempt at a proof, I'm going to ignore you like everyone else does.

I don't blame you for that.

You mentioned earlier we have Fermat PRP and strong Fermat. Both these are no foolproof and PSPs (pseudoprimes) can be constructed. e.g. Carmichael (absolute PSP) numbers for Fermat PRP.

Lucas sequence can be used as an alternative. It is now known whether absolute PSPs exist for Lucas.

Then there is BPSW. It is believed that counterexamples exist for this test: See: https://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html and http://pseudoprime.com/dopo.pdf

I am not convinced by my own reasoning -- albeit shallow -- that my tests for b=-3 and b=-12 are true or not.

Until I have a proof I will keep shtum!

chalsall · 2022-12-19, 00:40

Quote:

Originally Posted by paulunderwood

I am not convinced by my own reasoning -- albeit shallow -- that my tests for b=-3 and b=-12 are true or not. Until I have a proof I will keep shtum!

Please forgive me for this, but...

I greatly enjoy watching people do things. Sometimes things work; sometimes things don't...

Please keep working on this until you have either proven everyone else incorrect, or you have proven to yourself that you are incorrect.

I go down *so* many rabbit holes that are a waste of R&D time. But, rarely, there gold down in those holes! 8^)

P.S. Has anyone worked with the PRUs on some ARM kit? Kinda cool...

LaurV · 2022-12-19, 14:31

Quote:

Originally Posted by paulunderwood

It is now known whether absolute PSPs exist for Lucas.

you mean it is not known

paulunderwood · 2022-12-20, 04:35

I'm back by popular demand!

The key with x^2-3^r*x-3 was to transform it to z^2-((-3)^(2*r-1)-2)*z+1 and note that (-3)^(2*r-1)-2 = -3*(3^(2*(r-1))+1)+3-2. So we want to "avoid" 3^(4*(r-1))-1. Thus avoiding cyclotomic z^2-z+1

With the transformation of x^2-2^r*x+1 to z^2-(-2^(2*r-1)-2)*z+1 the "key" is to notice that (-2)^(2*r-1) - 2 = (-2)^(2*r-1)-1+1-2. where we want to "avoid" 2^(2*(2*r-1))-1. So we take gcd(2*r-1,n)==1. We avoid cyclotomic z^2+z+1

Here is some more code I am running. The patterns are (multiplicative order) z is odd for pseudoprimes and these only exist for n%6==5. Using Feitsma's 2-PSP list:

Code:

{b=-2;for(v=1,#V,
n=V[v];if(Mod(b,n)^((n-1)/2)==kronecker(b,n),
z=znorder(Mod(b,n));for(r=1,z,
a=lift(Mod(b,n)^r);D=lift(a^2-4*b);if(kronecker(D,n)==-1&&Mod(Mod(x,n),x^2-a*x+b)^(n+1)==b,
g=gcd(2*r-1,n-1);print([n,n%6,b,z,g,r])))));}

Another pattern for pseudoprimes (which can be eliminated with a gcd) is that kronecker(-2,n)==1 (for b=-2) and kronecker(-3,n)==-1 (for b=-3).

Here is a table of patterns for pseudoprimes:

Code:

b==-2; z odd;   kronecker(-2,n)==1;   n%6==5; requires gcd(2*r-1,n-1); exists a pseudoprime for r=(z+1)/2;
b==-3; z even;  kronecker(-3,n)==-1; n%12==5; requires gcd(r-1,n-1);   exists a pseudoprime for r=z/4+1;

paulunderwood · 2022-12-22, 14:36

Quote:

Originally Posted by paulunderwood

Here is a table of patterns for pseudoprimes:

Code:

b==-2; z odd;   kronecker(-2,n)==1;   n%6==5; requires gcd(2*r-1,n-1); exists a pseudoprime for r=(z+1)/2;
b==-3; z even;  kronecker(-3,n)==-1; n%12==5; requires gcd(r-1,n-1);   exists a pseudoprime for r=z/4+1;

Code:

[452295831401, 5, -2, 9716, 2429, 3644]
[452295831401, 5, -2, 9716, 2429, 8502]

Here z is even for b=-2 and there is no pseudoprime "r=(z+1)/2", yet gcd(2*r-1,n-1) != 1.

Another pattern might be z < sqrt(n).

paulunderwood · 2023-01-30, 00:05

The test x^(n+1)==-3 (mod n, x^2-3^r*x-3) and gcd(r-1,n-1) pans out for n < 10^13 and all r.

The verification with GMP+primesieve took several weeks on a dual core Celeron. If the code was run on some big iron machines then a much higher bound could be achieved, but I believe not high enough to find a pseudoprime.

paulunderwood · 2023-05-17, 15:32

If instead I compute over x^2-x-(-12)^r I observe the following:

pseudoprimes only exist for n==5 mod 6
if z is znorder of -12 mod n then pseudoprimes are exactly for r=z/2.

with this chink in knowledge can you prove anything, given it is implicit that n must be a base -12 Euler pseudoprime?

On the other hand there is only output of pseudoprimes over x^2-x+12^r for r==z where z is the order of 12

paulunderwood · 2023-06-29, 21:25

mart_t and I checked for pseudoprimes w.r.t. x^2-12^r*x-12 for n<10^12 some months back na drew a blank. I have continued checking but only Carmichael numbers and have reached 10^13 (on a 1.1GHz Celeron core with pari-gp).

paulunderwood · 2023-07-07, 22:06

Having searched Wiki for "12" I found that: "Twelve is the smallest weight for which a cusp form exists... SL(2,Z)....."

https://en.wikipedia.org/wiki/12_(number)

Being a bear of little brain I ask the question: "Could this have something to do with the GCD-less test based on x^2-12^r*x-12?"

2022-12-20, 04:35	#39
paulunderwood Sep 2002 Database er0rr 11313₈ Posts	The case for b=-2 I'm back by popular demand! The key with x^2-3^rx-3 was to transform it to z^2-((-3)^(2r-1)-2)z+1 and note that (-3)^(2r-1)-2 = -3(3^(2(r-1))+1)+3-2. So we want to "avoid" 3^(4(r-1))-1. Thus avoiding cyclotomic z^2-z+1 With the transformation of x^2-2^rx+1 to z^2-(-2^(2r-1)-2)z+1 the "key" is to notice that (-2)^(2r-1) - 2 = (-2)^(2r-1)-1+1-2. where we want to "avoid" 2^(2(2r-1))-1. So we take gcd(2r-1,n)==1. We avoid cyclotomic z^2+z+1 Here is some more code I am running. The patterns are (multiplicative order) z is odd for pseudoprimes and these only exist for n%6==5. Using Feitsma's 2-PSP list: Code: {b=-2;for(v=1,#V, n=V[v];if(Mod(b,n)^((n-1)/2)==kronecker(b,n), z=znorder(Mod(b,n));for(r=1,z, a=lift(Mod(b,n)^r);D=lift(a^2-4b);if(kronecker(D,n)==-1&&Mod(Mod(x,n),x^2-ax+b)^(n+1)==b, g=gcd(2r-1,n-1);print([n,n%6,b,z,g,r])))));} Another pattern for pseudoprimes (which can be eliminated with a gcd) is that kronecker(-2,n)==1 (for b=-2) and kronecker(-3,n)==-1 (for b=-3). Here is a table of patterns for pseudoprimes: Code: b==-2; z odd; kronecker(-2,n)==1; n%6==5; requires gcd(2r-1,n-1); exists a pseudoprime for r=(z+1)/2; b==-3; z even; kronecker(-3,n)==-1; n%12==5; requires gcd(r-1,n-1); exists a pseudoprime for r=z/4+1; Last fiddled with by paulunderwood on 2022-12-20 at 06:54*

2023-05-17, 15:32	#42
paulunderwood Sep 2002 Database er0rr 17×283 Posts	More on 12 If instead I compute over x^2-x-(-12)^r I observe the following: pseudoprimes only exist for n==5 mod 6 if z is znorder of -12 mod n then pseudoprimes are exactly for r=z/2. with this chink in knowledge can you prove anything, given it is implicit that n must be a base -12 Euler pseudoprime? On the other hand there is only output of pseudoprimes over x^2-x+12^r for r==z where z is the order of 12 Last fiddled with by paulunderwood on 2023-05-17 at 15:33

2023-07-07, 22:06	#44
paulunderwood Sep 2002 Database er0rr 12CB₁₆ Posts	Having searched Wiki for "12" I found that: "Twelve is the smallest weight for which a cusp form exists... SL(2,Z)....." https://en.wikipedia.org/wiki/12_(number) Being a bear of little brain I ask the question: "Could this have something to do with the GCD-less test based on x^2-12^rx-12?" Last fiddled with by paulunderwood on 2023-07-07 at 23:22*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Amazing 6	paulunderwood	Miscellaneous Math	118	2021-03-18 21:53
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

2022-12-18, 19:09	#35
Andrew Usher Dec 2022 2×3×7×13 Posts	As this clearly isn't an attempt at a proof, I'm going to ignore you like everyone else does.

2023-01-30, 00:05	#41
paulunderwood Sep 2002 Database er0rr 1001011001011₂ Posts	The test x^(n+1)==-3 (mod n, x^2-3^r*x-3) and gcd(r-1,n-1) pans out for n < 10^13 and all r. The verification with GMP+primesieve took several weeks on a dual core Celeron. If the code was run on some big iron machines then a much higher bound could be achieved, but I believe not high enough to find a pseudoprime.

2023-06-29, 21:25	#43
paulunderwood Sep 2002 Database er0rr 17×283 Posts	mart_t and I checked for pseudoprimes w.r.t. x^2-12^r*x-12 for n<10^12 some months back na drew a blank. I have continued checking but only Carmichael numbers and have reached 10^13 (on a 1.1GHz Celeron core with pari-gp).