mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2021-06-16, 02:51   #1
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

10001100002 Posts
Default Possible extension to P-1 Stage 2

I know lots of these ideas come along, and I am getting more comfortable with the math involved with Stage 2 as I write this, so please forgive me if I missed something.

From what I understand, in the P-1 factoring stage 1, Given Mp, we calculate 3^(2*E*p)-1 mod Mp where E is the product of many powers of prime factors less than a number B1. In stage 2, for various primes q between B1 and B2, we then calculate 3^(2*E*p*q)-1 mod Mp.

Noting that every prime q divides 2^n-1 for some value of n (and in fact all integer multiples of n), would it be feasible in some cases to instead calculate 3^(2*E*p*(2^n-1))-1 mod Mp for such a value of n?
JuanTutors is offline   Reply With Quote
Old 2021-06-16, 07:01   #2
Zhangrc
 
"University student"
May 2021
Beijing, China

2×53 Posts
Default

That's right, but the extension is not economic. You need even more iterations to calculate it. Also you can't directly use your sub-products for PRP either, unless you calculate modular inverses (higher complexity!)
Zhangrc is offline   Reply With Quote
Old 2021-06-16, 20:44   #3
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

23016 Posts
Default

Ahh, I see my error. I was comparing 3^Mp-1 to 2^n-1 instead of 3^(2^n-1).
JuanTutors is offline   Reply With Quote
Old 2021-06-17, 16:46   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

100110111010102 Posts
Default

Quote:
Originally Posted by JuanTutors View Post
3^(2*E*p*(2^n-1))-1 mod Mp
Then you take the GCD step, and... what?
LaurV is offline   Reply With Quote
Old 2021-06-17, 19:00   #5
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

23016 Posts
Default

Quote:
Originally Posted by LaurV View Post
Then you take the GCD step, and... what?
I did realize my error as I explained above but I did post in another thread by Zhangrc a more correct modification of this test. I'll reply there.

https://mersenneforum.org/showthread.php?t=26863&page=2
JuanTutors is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Extension request LaurV Data 9 2019-04-14 00:13
PCI-E USB 3.0 Extension Cable vsuite GPU Computing 7 2017-07-10 20:45
Stage 1 with mprime/prime95, stage 2 with GMP-ECM D. B. Staple Factoring 2 2007-12-14 00:21
brent suyama extension in P-1 bsquared Factoring 9 2007-05-18 19:24
Stage 1 and stage 2 tests missing Matthias C. Noc PrimeNet 5 2004-08-25 15:42

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


Sat May 21 15:04:07 UTC 2022 up 37 days, 13:05, 0 users, load averages: 1.20, 1.15, 1.23

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

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