20211122, 11:32  #1 
"Juan Tutors"
Mar 2004
560_{10} Posts 
Have P1 nonsmooth factors ever found by accident?
While playing with the P1 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^E1 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^E1 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 nonsmooth 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 nonsmooth Mersenne factors been found via the P1 method due to the fact that 3^(2Ep)1 is large? or is the probability of finding a nonsmooth 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? 
20211122, 12:00  #2  
Jun 2003
1010011101111_{2} Posts 
Quote:
But for regular numbers, there is no special structure to the factor1, and so we rely on the basic smoothness only. 

20211122, 13:23  #3 
"Juan Tutors"
Mar 2004
230_{16} Posts 
Last fiddled with by JuanTutors on 20211122 at 13:24 
20211122, 14:26  #4 
Jun 2003
23×233 Posts 
Ok. Then, can you give an example where the size of 3^E1 mattered instead of the the smoothness of E?

20211122, 14:26  #5  
"Robert Gerbicz"
Oct 2005
Hungary
1567_{10} Posts 
Quote:
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 ? 

20211122, 14:39  #6 
Jun 2003
5359_{10} Posts 
Sure, I'm aware of this possibility. In this particular case, 3 == 394^59 (mod 1181), so we effectively did a proper P1 using based 394.
It is much more likely to work when we're working with toysized numbers. For practical P1, 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^E1 is just an artifact of dealing with /more/ numbers. 
20211122, 15:06  #7 
"Juan Tutors"
Mar 2004
2^{4}×5×7 Posts 
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 B1smooth are also factors of 3^E1. However, 3^E1 also has factors which are not B1smooth. Some of these non B1smooth factors are themselves products of B1smooth factors of 3^E1, and some are not. My question was, in the case of performing P1 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 20211122 at 15:08 
20211122, 15:15  #8  
"Robert Gerbicz"
Oct 2005
Hungary
1,567 Posts 
Quote:
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 

20211122, 15:23  #9 
"Vincent"
Apr 2010
Over the rainbow
2838_{10} Posts 
Brent  Suya extension anyone?

20211123, 00:35  #10 
"Juan Tutors"
Mar 2004
2^{4}·5·7 Posts 
Granted that the first case of a factor which is not B1smooth and has no B1smooth factors should be rare, I would think that this second case should happen occasionally. After all, if 2Jp+1 and 2Kp+1 are both B1smooth, then (2Jp+1)(2Kp+1)=2p(2JKp+J+K)+1 is unlikely to be B1smooth. If the probability of finding one factor that is B1smooth is about 2%, while recognizing that factors are not evenly distributed, we should occasionally come across a Mersenne number that has two B1smooth factors.
Last fiddled with by JuanTutors on 20211123 at 00:41 
20220109, 15:16  #11 
Romulan Interpreter
"name field"
Jun 2011
Thailand
7·1,423 Posts 
There are many cases of double and triple factors like that (i.e. composite P1 factors), we find them monthly or weekly. Last one here. We don't know of any prime factor like that (except BrentSuyama factors).
Last fiddled with by LaurV on 20220109 at 15:28 
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 Mersennearies  14  20210412 13:12 
Factors found before ECM starts  MisterBitcoin  YAFU  1  20180810 16:58 
How are such big factors found? (M1193)  heliosh  PrimeNet  7  20180124 16:54 
No factors found  aketilander  PrimeNet  9  20110517 11:32 
Fermat 12 factors already found?  UberNumberGeek  Factoring  6  20090617 17:22 