mersenneforum.org  

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

Reply
 
Thread Tools
Old 2014-03-08, 23:44   #1
siegert81
 
Dec 2010

2×37 Posts
Default P-1 factoring question

From "The Math" section of GIMPS:

Quote:
This method when adapted to Mersenne numbers is even more effective. Remember, that the factor q is of the form 2kp+1. It is easy to modify the P-1 method such that it will find the factor q whenever k is highly composite.

The P-1 method is quite simple. In stage 1 we pick a bound B1. P-1 factoring will find the factor q as long as all factors of k are less than B1 (k is called B1-smooth). We compute E – the product of all primes less than B1. Then we compute x = 3^E*2*P. Finally, we check the GCD (x-1, 2P-1) to see if a factor was found.
Does Prime95 only use one power of each prime less than B1 when computing E? Or does it use numerous powers of 2,3,5,7,11,13 and all other very small primes? After all, every 9th k value is divisible by 9, and if E only has one power of three, the GCD function will fail to produce all sorts of large factors of Mersenne numbers. If q=2*9*k*p+1, this implementation of P-1 would miss such a factor.

I would think E should be the product of all primes less than B1, all squares of primes less than the the square root of B1, all cubes of primes less than the cubic root of B1, etc.

Or am I way off here, missing something about the math?

When reading about P-1 factoring, K! was used instead which contains more than a sufficient number of powers of small primes.

If I am catching a missed opportunity here, then P-1 factoring for Mersenne numbers could be very substantially improved on using additional powers of the small primes. After all, numerous k values of real factors are divisible by 4, 8, 16, 32, 64, 128 or 9, 27, 81, or 25, 125, or 49, 121, 169, etc.

Last fiddled with by siegert81 on 2014-03-08 at 23:53
siegert81 is offline   Reply With Quote
Old 2014-03-09, 01:06   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts
Default

Quote:
Originally Posted by siegert81 View Post
Does Prime95 only use one power of each prime less than B1 when computing E? Or does it use numerous powers of 2,3,5,7,11,13 and all other very small primes?
For each prime, it uses the highest power of that prime that is not larger than B1.

Quote:
After all, every 9th k value is divisible by 9, and if E only has one power of three, the GCD function will fail to produce all sorts of large factors of Mersenne numbers. If q=2*9*k*p+1, this implementation of P-1 would miss such a factor.
But we don't see such misses. :-)

Quote:
I would think E should be the product of all primes less than B1, all squares of primes less than the the square root of B1, all cubes of primes less than the cubic root of B1, etc.
If you said "less than or equal to" or "not larger than" instead of "less than", that would be correct.

Quote:
Or am I way off here, missing something about the math?
No, you got it. The descriptions in "The Math" are not all perfect. :-(

You've found a documentation bug, or at least a nonclarity.

Quote:
If I am catching a missed opportunity here, then P-1 factoring for Mersenne numbers
would have been missing many, many factors because of that. That number of P-1 misses would have been at least partially discovered by now after so many years, because of ECM or further TF.

But in fact, the few missed factors that are occasionally discovered have been missed because of other problems, not because of insufficient prime-powering in Prime95's implementation of P-1.

Last fiddled with by cheesehead on 2014-03-09 at 01:14
cheesehead is offline   Reply With Quote
Old 2014-03-09, 05:04   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2×17×293 Posts
Default

Saying it differently, the described method guarantees that it searches all the "searching space" under B1, i.e. it will guarantee to find a factor q if q-1 is B1-power-smooth. Only talking about stage 1 here. Stage 2 is a different fish. Of course, you can use higher powers if you like, that would be a "shot in the dark", trying to find some factors "out of the searching space". It will be called an "extension" to the algorithm, and that is what Brent-Suyama extension is doing. You can do any type of "extensions" you like, but not all of them are worth a try, you can work in vain ages without finding a factor. Remark that you do not "extend" B1, by using larger powers, unless you do not add new primes to the exponent. Take a small example and try to do it practically.
LaurV is offline   Reply With Quote
Old 2014-03-09, 12:38   #4
siegert81
 
Dec 2010

2×37 Posts
Default

Quote:
No, you got it. The descriptions in "The Math" are not all perfect. :-(

You've found a documentation bug, or at least a nonclarity.
Thank you. I would have been quite surprised if GIMPS had been using only one power of the small primes.
siegert81 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring Question Rde Software 12 2009-06-12 22:38
Factoring Question AntonVrba Math 7 2006-08-30 07:15
Question about factoring 24737*2^991+1 VJS Factoring 56 2005-06-15 19:49
factoring question philmoore Factoring 8 2005-06-14 22:13
Trial factoring question ThomRuley Math 1 2004-02-26 21:43

All times are UTC. The time now is 20:13.


Sun May 22 20:13:23 UTC 2022 up 38 days, 18:14, 0 users, load averages: 2.33, 1.48, 1.26

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.

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