3 of 6
rath
• 2426
• 2
• 20
• 38

# 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?