# 4: The Hardless of Factoring N

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:

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

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 x2N 1. If x ≢≡N 1 and x ≢≡N −1, 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 xtakes 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 − 2n.