Skip to content

Discrete Log Hot Sheet

Use this page when the unknown is in the exponent and the contest-sized route is:

\[ a^x \equiv b \pmod m \]

with O(sqrt(m)) time and memory still acceptable.

Do Not Use When

  • you only need powmod or one modular inverse
  • the real task is congruence merging, not exponent recovery
  • sqrt(m) memory is already too large for the intended constraints
  • the intended lane is Modular Square Root / Discrete Root rather than plain discrete log

Choose By Signal

Core Invariants

  • in the coprime stage, rewrite x = pn + q with n ≈ sqrt(m)
  • store baby steps and scan giant steps until one residue collision appears
  • keep the minimum pn + q, not just any valid answer
  • when gcd(a, m) > 1, reduce first; BSGS is the second stage, not the whole story
  • this route only makes sense when the square-root table is still contest-safe

Main Traps

  • forgetting the gcd-reduction stage for composite-mod instances
  • returning one collision without checking whether it is the minimum valid exponent
  • treating this as a cheap lane when m is too large for O(sqrt(m)) memory
  • mixing up discrete log with linear congruence solving

Exact Starters In This Repo

Reopen Paths