Why are the e-th root mod N and the discrete logarithm mod p the two fundamental hard problems underlying asymmetric cryptography?
Computing $x^e \mod N$ (forward) is easy via SAM, but the inverse operations — e-th root mod N and discrete logarithm mod p — are computationally infeasible without special knowledge. This asymmetry IS asymmetric cryptography.
* Both functions are easy forward, hard backward. RSA's e-th root has a trapdoor (the factorization N = p·q); the discrete logarithm has none — it is hard for everyone. *
Problem 1: e-th root mod N (basis of RSA)
- Forward: $y \equiv x^e \mod N$ — easy (SAM algorithm)
- Inverse: $x \equiv \sqrt[e]{y} \mod N$ — hard in general
- But with a trapdoor (knowing the factorization $N = p \cdot q$), the inverse becomes easy
- This is a one-way function with trapdoor
Problem 2: Discrete logarithm mod p (basis of Diffie-Hellman, ElGamal, ECC)
- Forward: $y \equiv a^x \mod p$ — easy (SAM algorithm)
- Inverse: $x \equiv \log_a y \mod p$ — hard for everyone
- There is no known trapdoor — nobody can compute it efficiently
- This is a one-way function without trapdoor
The chaotic behavior: The values of $627^x \mod 941$ for $x = 1, 2, 3, ...$ appear completely random and chaotic. With real-world moduli ($N > 10^{900}$ for a 3000-bit key — the BSI recommendation from 2023), exhaustive search is impossible. For scale: even if every one of the ~$10^{80}$ atoms in the universe carried an entire universe of atoms, that would be only ~$10^{160}$ — still negligibly tiny beside $10^{900}$.
Tip: Both problems are "easy forward, hard backward" — this asymmetry is the entire foundation of public-key cryptography.
Go deeper:
Trapdoor function (Wikipedia) — the formal notion of easy-forward, hard-backward-with-a-secret.
Public Key Cryptography (Computerphile) — the one-way idea explained with a paint-mixing analogy.