3 of 6
texified, removed clutter, made more concise and added relevant tag

Is it possible to attack RSA with a WalkSat derivative?

We consider a large $n$-bit number $N$. We want to find a factor, if it admits any.

For $m$ taking values from $1$ to $n$, perform the following three steps (actually, for each $m$, perform many cycles, as described below).

  1. Generate a random $m$-bit $x$.

  2. If $x$ is a divisor of $N$, return $x$. Otherwise go to Step 3.

  3. Choose a random bit $x_i$ and flip its value. Repeat Steps 2 and 3 for $t * m^2$ cycles, if necessary (where t is a fixed number).

This algorithm runs for a total of $C * n^3$ cycles (where the constant $C$ can be determined), and it either finds a divisor of $N$, or else says that $N$ is prime.

The probability of reporting a false prime will be as small as we want, as we have a random walk with one absorbing barrier and one reflecting barrier.

This is basically a WalkSat - type algorithm, and we define the Hamming distance and the random walk on the space of $m$-bit binary strings, where $m$ takes values from $1$ to $n$.

Is this a feasible factorization algorithm? Could it be used to crack RSA in practice?