0

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?

AmI Alive
  • 21
  • 1
    https://www.cs.purdue.edu/homes/ssw/2014c.pdf – Moo Jan 07 '22 at 13:13
  • 4
    "...the composite number can be easily factored." How? – Sergey Guminov Jan 07 '22 at 13:15
  • It is only easy if you know the factors – Peter Jan 07 '22 at 13:19
  • I mean, if both p and q are primes, then isn't finding the factors easy using the computer? Because prime*prime = a number, and the number can only be obtained using those two primes – AmI Alive Jan 07 '22 at 13:19
  • There is no known efficient method to factor an arbitary number. The best known methods have a superpolynomial computational complexity. – Peter Jan 07 '22 at 13:20
  • @AmiAlive. The most straightforward way would be to try to divide N by all prime numbers consecutively, but this requires an order of N divisions, since there is no easy way to list all primes, and N is exponential in the number of bits of N! So this is an exponential time algorithm. Smarter algorithms are subexponential, but still nowhere near being polynomial time. – Sergey Guminov Jan 07 '22 at 13:25
  • @AmIAlive, practical applications of RSA involve factoring numbers with over 300 digits and only two factors. Naive methods of factorisation have no chance of success, and non-naive methods may get there eventually but you're looking at months, not seconds, to complete. – Peter Phipps Jan 07 '22 at 13:33
  • @PeterPhipps I see. Maybe I said it's 'easy' because I'm doing 16-bits only. Thanks and I'll keep it in mind. – AmI Alive Jan 07 '22 at 13:39
  • @SergeyGuminov Thanks for the clarification. I'll study more while keeping it in my mind ^^ – AmI Alive Jan 07 '22 at 13:40
  • Exponential-time algorithms do tend to be "easy" when the exponent is small! – David K Jan 07 '22 at 13:41
  • @Moo I am still not convinced that this algorithm , which is very abstractively described in wikipedia , would actually work. However, RSA has not even be proven to be safe assuming the enemy cannot determine the prime factors. Not good for a such widely used method. – Peter Jan 07 '22 at 14:05
  • @Moo Nevertheless , I wish , Peter Ripota would be right , claiming that quantum computers cannot be realized anyway. The damage the development of classical computers has caused , is already big enough. – Peter Jan 07 '22 at 14:15
  • @Moo Unfortunately , the typical way things develop. Just look who won the nobel prizes in physics in the last , say , $20$ years and for what. I think, we should end now here , we can continue however in a new chatroom, if you want. – Peter Jan 07 '22 at 14:25
  • Let us continue this discussion in chat. – Peter Jan 07 '22 at 14:28

2 Answers2

2

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.

aschepler
  • 9,449
0

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$.

kelalaka
  • 1,637