mersenneforum.org > Math Brent-Suyama extension of P-1 factoring
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2009-08-23, 12:18 #1 S485122     "Jacob" Sep 2006 Brussels, Belgium 1,777 Posts Brent-Suyama extension of P-1 factoring The Brent-Suyama extension of P-1 factoring DOES find factors ;-) I stumbled upon this when looking the last factor I found by P-1 factoring : [Sun Aug 23 03:49:05 2009] P-1 found a factor in stage #2, B1=540000, B2=18225000. UID: S485122/Q67-P3, M21909863 has a factor: 5349424617695409539087 The 73 bits factor 5349424617695409539087 = 2 x 1069 x 2269 x 21909863 x 50329801 + 1 The 50329801 factor of q-1 is is about 2,76 times the B2 bound ! It must be the Brent-Suyama extension doing its work. I then looked through my previous factors found and stumbled upon this : [Mon Nov 12 09:58:01 2007] P-1 found a factor in stage #2, B1=100000, B2=3000000. UID: S485122/Q67-P3, M2824333 has a factor: 89849066709690811889 67 bits factor 89849066709690811889 = 2^4 * 6481 * 306786091 * 2824333 + 1 The 306786091 factor of q-1 is more than 100 times the B2 bound !!! Those are the only cases I found in my results files where the largest factor of q-1 is bigger than the B2 bound, out of 930 P-1 factoring attempts with E=6 and 214 P-1 factoring attempts with E=12. What is the probability of the Brent-Sumaya extension of finding a factor during P-1 factoring of Mersenne numbers ? As a side note : am I right in thinking that there is no limit (except the number to factor of course ;-) to the factor that could be found with even a small B1 bound. For fun one could search for a (large) prime number q = 2 * Product( ki^j ) * p + 1 {ki < B1} that is factor of 2^p - 1. It would be reversing the search : start with the factor and find the corresponding Mersenne number. Each number to check does no imply much work : check if q is congruent to 1 or 7 mod 8, check if it is prime and then check if it divides 2^p - 1 for different values of p. Of course the searching algorithm is still to be written. Perhaps that last paragraph should be in the puzzles (or Misc Math) sub-forum. Jacob
 2009-08-23, 15:21 #2 MatWur-S530113     Apr 2007 Spessart/Germany 101000102 Posts Hello, you can find some notes on the Brent-Suyama extension in the Readme file of GMP-ECM, but I don't know anything about the increasing of the chance to find a factor, too. Of course it is true: if q divides 2^p-1 then 2p divides q-1. But this statement is true for other bases, too: f.e.: if q divides 5^p-1 then 2p divides q-1. Thus if you sieve out the primes q congruent 1 mod 2p you have 2 problems: 1) is it the correct exponent p or is another prime p' (which divides q-1, too) the correct exponent? 2) if p is the correct exponent which base is the correct one? and another problem: is there always a base b and a prime p that q==1 mod 2p divides b^p-1 ? And reducing this problems to Mersenne numbers only results in a slow kind of trial factoring the Mersenne number. I know it because I tried to find an 80-digit factor this way... of course without success ;-) best regards, Matthias

 Similar Threads Thread Thread Starter Forum Replies Last Post chris2be8 Factoring 446 2020-04-29 17:08 LaurV Data 9 2019-04-14 00:13 vsuite GPU Computing 7 2017-07-10 20:45 siegert81 Math 2 2014-11-23 21:12 bsquared Factoring 9 2007-05-18 19:24

All times are UTC. The time now is 06:01.

Fri Jan 28 06:01:54 UTC 2022 up 189 days, 30 mins, 2 users, load averages: 1.61, 1.50, 1.50

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.

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