How does the discrete logarithm mod p differ from the e-th root mod N, and why is it considered harder?

Question

Accepted Answer

Both are "easy forward, hard backward," but the discrete logarithm has NO known trapdoor — nobody can compute it efficiently, regardless of what they know. This makes it fundamentally different from RSA's e-th root.

* Exponentiation mod p scrambles the output: 15ˣ mod 19 already jumps around, and 627ˣ mod 941 looks purely random — so inverting it (the discrete log) has no shortcut. *
Concrete example: $15^x \mod 19$ (15 is a generator of $\mathbb{Z}_{19}^*$, so its powers cycle through all of $1..18$)

$x$
1
2
3
4
5
6
7
8
9
10

$15^x \mod 19$
15
16
12
9
2
11
13
5
18
4

The output jumps around with no pattern. Going forward ($x \mapsto 15^x$) is easy with SAM, but going backward is a search: to find $\log_{15} 4 \mod 19$ you must hunt for the $x$ with $15^x \equiv 4$ — here $x = 10$. With a 3000-bit prime in place of 19, that search is hopeless.
Comparison:

e-th Root mod N (RSA)
Discrete Log mod p (DH/ECC)

Forward
$y = x^e \mod N$ (easy)
$y = a^x \mod p$ (easy)

Backward
$x = \sqrt[e]{y} \mod N$ (hard)
$x = \log_a y \mod p$ (hard)

Trapdoor
Yes — knowing $p, q$ makes it easy
No — hard for everyone

Used in
RSA encryption/signatures
Diffie-Hellman, ElGamal, ECC

Why "no trapdoor" matters: In RSA, the key holder CAN decrypt (using the trapdoor). In DH, nobody computes discrete logs — instead, the protocol is cleverly designed so both parties reach a shared secret without either one solving the hard problem.
Go deeper:

Discrete logarithm (Wikipedia) — the no-trapdoor hard problem behind DH and ECC.

	e-th Root mod N (RSA)	Discrete Log mod p (DH/ECC)
Forward	$y = x^e \mod N$ (easy)	$y = a^x \mod p$ (easy)
Backward	$x = \sqrt[e]{y} \mod N$ (hard)	$x = \log_a y \mod p$ (hard)
Trapdoor	Yes — knowing $p, q$ makes it easy	No — hard for everyone
Used in	RSA encryption/signatures	Diffie-Hellman, ElGamal, ECC