After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? They did not go into enough detail of this, sadly, so here is my question.
What is the relation of P, NP, and NP-Complete to encryption?
If I understand it correctly...
- P are the easily solvable problems such as 7 and 7 is 49.
- NP is finding the prime factors of very large numbers, in the realm of Google to Googleplex
Relations to Encryption:
- P is the "key" which allows us to decrypt the information when it reaches where it needs to go.
- NP encrypts the information with a long complex algorithm based on the concept of NP
Let's start with some definitions. We define the complexity classes P and NP in terms of languages and Turing Machines. A language is a set of finite strings over some finite alphabet. You can think of problems (ie., the Traveling Salesman Problem, Integer factoring problem) as languages.
A language $L$ is said to be recursively-enumerable or Turing acceptable if there exists a Turing Machine $M$ such that $L(M) = L$. That is, $M$ only accepts strings in $L$. If a string is not in $L$, then $M$ may not halt (think of an infinite loop on a program).
A language $L$ is recursive or decidable if $L(M) = L$ and $M$ can determine correctly if a string is or is not in $L$. That is, $M$ always halts with the correct "yes" or "no" answer.
A language $L$ is said to be in the class $NP$ if there exists a non-deterministic TM that can accept strings in $L$ in polynomial time. $L$ is said to be NP-Complete if every language in $NP$ can be reduced to $L$ in polynomial time. In other words- every problem in $NP$ can be solved with an algorithm used to solve an NP-Complete Problem.
The class $P$ is defined similarly to $NP$. We instead consider a deterministic TM that can decide $L$ in log-space (which implies polynomial time). So trivially, $P \subset NP$, but we don't know if $NP \subset P$.
Now (after the long-winded intro to complexity), let's talk more about the crypto. The big deal with cryptography and complexity is with integer factoring. As it stands, integer factoring is a hard problem. We don't have an efficient method for factoring large integers, which is the big reason the RSA cryptosystem works. This is the standard cryptosystem used today. Integer factoring is considered to be NP-Intermediate. That is, if $P \neq NP$, then integer factoring is neither in $P$ nor is it $NP$-Complete. So if someone could prove integer factoring was in $P$, people would be rushing to develop more efficient factoring algorithms as well as cryptosystems that don't rely on integer factoring being hard.