# 13.4: Chinese Remainder Theorem

- Page ID
- 7400

Clearly the hardness of RSA is related to the hardness of factoring the modulus *N*. Indeed, if you can factor *N*, then you can compute *ϕ*(*N*), solve for *d*, and easily invert RSA. So factoring must be *at least as hard* as inverting RSA.

Factoring integers (or, more specifically, factoring RSA moduli) is believed to be a hard problem for classical computers.^{5} In this section we show that some other problems related to RSA are “as hard as factoring.” What does it mean for a computational problem to be “as hard as factoring?” More formally, in this section we will show the following:

**Theorem 13.4:**

*Either all of the following problems can be solved can be solved in polynomial-time, or none of them can:*

*Given an RSA modulus N*; =*pq, compute its factors p and q*.*Given an RSA modulus N*=*pq compute ϕ*(*N*) = (*p*– 1)(*q*– 1)*Given an RSA modulus N*=*pq and value e, compute its inverse d, where ed*≡*ϕ*(*N*) 1.*Given an RSA modulus N*=*pq, find any x*≢≡*N*± 1*such that x*^{2}≡*N*1

To prove the theorem, we will show:

*if*there is an efficient algorithm for (1),*then*we can use it as a subroutine to construct an efficient algorithm for (2). This is straight-forward: if you have a subroutine factoring*N*into*p*and*q*, then you can call the subroutine and then compute (*p*− 1)(*q*− 1).*if*there is an efficient algorithm for (2),*then*we can use it as a subroutine to construct an efficient algorithm for (3). This is also straight-forward: if you have a subroutine computing*ϕ*(*N*) given*N*, then you can compute the multiplicative inverse of*e*using the extended Euclidean algorithm.*if*there is an efficient algorithm for (3),*then*we can use it as a subroutine to construct an efficient algorithm for (4).*if*there is an efficient algorithm for (4),*then*we can use it as a subroutine to construct an efficient algorithm for (1).

Below we focus on the final two implications.

**Using square roots of unity to factor N**

Problem (4) of __ Theorem 13.4__ concerns a new concept known as square roots of unity:

Definition \(\PageIndex{1}\): sqrt of unity

*x is a square root of unity modulo N if x*

^{2}≡

*1.*

_{N}*If x*≢≡

_{N}1 and

*x ≢≡*−1,

_{N}*then we say that x is a*

**non-trivial**square root of unity. Note that ±1 are always square roots of unity modulo *N*, for any *N*((±1)^{2} = 1 over the integers, so it is also true mod *N*). But if *N* is the product of distinct odd primes, then *N* has 4 square roots of unity: two trivial and two non-trivial ones (see the exercises in this chapter).

**Claim 13.6**

*Suppose there is an efficient algorithm for computing nontrivial square roots of unity modulo N. Then there is an efficient algorithm for factoring N. (This is the (4) ⇒ (1) step in Theorem 13.4.)*

**Proof**

The reduction is rather simple. Suppose NTSRU is an algorithm that on input *N* returns a non-trivial square root of unity modulo *N*. Then we can factor *N* with the following algorithm:

The algorithm is simple, but we must argue that it is correct. When *x* is a nontrivial square root of unity modulo *N*, we have the following:

So the prime factorization of (*x* + 1)(*x* − 1) contains a factor of *p* and a factor of *q*. But neither *x* + 1 nor *x* − 1 contain factors of *both p* and *q*. Hence *x* + 1 and *x* − 1 must each contain factors of exactly one of {*p,q*}, and {gcd(*pq,x* − 1),gcd(*pq,x* + 1)} = {*p,q*}.

**Finding square roots of unity**

**Claim 13.7**

*If there is an efficient algorithm for computing d* ≡*ϕ*(*N*) *e*^{−1} *given N and e, then there is an efficient algorithm for computing nontrivial square roots of unity modulo N. (This is the (3) ⇒ (4) step in Theorem 13.4.)*

**Proof**

Suppose we have an algorithm FIND_D that on input (*N,e*) returns the corresponding exponent *d*. Then consider the following algorithm which uses FIND_D as a subroutine:

There are several return statements in this algorithm, and it should be clear that all of them indeed return a square root of unity. Furthermore, the algorithm does eventually return within the main for-loop, because *x*takes on the sequence of values:

Conditioned on *w* ∈ ℤ^{∗}* _{N}*, it is possible to show that SqrtUnity(

*N,e,d*) returns a square root of unity chosen

*uniformly at random*from among the four possible square roots of unity. So with probability 1/2, the output is a nontrivial square root. We can repeat this basic process

*n*times, and eventually encounter a nontrivial square root of unity with probability 1 − 2

^{−n}.