mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-05-02, 18:54   #12
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·29·31 Posts
Default

Quote:
Originally Posted by ONeil View Post
Paul can you elaborate on this concept of rapid verification of Mprime?.
It is defunct point now that Dr Sardonicus has shown it fails as a concept for non-prime 2^37-1, but the idea was to take x, square and add 6.
paulunderwood is offline   Reply With Quote
Old 2018-05-02, 18:58   #13
ONeil
 
ONeil's Avatar
 
Dec 2017

24×3×5 Posts
Wink

Quote:
Originally Posted by paulunderwood View Post
It is defunct point now that Dr Sardonicus has shown it fails as a concept for non-prime 2^37-1, but the idea was to take x, square and add 6.
oh well I was rooting for you in your corner:)
37 is an anomaly in my book it always screws us!
ONeil is offline   Reply With Quote
Old 2018-05-02, 20:03   #14
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·29·31 Posts
Default

I now have a new test to add to the previous 2:
Code:
f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2+1/a);a==2

f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2+3/a);a==0

f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2-1/a);a==0 [new]
Can you find any more such tests?
paulunderwood is offline   Reply With Quote
Old 2018-05-02, 23:06   #15
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·32·191 Posts
Default

I do not think I understand them, I do not use Pari/GP.

f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2+1/a);a==2

You start with a=2 and then you to (p-1) steps: a=(a/2 + 1/a)%Mp where 1/a is the modular inverse mod Mp, and the result after (p-1) steps a==2 for Mersenne primes?
What about a/2 when a is odd? is that integer division?
ATH is offline   Reply With Quote
Old 2018-05-02, 23:16   #16
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts
Default

Quote:
Originally Posted by ATH View Post
I do not think I understand them, I do not use Pari/GP.

f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2+1/a);a==2

You start with a=2 and then you to (p-1) steps: a=(a/2 + 1/a)%Mp where 1/a is the modular inverse mod Mp, and the result after (p-1) steps a==2 for Mersenne primes?
What about a/2 when a is odd? is that integer division?
Modularly it should be 1 mod mp in the first case and 1/a in that same case would be 2^(p-1) mod mp
science_man_88 is offline   Reply With Quote
Old 2018-05-02, 23:31   #17
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

106178 Posts
Default

Quote:
Originally Posted by ATH View Post
I do not think I understand them, I do not use Pari/GP.

f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2+1/a);a==2

You start with a=2 and then you to (p-1) steps: a=(a/2 + 1/a)%Mp where 1/a is the modular inverse mod Mp, and the result after (p-1) steps a==2 for Mersenne primes?
What about a/2 when a is odd? is that integer division?
For example a=Mod(2,7) sets up 2 (mod 7) -- it is a ring -- so a/2 is 1 (mod 7). Then 1/2 is 4 (mod 7) since 2*4 == 1 (mod 7).

Inverses are usually computed by the "extended Euclidean algorithm" which really slows down "f".

Last fiddled with by paulunderwood on 2018-05-02 at 23:47
paulunderwood is offline   Reply With Quote
Old 2018-05-02, 23:43   #18
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

118F16 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I now have a new test to add to the previous 2:
Code:
f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2-1/a);a==0 [new]
Interestingly, this algorithm works for Wagstaff (2^p+1)/3 by setting wp=2^p+1 and observing that the result is either -1 or 2:

f(p)=wp=2^p+1;a=Mod(2,wp);for(b=1,p-1,a=a/2-1/a);a==-1||a==2

(You have to fiddle with Mod and lift to get a good result for W3.)

I have not tested this very far.

Last fiddled with by paulunderwood on 2018-05-03 at 00:09
paulunderwood is offline   Reply With Quote
Old 2018-05-03, 00:05   #19
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
For example a=Mod(2,7) sets up 2 (mod 7) -- it is a ring -- so a/2 is 1 (mod 7). In the next iteration a/2 is 1/2 is 4 (mod 7) since 2*4 == 1 (mod 7).
a/2 1/a a p
.......... 2 3
1 4 5 3
6 3 2 3

In other words.

Last fiddled with by science_man_88 on 2018-05-03 at 00:07
science_man_88 is offline   Reply With Quote
Old 2018-05-03, 00:58   #20
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×32×191 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
For example a=Mod(2,7) sets up 2 (mod 7) -- it is a ring -- so a/2 is 1 (mod 7). Then 1/2 is 4 (mod 7) since 2*4 == 1 (mod 7).

Inverses are usually computed by the "extended Euclidean algorithm" which really slows down "f".
Ok, it worked now, so a=(a*c + 1/a) (mod Mp) where c=2-1 (mod Mp) can be calculated in advance.

So testing all 3 algorithms for all primes up to 11K they finds all Mersenne Primes up to 11213, but that does not prove them. Though it would be weird for them to find so many Mersenne Primes and then fail for higher primes.

Last fiddled with by ATH on 2018-05-03 at 00:59
ATH is offline   Reply With Quote
Old 2018-05-03, 02:56   #21
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

106178 Posts
Default

Quote:
Originally Posted by ATH View Post
Ok, it worked now, so a=(a*c + 1/a) (mod Mp) where c=2-1 (mod Mp) can be calculated in advance.
It is quicker to use a left shift by pre-computed t=p-1 bits: a=(a<<t+1/a) (mod Mp).
Or if a is even ">>1", else "<<t", but testing for even is slow in Pari-gp.

The hard thing remains computing of 1/s (mod Mp).

Last fiddled with by paulunderwood on 2018-05-03 at 03:05
paulunderwood is offline   Reply With Quote
Old 2018-05-04, 11:36   #22
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·29·31 Posts
Default

Here is another test for Wagstaff (2^p+1)/3:

Code:
f(p)=wp=2^p+1;a=Mod(1/2,wp);for(b=1,p-1,a=a/2-1/a);lift(a*2)%(wp/3)==1

Last fiddled with by paulunderwood on 2018-05-04 at 11:40
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fulsorials a1call Miscellaneous Math 46 2020-08-03 00:31
Java applet alternative a1call Programming 19 2019-11-08 22:31
alternative ( points of view ) cmd cmd 51 2019-09-28 14:56
CEMPLLA: An alternative to GIMPS ? CEMPLLA Author Data 233 2019-06-28 17:18
free alternative to EasyFit? ixfd64 Software 1 2008-04-26 21:28

All times are UTC. The time now is 15:00.


Sat Feb 4 15:00:47 UTC 2023 up 170 days, 12:29, 1 user, load averages: 0.97, 0.88, 0.87

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.

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