Factorization of Mersenne Numbers as a Constrained Optimization Problem
 

An illustration of the factorization of Mersenne numbers as a constrained optimization problem is given for
[I]M[/I][SUB]11[/SUB]=2[SUP]11[/SUP]-1=2047=11111111111[SUB]2[/SUB] with BitLength[[I]M[/I][SUB]11[/SUB]]=11.
One has to start with an assumption about the number of bits necessary to represent a prospective factor [I]a[/I].
Let's assume that BitLength[[I]a[/I]]=5. Therefore, [I]M[/I][SUB]11[/SUB] = [I]ab[/I] and BitLength[[I]b[/I]]=11-5+1=7.
In polynomial form,
[I]x[/I][SUP]10[/SUP]+[I]x[/I][SUP]9[/SUP]+[I]x[/I][SUP]8[/SUP]+[I]x[/I][SUP]7[/SUP]+[I]x[/I][SUP]6[/SUP]+[I]x[/I][SUP]5[/SUP]+[I]x[/I][SUP]4[/SUP]+[I]x[/I][SUP]3[/SUP]+[I]x[/I][SUP]2[/SUP]+[I]x[/I]+1 = ([I]x[/I][SUP]4[/SUP]+[I]a[/I][SUB]3[/SUB][I]x[/I][SUP]3[/SUP]+[I]a[/I][SUB]2[/SUB][I]x[/I][SUP]2[/SUP]+[I]a[/I][SUB]1[/SUB][I]x[/I]+1)([I]x[/I][SUP]6[/SUP]+[I]b[/I][SUB]5[/SUB][I]x[/I][SUP]5[/SUP]+[I]b[/I][SUB]4[/SUB][I]x[/I][SUP]4[/SUP]+[I]b[/I][SUB]3[/SUB][I]x[/I][SUP]3[/SUP]+[I]b[/I][SUB]2[/SUB][I]x[/I][SUP]2[/SUP]+[I]b[/I][SUB]1[/SUB][I]x[/I]+1),
and the binary vectors are [B][I]a[/I][/B]=(1,[I]a[/I][SUB]3[/SUB],[I]a[/I][SUB]2[/SUB],[I]a[/I][SUB]1[/SUB],1) and [B][I]b[/I][/B]=(1,[I]b[/I][SUB]5[/SUB],[I]b[/I][SUB]4[/SUB],[I]b[/I][SUB]3[/SUB],[I]b[/I][SUB]2[/SUB],[I]b[/I][SUB]1[/SUB],1) where 0≤[I]a[/I][SUB]3[/SUB]+[I]b[/I][SUB]5[/SUB]≤1 and [I]a[/I][SUB]1[/SUB]+[I]b[/I][SUB]1[/SUB]=1.
The expansion of the polynomial product gives
[I]x[/I][SUP]10[/SUP]+[I]x[/I][SUP]9[/SUP]+[I]x[/I][SUP]8[/SUP]+[I]x[/I][SUP]7[/SUP]+[I]x[/I][SUP]6[/SUP]+[I]x[/I][SUP]5[/SUP]+[I]x[/I][SUP]4[/SUP]+[I]x[/I][SUP]3[/SUP]+[I]x[/I][SUP]2[/SUP]+[I]x[/I]+1 = [I]x[/I][SUP]10[/SUP]+([I]a[/I][SUB]3[/SUB]+[I]b[/I][SUB]5[/SUB])[I]x[/I][SUP]9[/SUP]+([I]b[/I][SUB]4[/SUB]+[I]a[/I][SUB]3[/SUB][I]b[/I][SUB]5[/SUB]+[I]a[/I][SUB]2[/SUB])[I]x[/I][SUP]8[/SUP]+([I]b[/I][SUB]3[/SUB]+[I]a[/I][SUB]3[/SUB][I]b[/I][SUB]4[/SUB]+[I]a[/I][SUB]2[/SUB][I]b[/I][SUB]5[/SUB]+[I]a[/I][SUB]1[/SUB])[I]x[/I][SUP]7[/SUP]+([I]b[/I][SUB]2[/SUB]+[I]a[/I][SUB]3[/SUB][I]b[/I][SUB]3[/SUB]+[I]a[/I][SUB]2[/SUB][I]b[/I][SUB]4[/SUB]+[I]a[/I][SUB]1[/SUB][I]b[/I][SUB]5[/SUB]+1)[I]x[/I][SUP]6[/SUP]+([I]b[/I][SUB]1[/SUB]+[I]a[/I][SUB]3[/SUB][I]b[/I][SUB]2[/SUB]+[I]a[/I][SUB]2[/SUB][I]b[/I][SUB]3[/SUB]+[I]a[/I][SUB]1[/SUB][I]b[/I][SUB]4[/SUB]+[I]b[/I][SUB]5[/SUB])[I]x[/I][SUP]5[/SUP]+(1+[I]a[/I][SUB]3[/SUB][I]b[/I][SUB]1[/SUB]+[I]a[/I][SUB]2[/SUB][I]b[/I][SUB]2[/SUB]+[I]a[/I][SUB]1[/SUB][I]b[/I][SUB]3[/SUB]+[I]b[/I][SUB]4[/SUB])[I]x[/I][SUP]4[/SUP]+([I]a[/I][SUB]3[/SUB]+[I]a[/I][SUB]2[/SUB][I]b[/I][SUB]1[/SUB]+[I]a[/I][SUB]1[/SUB][I]b[/I][SUB]2[/SUB]+[I]b[/I][SUB]3[/SUB])[I]x[/I][SUP]3[/SUP]+([I]a[/I][SUB]2[/SUB]+[I]a[/I][SUB]1[/SUB][I]b[/I][SUB]1[/SUB]+[I]b[/I][SUB]2[/SUB])[I]x[/I][SUP]2[/SUP]+([I]a[/I][SUB]1[/SUB]+[I]b[/I][SUB]1[/SUB])[I]x[/I]+1
An implementation in Wolfram code
[code]FindInstance[
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 + ca1*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 && 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][/code]
gives the following result:
[code]{{ca3 -> 0, ca2 -> 1, ca1 -> 1, cb5 -> 0, cb4 -> 1, cb3 -> 1, cb2 -> 0, cb1 -> 0}}[/code]
Thus [B][I]a[/I][/B]=(1,0,1,1,1), [I]a[/I] = 10111[SUB]2[/SUB] = 23, [B][I]b[/I][/B]=(1,0,1,1,0,0,1), [I]b[/I]=1011001[SUB]2[/SUB] = 89, and 23×89=2047=11111111111[SUB]2[/SUB].

