Factorization of Mersenne Numbers as a Constrained Optimization Problem

[Dobri]

An illustration of the factorization of Mersenne numbers as a constrained optimization problem is given for
M₁₁=2¹¹-1=2047=11111111111₂ with BitLength[M₁₁]=11.
One has to start with an assumption about the number of bits necessary to represent a prospective factor a.
Let's assume that BitLength[a]=5. Therefore, M₁₁ = ab and BitLength[b]=11-5+1=7.
In polynomial form,
x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1 = (x⁴+a₃x³+a₂x²+a₁x+1)(x⁶+b₅x⁵+b₄x⁴+b₃x³+b₂x²+b₁x+1),
and the binary vectors are a=(1,a₃,a₂,a₁,1) and b=(1,b₅,b₄,b₃,b₂,b₁,1) where 0≤a₃+b₅≤1 and a₁+b₁=1.
The expansion of the polynomial product gives
x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1 = x¹⁰+(a₃+b₅)x⁹+(b₄+a₃b₅+a₂)x⁸+(b₃+a₃b₄+a₂b₅+a₁)x⁷+(b₂+a₃b₃+a₂b₄+a₁b₅+1)x⁶+(b₁+a₃b₂+a₂b₃+a₁b₄+b₅)x⁵+(1+a₃b₁+a₂b₂+a₁b₃+b₄)x⁴+(a₃+a₂b₁+a₁b₂+b₃)x³+(a₂+a₁b₁+b₂)x²+(a₁+b₁)x+1
An implementation in Wolfram 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]

gives the following result:

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

Thus a=(1,0,1,1,1), a = 10111₂ = 23, b=(1,0,1,1,0,0,1), b=1011001₂ = 89, and 23×89=2047=11111111111₂.

[R. Gerbicz]

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

[Dobri]

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, b₁+a₃b₂+a₂b₃+a₁b₄+b₅≤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.

[R. Gerbicz]

Originally Posted by Dobri

3) Preparation of a quadratic function to be tried on a quantum annealing computer like D-Wave Systems.

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

[Dobri]

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 https://www.youtube.com/watch?v=dAyDi1aa40E.

[Dobri]

Below is a more compact Wolfram code which allows one to enter the bit length Mbl of the Mersenne number and the bit length Fbl of the prospective factor.
For this second illustration, M₂₉=2²⁹-1=536870911=11111111111111111111111111111₂ is chosen (Mbl=29) and it is assumed that the bit length of the prospective factor is Fbl=11.

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]

The output is in Boolean format, True (1) or False (0).

{{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}}

The obtained factor is 10001001111₂=1103.

[Dobri]

In this third illustration, the optimization is only over the unknown bits of the binary vector a=(1,a_Fbl-2,...,a₁,1).
The Mersenne number M₁₂₄₉=2¹²⁴⁹-1 is chosen (Mbl=1249) and it is assumed that the bit length of the prospective factor is Fbl=26.
The simplified Wolfram 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]

gives the following result:

{{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}}

The obtained factor is 11000111101110101111000001₂=52358081.

[VBCurtis]

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

[Dobri]

Originally Posted by VBCurtis

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

I am working on it indeed. It is a work in progress involving a combination of constrained optimization with empirical constraints and heuristic sieves.

[Dr Sardonicus]

Originally Posted by Dobri

In this third illustration, the optimization is only over the unknown bits of the binary vector a=(1,a_Fbl-2,...,a₁,1).
The Mersenne number M₁₂₄₉=2¹²⁴⁹-1 is chosen (Mbl=1249) and it is assumed that the bit length of the prospective factor is Fbl=26.
The simplified Wolfram 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]

gives the following result:

{{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}}

The obtained factor is 11000111101110101111000001₂=52358081.

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.

? 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

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

[Dobri]

Originally Posted by Dr Sardonicus

Just out of curiosity, how long did your program take to find that factor?

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.