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

Question

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?

Answer 1

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.