Factoring Numbers with inner nulls

35 Views Asked by At

Just imagine I have two primes, $p$ and $q$, each $1400$ bits long.

Each has the middle $1000$ bits set to $0$. Thus the top $200$ and bottom $200$ bits are meaningful in each number.

Take $s=pq$.

Would it be trivial given $s$, to determine what $p$ and $q$ were?

2

There are 2 best solutions below

0
On

Let $m=200$, $n=1200$. You have $$\begin{align} p &= 2^n a + b & 0 < a &< 2^m & 0 < b &< 2^m \\ q &= 2^n c + d & 0 < c &< 2^m & 0 < d &< 2^m \end{align}$$ Therefore $$s = pq = 2^{2n}ac + 2^n(ad+bc) + bd$$ where $$\begin{align} 0 < ac &< 2^{2m} & 0 < ad+bc &< 2^{2m+1} & 0 < bd &< 2^{2m} \end{align}$$ Since $2m+1\leq n$, you can read off $ac$ by discarding the lowest $2n$ bits of $s$. And $bd$ by discarding all but the lowest $2m$ bits of $s$. And $ad+bc$ by reading bits $n\ldots(n+2m)$ of $s$.

Now you can compute $$\begin{align} |ad-bc| &= \sqrt{(ad+bc)^2 - 4(ac)(bd)} \\ \{ad, bc\} &= \frac{(ad+bc) \pm |ad-bc|}{2} \end{align}$$ Now we have $(ac,ad,bc,bd)$, except that we do not know which of $\{ad,bc\}$ is which. Let's just make an arbitrary choice there.

Since $p$ is prime, $a$ and $b$ must be coprime. Similarly, since $q$ is prime, $c$ and $d$ must be coprime. Therefore $$\begin{align} a &= a\gcd(c,d) = \gcd(ac,ad) & b &= b\gcd(c,d) = \gcd(bc,bd) \\ c &= \gcd(a,b)\,c = \gcd(ac,bc) & d &= \gcd(a,b)\,d = \gcd(ad,bd) \end{align}$$ from which you can recover $p$ and $q$.

If $ad$ and $bc$ are swapped (as allowed by the $\pm$), then the subsequent determination of $a,b,c,d$ simply swaps $a$ with $c$ and $b$ with $d$ and therefore swaps $p$ and $q$, which is as it should be.

Once you have determined $a$, you can as well use $$\begin{align} c &= \frac{ac}{a}; & b &= \frac{bc}{c}; & d &= \frac{bd}{b} = \frac{ad}{a} \end{align}$$ This ensures $pq=s$ even if you do not know whether $p$ and $q$ are prime.

This method works as long as we know that more than the middle third of the factor bitstrings are zeroed.

0
On

Let's consider a decimal example, with shorter numbers: $36037007$ is the product of two primes $a \times 10^3 + b$ and $c \times 10^3 + d$, where $a, b, c, d$ are single digits. Find $a, b, c, d$.

We have $$(a \times 10^3 + b)(c \times 10^3 + d) = ac \times 10^6 + (ad+bc) \times 10^3 + bd$$ and so we must have $ac = 36, bd = 7, ad + bc = 37$.

Therefore $c = 36/a, d = 7/b$ and so we have to solve

$$ a(7/b) + b(36/a) = 37 $$

Let $a/b = x$. Then we have $7x + 36/x = 37$. Multiply through by $x$ and rearrange to get $7x^2 - 37x + 36 = 0$. It turns out that this has solutions $x = 9/7$ and $x = 4$.

From $x = 9/7$ we can recover $a/b = 9/7$, and since we know $a \times 10^3 + b$ is prime we must have $a = 9, b= 7$. Similarly from $x = 4$ we get $a = 4, b = 1$. Thus we have $36037007 = 9007 \times 4001$.

Consider alternatively $36035007$, which is not such a product. Going through the same procedure we get $7x^2 - 35x + 36 = 0$, and this doesn't have rational solutions since $35^2 - 4 \times 7 \times 36 = 217$ is not a square.

This will generalize to factoring $(xn^2 + yn + z)$ into factors $an+b$ and $cn+d$ as long as $a, b, c, d$ are sufficiently small - I believe $a, b, c, d < \sqrt{n/2}$ works. And this method does not require any factoring, only simple arithmetic and testing if a number is square.