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).
Generate a random $m$-bit $x$.
If $x$ is a divisor of $N$, return $x$. If ~$x$ is a divisor of $N$, return ~$x$. (~$x$ is the complementary of $x$, basically flip every bit)
Otherwise go to Step 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 two absorbing barriers.
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$. We can probably run the random walk search directly for n - bit numbers, without the m - bit levelling (the algorithm can be improved).
Is this a feasible factorization algorithm? Could it be used to crack RSA in practice?
Sept. 2017. I found a fatal flaw in the mathematics long time ago (this is an older, edited question ). This particular algorithm is not efficient.