One-way and P vs NP

Why do we believe that factoring is hard? The answer plunges into complexity theory, and in particular into the most famous open question in computer science: P vs NP.

Verifying is not finding

Consider the factorization problem. If I give you n = 91 and claim that 7 is a factor of it, you verify with one multiplication: 7 × 13 = 91. Easy.

But if I give you only n = 91 and ask you to find a factor, you have to search. On small numbers, this goes fast; on an n of 600 digits, no known method succeeds in a reasonable time.

This is the fundamental distinction:

   +---------------------+-----------------------------+
   |  VÉRIFIER (facile)  |  TROUVER (conjecturé dur)   |
   +---------------------+-----------------------------+
   |  7 × 13 == 91 ?     |  facteur de 91 = ?          |
   |  une multiplication |  chercher parmi les diviseurs|
   +---------------------+-----------------------------+

The classes P and NP

Complexity theory sorts problems into classes:

• P: the problems we know how to solve quickly (in polynomial time).
• NP: the problems for which a proposed solution can be verified quickly.

Every problem in P is in NP (if we can solve, we can verify). The great question is the converse: P = NP? In other words, can everything that verifies quickly also be solved quickly?

Problem	Verifying a solution	Finding a solution
Factoring n	easy (one multiplication)	conjectured hard
Discrete logarithm	easy (one exponentiation)	conjectured hard
Sudoku k × k	easy (check the grid)	conjectured hard

The link with cryptography

A one-way function needs inversion to be hard while verification is easy. This is exactly the profile of an NP problem that would not be in P.

Dizzying consequence: if P = NP, no one-way function could exist. Everything that verifies quickly would be solved quickly; factoring, inverting a discrete logarithm would become easy; RSA, Diffie-Hellman and nearly all of public-key cryptography would collapse.

Conversely, P ≠ NP is necessary but not sufficient: even in that case, our specific problems (factorization, discrete log) would still need to be effectively hard.

An edifice built on a conjecture

Modern cryptography therefore accepts a gamble: it assumes a few well-studied problems are hard — factorization, discrete logarithm, lattice problems — without absolute proof of their difficulty.

This is not a shameful weakness but a deliberate choice: these problems have resisted the best researchers for decades, which constitutes the best guarantee available.

In summary

Verifying a solution is easy (class P), finding it is conjectured hard (NP problems outside of P). One-way functions require this imbalance. If P = NP, they would not exist and public-key cryptography would collapse. We therefore build security on problems reputed to be hard, without absolute proof.