Understanding the P vs NP Problem: Factoring and Its Impact on Internet Security

[JakeA]

I have some questions about the presentation of the P vs NP problem here. I'm quite new to this stuff, so pardon my ignorance if I make dumb statements.

http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf

Specifically:

The security of the internet, including most financial transactions,
depend on complexity-theoretic assumptions such as the difficulty of
integer factoring or of breaking DES (the Data Encryption Standard). If P=
NP these assumptions are all false. Specifically, an algorithm solving 3-SAT
in n2 steps could be used to factor 200-digit numbers in a few minutes.

First of all this statement is confusing to me. Is he talking about 200 binary digit numbers? Decimal? It's a bit ambiguous to me.

By factoring is he talking about prime factoring?

Is he talking about any 200 digit number? I can prime factor 2²⁰⁰ in less than a second.

Finally I assume he's claiming that since you can verify factors of 200 digit numbers in a few minutes, if P = NP then you could factor numbers in equally bounded time. Is this correct? I'm not sure because I see 2 problems with it.

1) If the problem is bounded by n^K, who's to say what k is? It could be huge, much larger than the k for the NP problem.

2) If he's talking about prime factorization, he is effectively saying that you can verify a prime number in P time, a very dubious claim.

As far as I can tell with the state of the art in cryptography, new factoring algorithms are big problems, actually increasing the need for larger keys/certificates all the time. My view is that the reason cryptography works is not because P != NP, but because prime number verification is Non P, meaning that incremental increases in number size create exponential increases in computational time. Again, I'm no expert, just wanting more information.

Thanks

 

[willem2]

First of all this statement is confusing to me. Is he talking about 200 binary digit numbers? Decimal? It's a bit ambiguous to me.

Decimal digits. 200 binary digits is already easy to factor. Pari does this in under 2 minutes
on my pc using the quadratic sieve algorithm

(21:25) gp > factor( nextprime(2^98) * nextprime(2^102))
%4 =
[316912650057057350374175801351 1]

[5070602400912917605986812821771 1]

(21:27) gp >

By factoring is he talking about prime factoring?

yes

Is he talking about any 200 digit number? I can prime factor 2²⁰⁰ in less than a second.

Number with 2 prime factors that are roughly the same size, such as used for RSA encryption.

Finally I assume he's claiming that since you can verify factors of 200 digit numbers in a few minutes, if P = NP then you could factor numbers in equally bounded time. Is this correct?
I'm not sure because I see 2 problems with it.

1) If the problem is bounded by n^K, who's to say what k is? It could be huge, much larger than the k for the NP problem.

It's indeed true that the polynomial could be a huge power, although this very rarely
occurs for any practical algorithm. Of course this is quite uncertain.

2) If he's talking about prime factorization, he is effectively saying that you can verify a prime number in P time, a very dubious claim.

Actually veryfying primality can be done in P time, look up the AKS primality test.
You don't need to do that however, since just checking the factorization by multiplying
the factors is enough, and there's no need to verify that they are prime.

 

[redwasp]

peace,

a problem is called 'P' if it is in the set P of the problems with a solution in polynomial time. this means that the time to solve it is a polynomial function (y = a₀ + a₁n + a₂n² + ... + a_mx^m for some integer m) of the size of the problem.

suppose we want to double an integer n. as n gets larger, we will always need more time to do the calculation. however we will always find a polynomial function of n that exceeds the needed time. the problem is in P.

suppose we want to look at the problem of factoring an integer n. this problem is not as easy as the first one. we will need a lot of steps to calculate the factors of n as n gets larger. in fact, up to now we don't know any algorithm that guarantees us a solution of the factorisation-problem in polynomial time. we have no proof that the problem is in P (actualy, most mathematicians would guess that it isn't in P).

now a problem is said to be in the set NP when the verification of its solution is possible in polynomial time.

it is trivial that a problem in P will also be in NP. but it is an open question if all problems in NP are also in P.

we can easily see that the factorisation problem is in NP. once we have obtained the factors p₁, p₂, p₃..., p_m of the integer n, we just have to multiply all these factors together to verify if our solution was correct. it is obvious that this can be done in polynomial time.

so if we can find a proof that the factorisation of n is a problem that is not in P, we would have a counterexample to the hypothesis that P = NP, we would have a problem p for which p ∉ P but p ∈ NP. this also means that if we would be able to find a proof that P = NP, it would imply that a smart algorithm exists (and could be found) that factorises n in polynomial time.

peace,

redwasp

 

[Robert1986]

Additionally, I think there is something worth mentioning with respect to the security of our crypto-systems. The reason that factoring a large integer is important is because, currently, this is the only way we know how to solve the discrete log problem. If we could find faster way to solve discrete log, then it wouldn't matter (with respect to cryptosystems) whether or not integers can be factored. Also, if Quantum Computers are ever made that can, say, factor integers other than 15, this whole thing goes out the window. There are other crpytosystems, like lattice-point, that seem to be impervious to even quantum attacks.

 

[blue_raver22]

for the interesting presentation.Thank you for your questions and interest in the P vs NP problem and its impact on internet security. I will try my best to address your concerns and clarify the information presented.

Firstly, the statement about 200-digit numbers refers to decimal digits. This means that if P = NP, an algorithm solving 3-SAT in n^2 steps could be used to factor numbers with 200 decimal digits in just a few minutes. This is a significant concern for internet security as many encryption algorithms, such as RSA, rely on the difficulty of factoring large numbers to protect sensitive information.

When we talk about factoring, we are indeed referring to prime factoring. This is because most encryption algorithms are based on the idea that it is easy to multiply two large prime numbers together, but very difficult to factor the product back into its original prime factors. Therefore, if P = NP, it would mean that prime factorization is also easy and encryption algorithms would no longer be secure.

You are correct in your understanding that if P = NP, the time required to factor a number would be bounded by n^k, where k is some constant. This means that for any number, no matter how large, there would be an algorithm that could factor it in a fixed amount of time. This is a major concern for internet security as it would render current encryption methods useless.

Regarding your points about prime number verification, I would like to clarify that verifying whether a number is prime is indeed in P, as there are efficient algorithms for this. However, finding the prime factors of a number is a different problem, known as prime factorization, and is believed to be in NP. This means that while verifying a prime number may be easy, actually finding its prime factors is a much more difficult task.

In conclusion, the belief that prime factorization is a hard problem is what allows for secure encryption on the internet. If P = NP, this belief would be proven false and the security of the internet would be compromised. I hope this helps to clarify some of the points raised in the presentation. Thank you again for your interest and questions.