And of course this is not a simplification of the problem, because it is a quadratic optimization problem using binary integers.
And I'd prefer this (known) form:

min{0 : x*y=n, x>=2, y>=2, x and y are integers},
it is feasible iff n is composite, and for composites it will give a non-trivial divisor of n [and with that you can factor n fully recursively].

The illustration in post #1 is not a simplification indeed.
The approach is to be further expanded in at least three directions as follows:
1) Addition of heuristic constraints (for example, [I]b[SUB]1[/SUB][/I]+[I]a[/I][SUB]3[/SUB][I]b[/I][SUB]2[/SUB]+[I]a[/I][SUB]2[/SUB][I]b[/I][SUB]3[/SUB]+[I]a[/I][SUB]1[/SUB][I]b[SUB]4[/SUB][/I]+[I]b[/I][SUB]5[/SUB]≤2, etc.);
2) Use of evolutionary computation and genetic algorithms, like GENOCOP for numerical optimization problems; and
3) Preparation of a quadratic function to be tried on a quantum annealing computer like D-Wave Systems.

[QUOTE=Dobri;603748]3) Preparation of a quadratic function to be tried on a quantum annealing computer like D-Wave Systems.[/QUOTE]

On quantum computer we already have the polynomial time factorization Shor's algorithm.
I'd say it is quite unlikely that the quad binary approach would be in polynomial time using quantum [because the above form is from ancient].

