mersenneforum.org > Math Have P-1 non-smooth factors ever found by accident?
 Register FAQ Search Today's Posts Mark Forums Read

 2021-11-22, 11:32 #1 JuanTutors     "Juan Tutors" Mar 2004 23016 Posts 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?
2021-11-22, 12:00   #2
axn

Jun 2003

10100100100012 Posts

Quote:
 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.

2021-11-22, 13:23   #3
JuanTutors

"Juan Tutors"
Mar 2004

24×5×7 Posts

Quote:
 Originally Posted by axn 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

 2021-11-22, 14:26 #4 axn     Jun 2003 34·5·13 Posts Ok. Then, can you give an example where the size of 3^E-1 mattered instead of the the smoothness of E?
2021-11-22, 14:26   #5
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101111110112 Posts

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

 2021-11-22, 14:39 #6 axn     Jun 2003 526510 Posts 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.
 2021-11-22, 15:06 #7 JuanTutors     "Juan Tutors" Mar 2004 56010 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 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
2021-11-22, 15:15   #8
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

27738 Posts

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

 2021-11-22, 15:23 #9 firejuggler     "Vincent" Apr 2010 Over the rainbow 13·211 Posts Brent - Suya extension anyone?
 2021-11-23, 00:35 #10 JuanTutors     "Juan Tutors" Mar 2004 24·5·7 Posts 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
 2022-01-09, 15:16 #11 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 268416 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Kalli Hofmann Marin's Mersenne-aries 14 2021-04-12 13:12 MisterBitcoin YAFU 1 2018-08-10 16:58 heliosh PrimeNet 7 2018-01-24 16:54 aketilander PrimeNet 9 2011-05-17 11:32 UberNumberGeek Factoring 6 2009-06-17 17:22

All times are UTC. The time now is 23:34.

Wed Jan 19 23:34:37 UTC 2022 up 180 days, 18:03, 0 users, load averages: 1.90, 1.44, 1.35