Why is the complexity of N=pq for RSA considered as exponential time?

Question

I'm studying about RSA algorithm for 16-bits and noticed that the complexity of N=pq is considered as exponential time.

In the algorithm, p and q are two random and distinct strong primes. All the prime numbers, except 2, are odd numbers. So, when p is multiplied by q, we will get an odd composite number, and the composite number can be easily factored. So, why is N=pq called the integer factorization problem and is hard to solve?

Answer 1

Note computational complexity, if not otherwise specified, is a function of the size of the information content of the inputs. We can think of that size as the number of bits needed to specify the input. (Another usable definition for the information content size is the length of an input string, where each character in the string is an element of a fixed finite "alphabet" set. Counting bits is the case where the alphabet has two elements.)

So a straightforward algorithm for finding the two non-trivial factors of a positive integer $N$ by trying division by $2$ and each odd number up to $\sqrt{N}$ does have complexity $O(\sqrt{N}) \subset O(N)$, but $N$ is not the information content variable we want. The number of bits needed to represent the input in the usual way is about $B = \log_2 N$. So the complexity is $O(\sqrt{2^B}) = O(2^{B/2})$. This is why we consider this algorithm exponential time.

Answer 2

Why is the complexity of N=pq for RSA considered as exponential time?

No, it is sub-exponential! See the details;

$p$ and $q$ are two random and distinct strong primes.

No, RSA is no longer requires strong primes since ECM and NFS.

why is $N=pq$ called the integer factorization problem and is hard to solve

Because more than 2 centuries the researchers tried to find a polynomial-time algorithm and yet no one is able to find as in Primiality ( AKS test).

---

Security of RSA is mainly two-fold ( short story of the long story);

1. If one can solve the factorization then one can break the RSA.

2. Or break the RSA problem;

   RSA problem is finding the $P$ given the public key $(n,e)$ and a ciphertext $C$ computed with $C \equiv P^e \pmod n$.

   It is clear that $1 \implies 2$ but the reverse $2 \implies 1$ is not proven yet

   Many searchers try to solve 2 but none achieved to find $e$-th root modulo $N$

The common attack way is factorization and for a beginner, it might be easy to think that factorization is easy since we have factor command in Linux, Mathematica, Maple, and not the last SageMath. Just use it and done. Simple is it? Not so if you know a bit about big numbers and complexity. 100 bits requires 10000 operations if the complexity is $\mathcal{O}(n^2)$ and 10000 bits requires 10000000000 bits of operation under the same algorithm. So the complexity of the algorithm is important. Over the years we had lots of algorithms like Fermat factoring, Pollard's Rho, Elliptic Curve Factoring (ECM), Number Field Sieve (NFS), General Number Field Sieve (GNFS) other then the basic Sieve of Eratosthenes.

RSA labs had a tradition to motivate the attacks started in 1991, RSA factoring challanges. When you input 2048-bit of RSA modulus you will see that this is not the case. The best-known factoring record achieved in 2020 on RSA-250 (829-bit)

• The factorisation of RSA-250 utilised approximately 2700 CPU core-years, using a 2.1GHz Intel Xeon Gold 6130 CPU as a reference. The computation was performed with the Number Field Sieve algorithm, using the open source CADO-NFS software

With CADO-NFS you can find my small personal experiences in this answer

Now, what is the complexity of the Number Field Sieve algorithm? For $b$-bit number $n$ it is;

$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right) =L_n\left[\frac{1}{3},\sqrt[3]{\frac{64}{9}}\right]$$

This is a sub-exponential algorithm that is significantly smaller than exponentials and but grows faster than any polynomial.

We can roughly say that this is $\exp(n^{1/3})$

Let's plug 100 digits $n$ that is $10^{10}$ and 2048-bit RSA that has around $n=10^{617}$

digits	cost
100	$e^{10^{3} \sqrt[3]{10}}$
250	$e^{10^{83} \sqrt[3]{10}}$
617	$e^{10^{205} \sqrt[3]{100}}$

Now, can you grasp how this cost increasing? It grows faster than any polynomial! I.e., when you double the $n$ as $2n$ then the cost is higher than any polynomial $p(2n)$.

---

We should note that the cost is not polynomial time and some believe that there exists a polynomial-time algorithm for integer factorization. It is in $NP$ but not proven to be in $NP-complete$.