Shor's algorithm can be implemented on quantum computers like IBM Quantum where the problem is the limited number of qubits and the noise.
Quantum annealing is kind of pseudo-quantum computing for solving optimization problems having the advantage of the utilization of large matrix qubit configurations.
There are several works on integer factorization using D-Wave Systems but not much is known about the efficiency of factoring Mersenne numbers.
A short video that illustrates the classical idea for such optimizations is available at [URL]https://www.youtube.com/watch?v=dAyDi1aa40E[/URL].

Below is a more compact Wolfram code which allows one to enter the bit length [I]Mbl[/I] of the Mersenne number and the bit length [I]Fbl[/I] of the prospective factor.
For this second illustration, [I]M[/I][SUB]29[/SUB]=2[SUP]29[/SUP]-1=536870911=11111111111111111111111111111[SUB]2[/SUB] is chosen ([I]Mbl[/I]=29) and it is assumed that the bit length of the prospective factor is [I]Fbl[/I]=11.
[code]
Mbl = 29; Fbl = 11;
FindInstance[(2^(Fbl - 1) + 1 +
Sum[Boole[ca[i]]*2^i, {i, 1, Fbl - 2, 1}])*(2^(Mbl - Fbl) + 1 +
Sum[Boole[cb[i]]*2^i, {i, 1, Mbl - Fbl - 1, 1}]) == 2^Mbl - 1 &&
Boole[ca[Fbl - 2]] + Boole[cb[Mbl - Fbl - 1]] <= 1 &&
Boole[ca[1]] + Boole[cb[1]] == 1, {Sequence @@
Array[ca, {Fbl - 2}, {1}],
Sequence @@ Array[cb, {Mbl - Fbl - 1}, {1}]}, Booleans]
[/code]The output is in Boolean format, True (1) or False (0).
[code]
{{ca[1] -> True, ca[2] -> True, ca[3] -> True, ca[4] -> False,
ca[5] -> False, ca[6] -> True, ca[7] -> False, ca[8] -> False,
ca[9] -> False, cb[1] -> False, cb[2] -> False, cb[3] -> False,
cb[4] -> True, cb[5] -> False, cb[6] -> True, cb[7] -> False,
cb[8] -> True, cb[9] -> False, cb[10] -> True, cb[11] -> True,
cb[12] -> False, cb[13] -> True, cb[14] -> True, cb[15] -> False,
cb[16] -> True, cb[17] -> True}}
[/code]The obtained factor is 10001001111[SUB]2[/SUB]=1103.

In this third illustration, the optimization is only over the unknown bits of the binary vector [B][I]a[/I][/B]=(1,[I]a[/I][SUB]Fbl-2[/SUB],...,[I]a[/I][SUB]1[/SUB],1).
The Mersenne number [I]M[/I][SUB]1249[/SUB]=2[SUP]1249[/SUP]-1 is chosen ([I]Mbl[/I]=1249) and it is assumed that the bit length of the prospective factor is [I]Fbl[/I]=26.
The simplified Wolfram code
[code]
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]
[/code]
gives the following result:
[code]
{{ca[1] -> False, ca[2] -> False, ca[3] -> False, ca[4] -> False, ca[5] -> False, ca[6] -> True, ca[7] -> True, ca[8] -> True, ca[9] -> True, ca[10] -> False, ca[11] -> True, ca[12] -> False, ca[13] -> True, ca[14] -> True, ca[15] -> True, ca[16] -> False, ca[17] -> True, ca[18] -> True, ca[19] -> True, ca[20] -> True, ca[21] -> False, ca[22] -> False, ca[23] -> False, ca[24] -> True}}
[/code]
The obtained factor is 11000111101110101111000001[SUB]2[/SUB]=52358081.

Please use your method on M1277 and let us know what the factor is.

