mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-11-22, 11:32   #1
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

24×5×7 Posts
Default Have P-1 non-smooth factors ever found by accident?

While playing with the P-1 test for a presentation (having nothing to do with Mersenne primes), I noticed that a great deal of large numbers had common factors with 3^E-1 using B1=10. After playing with the factors for a while, I realized that the larger the number was, the more likely that these factors were due to the fact that 3^E-1 is large (1202 digits), more than the fact that the exponent is divisible by E=(2^3)(3^2)(5)(7). In other words, I found a great amount of non-smooth factors of large numbers this way. The obvious reason is that the pattern of numbers with factors in common with E repeats, while as an integer variable grows, it gains access to more potential prime factors.

This got me wondering, have any non-smooth Mersenne factors been found via the P-1 method due to the fact that 3^(2Ep)-1 is large? or is the probability of finding a non-smooth common factor of 3^(2Ep)-1 and Mp just too low?

I guess an additional question is, might the algorithm be more productive if we start with a larger base, closer to k=(Mp)/2, since such a power would have about 2Ep*log(k) digits?
JuanTutors is offline   Reply With Quote
Old 2021-11-22, 12:00   #2
axn
 
axn's Avatar
 
Jun 2003

10100100110102 Posts
Default

Quote:
Originally Posted by JuanTutors View Post
After playing with the factors for a while, I realized that the larger the number was, the more likely that these factors were due to the fact that 3^E-1 is large (1202 digits), more than the fact that the exponent is divisible by E=(2^3)(3^2)(5)(7).
I suspect that you haven't quite understood how P-1 works. P-1 only cares for the smoothness of the (unknown factor minus 1). It just so happens that, for mersenne primes, the (factor-1) has a special structure which is divisible by the mersenne exponent. This special property holds for some other special numbers as well like (Generalized) Fermat Numbers, (Generalized) Rep Units, Fibonacci/Lucas numbers, etc. Since we know that numbers of these forms have f-1 divisible by the exponent, we can throw that in in 3^(E*N)-1.

But for regular numbers, there is no special structure to the factor-1, and so we rely on the basic smoothness only.
axn is online now   Reply With Quote
Old 2021-11-22, 13:23   #3
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

10001100002 Posts
Default

Quote:
Originally Posted by axn View Post
I suspect that you haven't quite understood how P-1 works.
I do.

Last fiddled with by JuanTutors on 2021-11-22 at 13:24
JuanTutors is offline   Reply With Quote
Old 2021-11-22, 14:26   #4
axn
 
axn's Avatar
 
Jun 2003

2·32·293 Posts
Default

Ok. Then, can you give an example where the size of 3^E-1 mattered instead of the the smoothness of E?
axn is online now   Reply With Quote
Old 2021-11-22, 14:26   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts
Default

Quote:
Originally Posted by axn View Post
I suspect that you haven't quite understood how P-1 works. P-1 only cares for the smoothness of the (unknown factor minus 1).
The OP's question is still valid, you can really find a factor for that p-1 is not smooth, beyond the B1 limit (with ofcourse excluding here the special factors for special numbers). Example:
use base=3 and B1=10 with the standard exponent=2^3*3^2*5*7 and you can factor n=1177457, finding the factor 1181=1+2^2*5*59:
Code:
? n=1177457;gcd(lift(Mod(3,n)^(8*9*5*7)-1),n)
%14 = 1181
? factor(1180)
%15 = 
[ 2 2]

[ 5 1]

[59 1]

? factor(n) 
%16 = 
[ 997 1]

[1181 1]

? 
? znorder(Mod(3,1181))
%17 = 20
?
What happens here and in other cases: you need a very big luck, if q|p-1 then you have 1/q chance that for a random base znorder(Mod(b,q)) is not divisible by q. So if q>B1 you'd have 1/q chance to find this p factor (assuming other p-1 factors are <=B1).
R. Gerbicz is offline   Reply With Quote
Old 2021-11-22, 14:39   #6
axn
 
axn's Avatar
 
Jun 2003

2×32×293 Posts
Default

