# Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors?

Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors? For example, suppose we have $n = p * q = 167653$; in this case, $p = 359 = 101100111_2$ and $q = 467 = 111010011_2$ are related by the bit-permutation $K = (2 4) (5 7)$. If $K$ is known, can $n$ be factored in polynomial time?

-
If I understand bit-permutations correctly, this means that $p$ and $q$ have the same number of $0$'s and $1$'s in their binary representations? Should we assume the two factors are the same order of magnitude, i.e both start with $1$? My gut feeling is yes, but last time I checked my internal organs weren't the greatest of complexity theorists. – anon Aug 14 '11 at 6:44
Yes, p and q have the same population count. AFAICT this by itself doesn't make factoring any easier. – Dan Brumleve Aug 14 '11 at 6:49
My first guess would be that `it depends'. If $K$ only affects a relatively small number of bits, then we should be able to limit the possible values of $p-q$ to a relatively small set $S$. Then we could find $q$ among the solutions of the equations $x(x+s)=n$, where we test each $s\in S$. If $K$ affects a significant fraction of the bits, then this doesn't really cut down the size of the search space. But another clever trick may be out there? – Jyrki Lahtonen Aug 14 '11 at 7:02
If $K$ moves $m$ positions, then the size of that set $S$ from my earlier comment is at most $2^{2m-1}$ (probably less), so in order to not help the complexity of a brute force search, you should have $m>(\log_2p) /2$ at least. Also, $K$ should move at least some of the most (resp. least) significant bits. For otherwise the MSBs (resp. LSBs) of $p$ and $q$ are equal. The MSBs would then be those of $[\sqrt{n}]$ (resp. there would be two possible values for the LSBs that could be computed recursively - essentially a 2-adic Hensel lift, but easily understood without any 2-adic theory). – Jyrki Lahtonen Aug 14 '11 at 7:49
Does it help if we restrict K to be composed of disjoint swaps (order 2)? Alternatively, what if p and q are interpreted as graph-numbers and K is guaranteed to be a graph isomorphism? – Dan Brumleve Aug 14 '11 at 22:11

If K is composed of $k$ order 2 disjoint swaps (as suggested in a comment by Dan) and if $p,\ q$ are $u$ bits in length (ie, $u = \lceil \lg p \rceil$, where $\lg x$ denotes $\log_2 x$) then a naive search can be done in $\theta(3^k)$ time, as noted below. Only if $k$ is small and not dependent on $u$ (ie, is $O(1)$ and not $O(u)$) would naive search be useful. I don't know whether the special form of numbers would assist in any modern fast integer factorization algorithm, and in following merely work out the arithmetic of when naive search is feasible.

The $\theta(3^k)$ bound (vs. $2^{2k-1}$ suggested by Jyrki) arises as follows. We have $n = p\cdot q = (r-h)(r+h)$, where $p,\ q$ are primes, $r=(p+q)/2$, and $h$ is half of a delta of form dictated by K. Each delta is the sum of $k$ terms. The term for K-element $(a\ b)$ with LSB numbered as bit 1 has one of three forms: 0, $2^a-2^b$, or $2^b-2^a$. Thus, $3^k$ sums of terms $t_1+t_2+...t_k$ are possible. Half the set are negatives of the other half and need not be considered. Using naive searches (dividing by primes, vs. testing $3^k/2$ possible deltas) the same number of tests will arise when $\sqrt p / \ln\sqrt p = 3^k/2$, or [update 1] $k\approx u \lg2/(2\lg3) +\lg2/\lg3\approx 0.31\cdot u+0.63$, which is when roughly 2/3 of the bits of $p,\ q$ change places.

Of course, tests that solve quadratic equations are more expensive than those that just divide with remainder, but the general idea remains that $k$ must be $O(1)$ for feasibility.

Update 2: Previously I inadvertantly used $n$ two ways, as mentioned in comments below and illustrated in my first reply. Now $n = p\cdot q$ and $u$= number of bits in p.

-
I would think $O((\log n)^{1/3})$ would suffice rather than just $O(1)$. – Charles Aug 15 '11 at 19:48
Perhaps you wrote $n$ rather than $p$ in the above. $p$ is the prime being factored, $n$ is the number of bits in its binary representation. But your point is correct -- $O(1)$ is too pessimistic. If we suppose a modern method is $O(p^{1/3})$ and solve $p^{1/3} = 3^k$, we get $k\approx n\cdot{\ln2\over3\ln3}\approx0.21n$; so brute force is competitive for these numbers if no more than 42% of the bits change places. – jwpat7 Aug 15 '11 at 20:32
$n=pq$ in the original question, so that's how I'm using it. Your answer uses it both ways. – Charles Aug 15 '11 at 20:42
@Charles, you are right, I apologize for that. I'm now going to edit the "n=#bits" references in my answer to "u=#bits" to reduce longer-term confusion. – jwpat7 Aug 15 '11 at 22:03

Another algorithm that may be efficient in practice is to use a sort of "Hensel lifting" style trick. I'd expect this trick to let us achieve a running time of $O(2^k)$ or better.

In particular, we know

$$n \equiv pq \pmod{2^j}$$

holds for all $j$. Thus, we can iterate over $j=1,2,3,\dots$ and exhaustively explore all possible values of $(p \bmod 2^j, q \bmod 2^j)$. The exact running time will depend on the nature of the bit-permutation and the number of swaps in it, but if the number of swaps is small, the running time should be good.

In more detail: maintain a set $S_j$, which is the set of all possible values $(\alpha,\beta)$ such that $0 \le \alpha,\beta < 2^j$ and each $(\alpha,\beta) \in S_j$ is a possible value for $(p \bmod 2^j, q \bmod 2^j)$. Given $S_j$, we construct $S_{j+1}$ as follows. Consider $(\alpha,\beta) \in S_j$. We guess bit $j+1$ of $p$ (call it $a$) and bit $j+1$ of $q$ (call it $b$) and form $\alpha',\beta'$ using that guess, i.e.,

\begin{align*} \alpha' &= a \cdot 2^j + \alpha\\ \beta' &= b \cdot 2^j + \beta \end{align*}

Next, we check whether

$$n \equiv \alpha' \times \beta' \pmod{2^{j+1}}.$$

If yes, we add this $(\alpha',\beta')$ to $S_{j+1}$. Do this for each $(\alpha,\beta) \in S_j$ and each legal guess at $a,b$.

The bit-permutation helps us known which guesses at $a,b$ are legal. If the bit-permutation doesn't affect bit $j+1$ (case I), then we know $a=b$, so there are only two possibilities for $a,b$. If the bit-permutation swaps bit $j+1$ with a lower-indexed bit (case II), then there's only one possibility for $a,b$. If the bit-permutation swaps bit $j+1$ with a higher-indexed bit (case III), there are four possibilities for $a,b$.

Heuristically, the filtering condition $n \equiv \alpha' \times \beta' \pmod{2^{j+1}}$ will hold for about half of possible values of $(\alpha',\beta')$. Thus, we have a stochastic process where in each iteration the size of $S_j$ is multiplied by some random variable, whose distribution falls into one of three possibilities:

• Case I: The size of $S_j$ is multiplied by a random variable of mean $1$.

• Case II: The size of $S_j$ is multiplied by a random variable of mean $1/2$.

• Case III: The size of $S_j$ is multiplied by a random variable of mean $2$.

(Heuristically, $\lg |S_j|$ is a quasi-birth-death process where in each iteration we add a random variable of mean $0$, $-1$, or $1$, according to whether we are in case I, II, or III.)

The behavior of this stochastic process can be analyzed. Ignoring logarithmic factors, we should expect $|S_j|$ to be about $2^{z_j}$ where $z_j$ is the number of transpositions that have exactly one entry from $\{1,\dots,j\}$. In particular, $z_j \le k$. Thus, roughly speaking, we should expect $|S_j| \le 2^{k}$ (ignoring constant factors and logarithmic factors). For some bit-permutations, the running time could be non-trivially better than that.

-