[QUOTE=VBCurtis;603882]Please use your method on M1277 and let us know what the factor is.[/QUOTE]
I am working on it indeed. It is a work in progress involving a combination of constrained optimization with empirical constraints and heuristic sieves.

[QUOTE=Dobri;603880]In this third illustration, the optimization is only over the unknown bits of the binary vector [B][I]a[/I][/B]=(1,[I]a[/I][SUB]Fbl-2[/SUB],...,[I]a[/I][SUB]1[/SUB],1).
The Mersenne number [I]M[/I][SUB]1249[/SUB]=2[SUP]1249[/SUP]-1 is chosen ([I]Mbl[/I]=1249) and it is assumed that the bit length of the prospective factor is [I]Fbl[/I]=26.
The simplified Wolfram code
[code]
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]
[/code]
gives the following result:
[code]
{{ca[1] -> False, ca[2] -> False, ca[3] -> False, ca[4] -> False, ca[5] -> False, ca[6] -> True, ca[7] -> True, ca[8] -> True, ca[9] -> True, ca[10] -> False, ca[11] -> True, ca[12] -> False, ca[13] -> True, ca[14] -> True, ca[15] -> True, ca[16] -> False, ca[17] -> True, ca[18] -> True, ca[19] -> True, ca[20] -> True, ca[21] -> False, ca[22] -> False, ca[23] -> False, ca[24] -> True}}
[/code]
The obtained factor is 11000111101110101111000001[SUB]2[/SUB]=52358081.[/QUOTE]Just out of curiosity, how long did your program take to find that factor?

I ran a completely mindless Pari-GP script to look for small factors 2*k*1249 + 1 of 2^1249 - 1 for k <= 1000000. It quickly found 3 small factors (one of which was smaller than the one your program found). I then checked the cofactor, and it tested composite.[code]? forstep(i=6*1249+1,2000000*1249+1,[2*1249,6*1249],r=Mod(2,i)^1249-1;if(r==0,print(i)))
97423
52358081
2379005273
? n=(2^1249-1)/97423/52358081/2379005273;ispseudoprime(n)
%4 = 0[/code]

I note that for M1277, your bit length would have to exceed the current TF limit in order to have any chance of turning up a factor. That could increase your program's run time somewhat.

I suggest you try a bit length of 426. If there is no factor that length or smaller, you will at least have shown that M1277 is a P[sub]2[/sub].

[QUOTE=Dr Sardonicus;603904]Just out of curiosity, how long did your program take to find that factor?[/QUOTE]
The result was obtained for approximately one hour while running the Wolfram code in interpreter mode on a Raspberry Pi 4B device for which Wolfram Mathematica is available for free. Compiling the code segment would make it run much faster.
The increase of the bit length increases the computation time exponentially if no additional constraints are stated.
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.

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

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

Good luck. :smile:

[QUOTE=Dobri;603880][code]
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]
[/code][/QUOTE]

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.

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.
[code]
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]
[/code]
[code]{{ca3 -> 0, ca2 -> 1, ca1 -> 1, cb5 -> 0, cb4 -> 1, cb3 -> 1, cb2 -> 0, cb1 -> 0}}[/code]
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.
[code]
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]
[/code]
[code]ca3 == 0 && ca2 == 1 && ca1 == 1 && cb5 == 0 && cb4 == 1 && cb3 == 1 && cb2 == 0 && cb1 == 0[/code]
Therefore, the introduction of the vector [B][I]b[/I][/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.

[QUOTE=Dobri;603920]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.[/QUOTE]

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

[QUOTE=Dobri;603905]<snip>
The increase of the bit length increases the computation time exponentially if no additional constraints are stated.[/quote]Exponentially? Uh-oh, trouble![quote]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.[/QUOTE]:confused2:

I have absolutely no idea what "empirical bit patterns" for an [b]unknown[/b] factor could [i]possibly[/i] mean.

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

The OP is trying to drink whiskey from a bottle of wine.
[QUOTE="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[/QUOTE]