Have P-1 non-smooth factors ever found by accident?

[JuanTutors]

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?

[axn]

Originally Posted by JuanTutors

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.

[JuanTutors]

Originally Posted by axn

I suspect that you haven't quite understood how P-1 works.

I do.

[axn]

Ok. Then, can you give an example where the size of 3^E-1 mattered instead of the the smoothness of E?

[R. Gerbicz]

Originally Posted by axn

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:

? 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).

[axn]

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.

[JuanTutors]

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.

[R. Gerbicz]

Originally Posted by axn

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

? 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).

[firejuggler]

Brent - Suya extension anyone?

[JuanTutors]

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.

[LaurV]

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).