Can this help filter out k-values when trial factoring?

[neomacdev]

Hi,

I was writing out the expressions for Mersenne numbers with 2 factors, or 3 factors, etc...

2^p - 1 = (2*k1*p+1)*(2*k2*p+1)
2^p - 1 = (2*k1*p+1)*(2*k2*p+1)*(2*k3*p+1)
...

And thinking about different ways the expressions can be re-written.

2^p - 1 = 2^2*(k1*k2)*p^2 + 2*(k1 + k2)*p + 1
2^p - 1 = 2^3*(k1*k2*k3)*p^3 + 2^2*(k1*k2 + k1*k3 + k2*k3)*p^2 + 2^1*(k1 + k2 + k3)*p + 1
...

In thinking about this in combination with Fermat's Little theorem I realized that:

mod( ((2^(p-1)-1) / p ), p ) = mod( (sum of k-values for all prime factors of M(p) ), p )

Which I double-checked for numerous composite Mersenne numbers and it appears to always hold. (At least for the dozen or so fully-factored Mersenne numbers that I checked by hand.) For example:

mod( ((2^66-1)/67), (67) ) = mod( (1445580+5685360129), (67) ) = 10

Likewise it appears this holds for the sum of k-values that generate prime factors along with composite co-factors. For example, let p=113 then the k-values for the first 3 prime factors are 15+103+292 and the k-value for the remaining composite co-factor (product of last two prime factors) is 8820457042988551707.

mod( ((2^112-1)/113), (113) ) = mod( (15+103+292+8820457042988551707), (113) ) = 83

I'm wondering if this has been used to help filter out potential k-values from being tested as potential factors. Or if perhaps the same k-values this would eliminate is already equivalent to some other filter on the k-values. I haven't had time to dig deeply into this idea yet, just thought I'd post and see what comments were generated.

[Uncwilly]

Try it on 332194969. How does it workout?

[neomacdev]

Originally Posted by Uncwilly

Try it on 332194969. How does it workout?

I'm not sure if you're being serious or not. As I said above, I haven't really thought in depth about how to use the fact, but I can quickly verify it for this exponent.

According to the info at https://www.mersenne.ca/exponent/332194969 the first factor of 2^332194969-1 is 84169568075407, generated by a k-value of 126687.

mod( (2^332194968-1)/332194969, 332194969) = 169375608
WolframAlpha result

The k-value of the composite co-factor for the rest of 2^p-1 (besides the first prime factor) would be (((2^332194969-1)/(84169568075407))-1)/(2*332194969) which has over 100 million digits so I'll omit it or it'd be a long post. :-)

But I can compute the mod of the sum of the first k-value with the k-value for this composite co-factor, and verify it equals the value above. And it does.

mod( (126687 + (((2^332194969-1)/(84169568075407))-1)/(2*332194969)) , 332194969) = 169375608.
WolframAlpha result

[neomacdev]

Originally Posted by neomacdev

I realized that:

mod( ((2^(p-1)-1) / p ), p ) = mod( (sum of k-values for all prime factors of M(p) ), p )

I'd love to know if this is a "known fact" -- as in it exists in published literature anywhere. If anyone has seen anything written about this, please let me know and if you are able to provide a citation/reference/link that'd be great. Thank you.

[Uncwilly]

Originally Posted by neomacdev

The k-value of the composite co-factor for the rest of 2^p-1 (besides the first prime factor) would be (((2^332194969-1)/(84169568075407))-1)/(2*332194969) which has over 100 million digits so I'll omit it or it'd be a long post. :-)

Knowing the k for for that is of what real value? How does it help us find factors or prove primality?
How do you know that the cofactor is composite?