mersenneforum.org Amazing pattern with -12 (was -3)
 Register FAQ Search Today's Posts Mark Forums Read

2022-12-18, 17:49   #34
paulunderwood

Sep 2002
Database er0rr

17×283 Posts

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.

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]

Last fiddled with by paulunderwood on 2022-12-18 at 18:03

 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.
2022-12-19, 00:06   #36
paulunderwood

Sep 2002
Database er0rr

113138 Posts

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!

2022-12-19, 00:40   #37
chalsall
If I May

"Chris Halsall"
Sep 2002

101100100111002 Posts

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

2022-12-19, 14:31   #38
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

1035810 Posts

Quote:
 Originally Posted by paulunderwood It is now known whether absolute PSPs exist for Lucas.
you mean it is not known

 2022-12-20, 04:35 #39 paulunderwood     Sep 2002 Database er0rr 113138 Posts The case for b=-2 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; Last fiddled with by paulunderwood on 2022-12-20 at 06:54
2022-12-22, 14:36   #40
paulunderwood

Sep 2002
Database er0rr

10010110010112 Posts

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

Last fiddled with by paulunderwood on 2022-12-22 at 14:38

 2023-01-30, 00:05 #41 paulunderwood     Sep 2002 Database er0rr 10010110010112 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-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-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).
 2023-07-07, 22:06 #44 paulunderwood     Sep 2002 Database er0rr 12CB16 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^r*x-12?" Last fiddled with by paulunderwood on 2023-07-07 at 23:22

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

Sun Oct 1 15:42:02 UTC 2023 up 18 days, 13:24, 0 users, load averages: 1.02, 0.80, 0.77