📂Number Theory

Factorization of Semiprimes: Conditions for Easy Resolution

Theorem ¹

The problem of factorizing semiprimes $N = pq$ becomes relatively easy under the following conditions:

• (i): $p$ is a smooth prime.
• (ii): $p \approx q$

Explanation

The meaning of condition (ii) is that when the difference between $p$ and $q$ is small, it becomes easier to solve, which requires explanation:

• At first glance, if $p,q \in \mathbb{N}$ is constrained by $(p + q)$, the best way to maximize $N = pq$ is to make the difference between $p$ and $q$ as small as possible. For instance, if $p+q \le 12$, then $pq$ has its maximum value $35$ when $7 = p \approx q = 5$.

To prevent solving by brute force, both $p$ and $q$ should be as large as possible. Suppose $$N_{1}=3 \cdot 47=141 \\ N_{2}=11 \cdot 13=143$$ is given, then when it is disclosed, the difference is only $2$, but $N_{1}$ gets solved immediately as the “hard work” begins.

• However, using $p$ and $q$ of similar sizes for this simplistic reason could be cracked by a two-dimensional thinker. Simply put, if really $p \approx q$, an attacker can significantly reduce the candidate solutions near $\sqrt{N}$ by assuming $N \approx p^2$. If mathematical techniques are applied in this idea, $N=pq$ becomes a very easy problem.

Proof

(i)

If $p$ is a smooth prime, the Pollard $p-1$ factorization algorithm can be used, making the semiprime factorization problem relatively easy to solve.

■

(ii)

If we set $p := a + b$, $q := a - b$, then $p$, $q$ become primes that are $\pm b$ distance apart centered around $a$. Representing this with $N$, $$\begin{align*} N =& ( a + b)(a - b) \\ =& a^2 - b^2 \end{align*}$$ which means $N + b^2 = a^2$. Thus, by increasing $1$ by $b$ in $N$ and finding when $\left( N + b^2 \right)$ becomes a square number, we can know what $p = a + b$, $q = a - b$ are, thus making the semiprime factorization problem relatively easy to solve.

■

Examples

As an example, consider $N = 25217$. Directly factorizing $N$ is not an easy task, but knowing that $25217 + 8^2 = 159^2$ allows us to immediately find $$\begin{align*} p =& 159 + 8 = 167 \\ q =& 159-8 = 151 \end{align*}$$ In the context of the text, because it’s $167 \approx 151$, it got solved easily.

On the other hand, let’s make finding this $b$ more ingenious. For some $k$, $$k N = a^2 - b^2$$ since $(a+b)$ and $(a-b)$ are multiples of $k$, simply dividing both sides by $k$ gives us the formula for $N$ directly. The reason for this cumbersome process is because the formula can be represented like this: $$a^2 \equiv b^2 \pmod{N}$$ Following this method, we find $d = q$ next.

---

Step 1. $c_{i}$

For numbers $c_{i}$ with a low calculation divisor, find $a_{1} , \cdots , a_{r}$ that satisfy $c_{i} \equiv a_{i}^{2} \pmod{p}$.

---

Step 2. $b^2$ Calculation

Find $c_{i_{1}} , \cdots , c_{i_{s}}$ that satisfy $$a_{i_{1}} \cdots a_{i_{s}} = a \\ c_{i_{1}} \cdots c_{i_{s}} = b^2$$

---

Step 3. $d = \gcd \left( N , a-b \right)$

Using the calculated $a$ and $b$, $$\begin{align*} a^2 & \equiv \left( a_{i_{1}} \cdots a_{i_{s}} \right)^{2} \\ & \equiv a_{i_{1}}^{2} \cdots a_{i_{s}}^{2} \\ & \equiv c_{i_{1}} \cdots c_{i_{s}} \\ & \equiv b^2 \end{align*}$$ so $d$ is a divisor of $N$, which is $q$.

See also

• Factorization

Security algorithms utilizing the difficulty of the factorization problem

• RSA public key cryptosystem
• Goldwasser-Micali probabilistic key cryptosystem

Attack algorithms for the factorization problem

• Pollard’s p-1 factorization algorithm
• Conditions for easily solving the semiprime factorization problem