5
$\begingroup$

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?

  • 0
    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?2011-08-14

2 Answers 2

3

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.

  • 0
    @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.2011-08-15
0

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.