Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
1  
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
1  
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.