Sure, I'm aware of this possibility. In this particular case, 3 == 394^59 (mod 1181), so we effectively did a proper P-1 using based 394.

It is much more likely to work when we're working with toy-sized numbers. For practical P-1, basically, there is no way to work this into a proper algorithm that will help us improve the odds while still maintaining same runtime. Simpler to just increase B1 and/or B2.

I guess OP's observation of this happening with larger 3^E-1 is just an artifact of dealing with /more/ numbers.
axn is online now   Reply With Quote
Old 2021-11-22, 15:06   #7
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

10608 Posts
Default

To clarify, I was curious as to whether such a factor has been found, not whether it is possible. In addition, I asked this question as a personal query, not in an effort to prove or disprove something. Letting B1=10, all numbers relatively prime to E which are B1-smooth are also factors of 3^E-1. However, 3^E-1 also has factors which are not B1-smooth. Some of these non B1-smooth factors are themselves products of B1-smooth factors of 3^E-1, and some are not. My question was, in the case of performing P-1 factorization of large Mersenne numbers, whether any such factors have been found.

//EDIT: I see that as I was typing, R. Gerbicz stated essentially what I mentioned.

Last fiddled with by JuanTutors on 2021-11-22 at 15:08
JuanTutors is offline   Reply With Quote
Old 2021-11-22, 15:15   #8
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts
Default

Quote:
Originally Posted by axn View Post
It is much more likely to work when we're working with toy-sized numbers. For practical P-1, basically, there is no way to work this into a proper algorithm that will help us improve the odds while still maintaining same runtime. Simpler to just increase B1 and/or B2.
Yes, it is pure luck, basically you have something 1/(B1*log(B1)) probability to see this lucky find (in this calc we don't assume that there is exactly one prime factor>B1).

Another type of example: use the same base, B1, exponent, but for n=2944901
Code:
? n=2944901;gcd(lift(Mod(3,n)^(8*9*5*7)-1),n)
%33 = 4201
we have found 4201 as a (prime) divisor, but here 4200=2^3*3*5^2*7, all prime factors are in the B1 limit, but we haven't included 5^2 only 5 in the exponent, we had luck (what we could see with 1/5 probability).
R. Gerbicz is offline   Reply With Quote
Old 2021-11-22, 15:23   #9
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

2×53×11 Posts
Default

Brent - Suya extension anyone?
firejuggler is offline   Reply With Quote
Old 2021-11-23, 00:35   #10
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

56010 Posts
Default

Granted that the first case of a factor which is not B1-smooth and has no B1-smooth factors should be rare, I would think that this second case should happen occasionally. After all, if 2Jp+1 and 2Kp+1 are both B1-smooth, then (2Jp+1)(2Kp+1)=2p(2JKp+J+K)+1 is unlikely to be B1-smooth. If the probability of finding one factor that is B1-smooth is about 2%, while recognizing that factors are not evenly distributed, we should occasionally come across a Mersenne number that has two B1-smooth factors.

Last fiddled with by JuanTutors on 2021-11-23 at 00:41
JuanTutors is offline   Reply With Quote
Old 2022-01-09, 15:16   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

71·139 Posts
Default

There are many cases of double and triple factors like that (i.e. composite P-1 factors), we find them monthly or weekly. Last one here. We don't know of any prime factor like that (except Brent-Suyama factors).

Last fiddled with by LaurV on 2022-01-09 at 15:28
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Nearly all Factors up to 2^71 found between 2.86 G and 2.96 G Kalli Hofmann Marin's Mersenne-aries 14 2021-04-12 13:12
Factors found before ECM starts MisterBitcoin YAFU 1 2018-08-10 16:58
How are such big factors found? (M1193) heliosh PrimeNet 7 2018-01-24 16:54
No factors found aketilander PrimeNet 9 2011-05-17 11:32
Fermat 12 factors already found? UberNumberGeek Factoring 6 2009-06-17 17:22

All times are UTC. The time now is 03:42.


Mon Jan 24 03:42:27 UTC 2022 up 184 days, 22:11, 0 users, load averages: 1.21, 1.25, 1.27

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.

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