Factorization of Mersenne Numbers as a Constrained Optimization Problem

[a1call]

In case you do find a factor, you might want to read this tread before publishing the factors:

https://mersenneforum.org/showthread.php?t=24775

Good luck.

[charybdis]

Originally Posted by Dobri

p = 1249; Mn = 2^p - 1;
Mbl = p; Fbl = 26;
FindInstance[
 Mod[Mn, FromDigits[Boole[Reverse[Join[{True}, 
 {Sequence @@ Array[ca, {Fbl - 2}, {1}]}, {True}]]], 2]] == 0, 
 {Sequence @@ Array[ca, {Fbl - 2}, {1}]}, Booleans]

This looks like extremely inefficient trial division. If there is some clever way to find factors by optimization - which I highly doubt - FindInstance isn't going to magically discover it.

[Dobri]

The Wolfram function FindInstance is used merely as an illustration.
The intended discussion in this thread is on the framework for prospective utilization of additional empirical constraints.
Let's consider the illustration in post #1 in some more detail.
If the numerical values of the convolution sums for each polynomial term were known, the problem could be reduced to finding the solution of a system of equations.

Solve[ca3 + cb5 == 0 &&
  cb4 + ca3*cb5 + ca2 == 2 &&
  cb3 + ca3*cb4 + ca2*cb5 + ca1 == 2 && 
  cb2 + ca3*cb3 + ca2*cb4 + ca1*cb5 + 1 == 2 && 
  cb1 + ca3*cb2 + ca2*cb3 + ca1*cb4 + cb5 == 2 && 
  1 + ca3*cb1 + ca2*cb2 + ca1*cb3 + cb4 == 3 && 
  ca3 + ca2*cb1 + ca1*cb2 + cb3 == 1 &&
  ca2 + ca1*cb1 + cb2 == 1 &&
  ca1 + cb1 == 1,
 {ca3, ca2, ca1, cb5, cb4, cb3, cb2, cb1}, NonNegativeIntegers]

{{ca3 -> 0, ca2 -> 1, ca1 -> 1, cb5 -> 0, cb4 -> 1, cb3 -> 1, cb2 -> 0, cb1 -> 0}}

Apparently, said numerical values are unknown but one could use empirical constraints to narrow the scope of work one way or another in an attempt to reduce the computation time.

Reduce[2^10 + (ca3 + cb5)*2^9 + (cb4 + ca3*cb5 + ca2)*2^8 + (cb3 + ca3*cb4 + ca2*cb5 + ca1)*2^7 + (cb2 + ca3*cb3 + ca2*cb4 + a1*cb5 + 1)*2^6 + (cb1 + ca3*cb2 + ca2*cb3 + ca1*cb4 + cb5)*2^5 + (1 + ca3*cb1 + ca2*cb2 + ca1*cb3 + cb4)*2^4 + (ca3 + ca2*cb1 + ca1*cb2 + cb3)*2^3 + (ca2 + ca1*cb1 + cb2)*2^2 + (ca1 + cb1)*2 + 1 == 2^11 - 1 && 
  ca3 + cb5 <= 1 &&
  cb4 + ca3*cb5 + ca2 <= 2 &&
  cb3 + ca3*cb4 + ca2*cb5 + ca1 <= 2 &&
  b2 + ca3*cb3 + ca2*cb4 + ca1*cb5 + 1 <= 3 && 
  cb1 + ca3*cb2 + ca2*cb3 + ca1*cb4 + cb5 <= 3 && 
  1 + ca3*cb1 + ca2*cb2 + ca1*cb3 + cb4 <= 3 && 
  ca3 + ca2*cb1 + ca1*cb2 + cb3 <= 2 && 
  ca2 + ca1*cb1 + cb2 <= 2 && 
  ca1 + cb1 == 1 && 
  ca1 <= 1 && ca2 <= 1 && ca3 <= 1 && cb1 <= 1 && cb2 <= 1 && cb3 <= 1 && cb4 <= 1 && cb5 <= 1,
 {ca3, ca2, ca1, cb5, cb4, cb3, cb2, cb1}, NonNegativeIntegers]

ca3 == 0 && ca2 == 1 && ca1 == 1 && cb5 == 0 && cb4 == 1 && cb3 == 1 && cb2 == 0 && cb1 == 0

Therefore, the introduction of the vector b is not a simplification of the factorization problem but an extension of the standard framework to allow for additional numerical techniques from other fields to be tested.

[charybdis]

Originally Posted by Dobri

Let's consider the illustration in post #1 in some more detail.
If the numerical values of the convolution sums for each polynomial term were known, the problem could be reduced to finding the solution of a system of equations.

I can reduce the problem to finding the solution to a system of one equation: x*y = N. Why overcomplicate things?

[Dr Sardonicus]

Originally Posted by Dobri

<snip>
The increase of the bit length increases the computation time exponentially if no additional constraints are stated.

Exponentially? Uh-oh, trouble!

For example, one could put constraints on the number of consecutive zeros and ones, add empirical bit patterns, etc., in order to reduce the computation time for a prospective factor.

I have absolutely no idea what "empirical bit patterns" for an unknown factor could possibly mean.

One thing I can guarantee: the last three bits of any factor of M_p, p prime > 2, are either 111 or 001.

[Batalov]

The OP is trying to drink whiskey from a bottle of wine.

Originally Posted by E.John

You better get back, honky cat
Living in the city ain't where it's at
It's like trying to find gold in a silver mine
It's like trying to drink whiskey from a bottle of wine