mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-11-27, 16:47   #23
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×33×83 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2022-12-13, 21:07   #24
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×33×83 Posts
Default 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
paulunderwood is offline   Reply With Quote
Old 2022-12-13, 21:54   #25
RMLabrador
 
"Chereztynnoguzakidai"
Oct 2022
Ukraine, near Kyiv.

2×23 Posts
Default

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?
RMLabrador is offline   Reply With Quote
Old 2022-12-13, 21:59   #26
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·33·83 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
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.
paulunderwood is offline   Reply With Quote
Old 2022-12-13, 22:19   #27
RMLabrador
 
"Chereztynnoguzakidai"
Oct 2022
Ukraine, near Kyiv.

2·23 Posts
Default

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?
RMLabrador is offline   Reply With Quote
Old 2022-12-13, 22:29   #28
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

448210 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
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
paulunderwood is offline   Reply With Quote
Old 2022-12-13, 23:15   #29
RMLabrador
 
"Chereztynnoguzakidai"
Oct 2022
Ukraine, near Kyiv.

2·23 Posts
Default

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))
RMLabrador is offline   Reply With Quote
Old 2022-12-14, 02:31   #30
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

448210 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
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
paulunderwood is offline   Reply With Quote
Old 2022-12-17, 16:34   #31
Andrew Usher
 
Dec 2022

199 Posts
Default 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.
Andrew Usher is offline   Reply With Quote
Old 2022-12-18, 05:08   #32
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×33×83 Posts
Default 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
paulunderwood is offline   Reply With Quote
Old 2022-12-18, 15:00   #33
Andrew Usher
 
Dec 2022

199 Posts
Default

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.
Andrew Usher is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