Discrete Logarithm (BSGS)
HardMathHash TableNumber Theory
Description
Given integers a, b, m with gcd(a, m) = 1 and m ≥ 2, return the smallest non-negative integer x such that a^x ≡ b (mod m). Return -1 if no such x exists.
Examples
Input:
a = 2, b = 3, m = 5Output:
3Explanation:
2^3 = 8 ≡ 3 mod 5.
Input:
a = 3, b = 1, m = 7Output:
0Explanation:
3^0 = 1.
Input:
a = 2, b = 4, m = 7Output:
2Explanation:
2^2 = 4.
Constraints
- •
2 ≤ m ≤ 10⁹ - •
gcd(a, m) = 1
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.