Finding primitive root
For prime p, check candidates g. g is primitive iff g^((p-1)/q) ≢ 1 for every prime factor q of p-1. Small g usually works.
Advertisement
Baby-step giant-step
Discrete log in O(√p). Precompute g^i for i in [0, √p). Query g^(x-i·√p) matches → x = j·√p + i.
Advertisement
Pollard's rho for DLP
Similar birthday paradox. O(√p) with much less memory than BSGS.
Diffie-Hellman
Alice: A = g^a. Bob: B = g^b. Shared: g^(ab). Security relies on DLP hardness.