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

 2022-11-27, 16:47 #23 paulunderwood     Sep 2002 Database er0rr 2×33×83 Posts As with "-12" (GCD-less probably because the discriminant of at r=znorder(Mod(-12,n)) is 1+48, a square) compared to "12", and comparing "-3" to "3" -- the latter needing GCD depending on whether n is 1 or 3 mod 4 -- the same can be said about "-2". This seems only to need a check for gcd(2*r-1,n-1)==1. It is all confusing, but it seems some (positive?) values need either a check of gcd(r-1,n-1)==1 or gcd(2*r-1,n-1)==1 depending on n%4.; The negative values require at most one GCD check be that 2*r-1 as with "-2" or r-1 as with "-3". What am taking about? Working over the equation x^2-b^r*x+b = 0. Last fiddled with by paulunderwood on 2022-11-27 at 16:47
 2022-12-13, 21:07 #24 paulunderwood     Sep 2002 Database er0rr 2×33×83 Posts Another attempted proof Having read the paper attached to this thread earlier, rather than considering (-3)^(4*(r-1))-1 if we consider (-3)^(2*(r-1))+1 -- the predecessor -- we have (-3)^(2*(r-1)) == -1 mod n. But then multiplicative order of -3 mod n called z must be even and (-3)^(z/2) == -1 mod n. Therefore (-3)^(2*(r-1)) == (-3)^(z/2) mod n. If 1<=r<=z then 4*(r-1) = z (**). But z | n-1 and we have already stipulated that gcd(r-1,n-1)==1. So gcd(r-1,z)==1. Thus (**) is impossible. Is this a proof of a lemma? Last fiddled with by paulunderwood on 2022-12-13 at 21:18
 2022-12-13, 21:54 #25 RMLabrador   "Chereztynnoguzakidai" Oct 2022 Ukraine, near Kyiv. 2×23 Posts sorry silly me (i'm lost the point, here in Ukraine now is the real AC/DC problem))), we still talk about something for pseudoprimes only or else?
2022-12-13, 21:59   #26
paulunderwood

Sep 2002
Database er0rr

2·33·83 Posts

Quote:
 Originally Posted by RMLabrador sorry silly me (i'm lost the point, here in Ukraine now is the real AC/DC problem))), we still talk about something for pseudoprimes only or else?
Pseudoprimes for now, but hopefully leading to a prime test. If the argument just given is valid, then it is one step in the right direction.

 2022-12-13, 22:19 #27 RMLabrador   "Chereztynnoguzakidai" Oct 2022 Ukraine, near Kyiv. 2·23 Posts I remember, I mumbled something about tree, so pseudoprime is a tree, an average tree, there is nothing special in them - their existence is only flaws in out primality test; take the true test - and we have NO pseudiprimes, and what are we suppose to do now?
2022-12-13, 22:29   #28
paulunderwood

Sep 2002
Database er0rr

448210 Posts

Quote:
 Originally Posted by RMLabrador I remember, I mumbled something about tree, so pseudoprime is a tree, an average tree, there is nothing special in them - their existence is only flaws in out primality test; take the true test - and we have NO pseudiprimes, and what are we suppose to do now?
Even a large tree starts out as a small one. A pseudoprime test that has no known counterexample for all parameters for n<2*10^12 (on a Celeron core); A test that may well turn out to be a revolutionary primality test. Instead of months on mullticore systems, a *proof* in minutes on one core! But I need someone to check over my lemma given above, before proceeding to a fully fledged proof attempt.

Last fiddled with by paulunderwood on 2022-12-13 at 22:31

 2022-12-13, 23:15 #29 RMLabrador   "Chereztynnoguzakidai" Oct 2022 Ukraine, near Kyiv. 2·23 Posts You know, the Solar core of our Sun, have a temperatures of 10 up to 15 million kelvins +- a few millions))) Here the diff btw mathematican&astronomer For me, the One Million Kelvins diff is OK The wierld mathmans from mersenneforums never say this and proof seems unlikely, sorry ((Every time using mod() (in prime test or so) we just like Moses&water from stone Sweet, but grave sin))
2022-12-14, 02:31   #30
paulunderwood

Sep 2002
Database er0rr

448210 Posts

Quote:
 Originally Posted by RMLabrador You know, the Solar core of our Sun, have a temperatures of 10 up to 15 million kelvins +- a few millions))) Here the diff btw mathematican&astronomer For me, the One Million Kelvins diff is OK The wierld mathmans from mersenneforums never say this and proof seems unlikely, sorry ((Every time using mod() (in prime test or so) we just like Moses&water from stone Sweet, but grave sin))
Instead of hand-waving and saying it just can't be true because mathematicians would find the truth of my argument unlikely, please pin point the error in the argument I gave in post #24.

Here is another argument. From the test we know (-3)^(n-1) == 1 mod n. We know (-3)^z == 1 mod n by definition. If (-3)^(4*(n-1)) == 1 mod n, then z | n-1 and z | 4*(r-1), but we have taken gcd(r-1,n-1) = 1. So z | 4. I.e. 80 == 0 mod n. So n must be 5. Where is flaw in this simpler argument?

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

 2022-12-17, 16:34 #31 Andrew Usher   Dec 2022 199 Posts Amazing pattern with -12 (was -3) Any proposed deterministic primality test absolutely requires a proof! If you don't know the different between a deterministic and a probable prime test (the latter of which we already have well enough) then you probably aren't going to be making a contribution. There isn't only one method of proof as the LL test shows. But some proof is necessary, not just checking that known primes satisfy it. Even if you also proved that all _composites_ up to a large limit failed the test, it wouldn't count as a proof. Such a primality proof would likely represent a significant breakthrough especially since it could probably be extended to other repunits and repunit-like numbers.
 2022-12-18, 05:08 #32 paulunderwood     Sep 2002 Database er0rr 2×33×83 Posts The case for 3 Consider working over x^2-3^r*x+3 (**) We want gcd(r-1,n-1)=1 as stated earlier. We also know the multiplicative order z (of 3 mod n) is even and 3^(z/2)==-1 mod n. Now x^2-3^(z/2)*3+3=0 is x^2+3*x+3=0. This is the same as (**) if we are taking (n+1)th powers of x over it. I claim there are only pseudoprimes for r=1 and r=z/2+1, both of which can be eliminated by taking gcd(r-1,n-1)=1. Here is code that I a am running: Code: {b=3;forstep(n=3,1000000000000,2, if(gcd(b,n)==1&&!ispseudoprime(n)&&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]))))));} The above claim is not quite right as I get output: Code: [28027505969, 3, 4048, 1, 28027505968] [28027505969, 3, 4048, 1233, 1232] Some more thinking is needed! I note z*k+1=p for some k where prime p | n. For all prime pi | n for various ki? Last fiddled with by paulunderwood on 2022-12-18 at 06:53
 2022-12-18, 15:00 #33 Andrew Usher   Dec 2022 199 Posts 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.

 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 16:11.

Sat Jan 28 16:11:33 UTC 2023 up 163 days, 13:40, 0 users, load averages: 0.78, 1.03, 1.14