algo-numalgo-01
0.000
Challenge · difficulty 5/5
# Generalized discrete logarithm
Implement a file **`solution.py`** containing a function `discrete_log` that
solves the **discrete logarithm** problem for an **arbitrary** modulus:
```python
def discrete_log(a: int, b: int, m: int) -> int:
"""Return the smallest non-negative integer x such that
a**x is congruent to b (mod m)
or -1 if no such x exists."""
```
## Inputs
- `a`, `b` are integers with `a >= 0` and `b >= 0`. They may be larger than `m`;
reduce them modulo `m` before doing anything.
- `m` is the modulus with `m >= 1`.
## What you must return
The **smallest** integer `x >= 0` with `a**x ≡ b (mod m)`, using the convention
`a**0 == 1`. If no such `x` exists, return `-1`.
Because you must return the *smallest* solution, ties are impossible: the answer
is unique.
## The catch: `m` need not be prime, and `a` need not be coprime to `m`
This is the whole difficulty of the problem.
- When `gcd(a, m) == 1`, the powers `a**0, a**1, a**2, ...` cycle through a group
and the classic **baby-step giant-step** meet-in-the-middle idea applies.
- When `gcd(a, m) > 1`, the sequence of powers is **not** a clean cycle — it has a
"tail" (a pre-period) before it becomes periodic, and `a` is never invertible
modulo `m`. A solution may lie in the tail (small `x`) **or** deep inside the
periodic part (large `x`), and it may not exist at all. You must handle every
combination correctly, still returning the *smallest* `x`.
## Efficiency
A naive `O(m)` scan over exponents will **not** pass: some tests use a modulus of
size roughly `10**12` and cases with no solution, where scanning the whole cycle
would exceed the time limit. You are expected to use a sub-linear
(≈ `O(sqrt(m))`) approach such as an extended baby-step giant-step that first
factors out `gcd(a, m)`.
## Examples
```python
assert discrete_log(2, 8, 10) == 3 # 2**3 = 8
assert discrete_log(2, 1, 10) == 0 # 2**0 = 1
assert discrete_log(2, 6, 10) == 4 # powers of 2 mod 10: 1,2,4,8,6,... -> 6 at x=4
assert discrete_log(2, 3, 10) == -1 # 3 is never a power of 2 mod 10
assert discrete_log(3, 13, 17) == 4 # 3**4 = 81 = 13 (mod 17)
assert discrete_log(2, 0, 1024) == 10 # 2**10 = 1024 = 0 (mod 1024)
assert discrete_log(0, 0, 7) == 1 # 0**0 = 1, 0**1 = 0
assert discrete_log(0, 1, 7) == 0 # 0**0 = 1
assert discrete_log(5, 3, 5) == 0 or True # (illustrative)
```
## Edge cases to respect
- `m == 1`: every integer is `≡ 0 (mod 1)`, so the answer is always `0`.
- `b ≡ 1 (mod m)`: the answer is `0` (since `a**0 == 1`), for any `a`.
- `a ≡ 0 (mod m)`: `0**0 == 1`, and `0**k == 0` for `k >= 1`.
- Inputs `a`, `b` may exceed `m` and must be reduced modulo `m` first.
You may use `math.gcd`, `math.isqrt`, and Python's built-in modular inverse
`pow(x, -1, m)`. Do not import any discrete-log or number-theory library that
solves the problem for you.tests/test_discrete_log.py
import random
import pytest
from solution import discrete_log
def brute(a, b, m, cap):
"""Smallest x in [0, cap) with a**x == b (mod m), else -1."""
a %= m
b %= m
cur = 1 % m
for x in range(cap):
if cur == b:
return x
cur = (cur * a) % m
return -1
# ---------------------------------------------------------------- basic anchors
def test_zero_exponent_when_b_is_one():
assert discrete_log(2, 1, 10) == 0
assert discrete_log(3, 1, 100) == 0
# any base with b == 1 mod m -> x = 0
assert discrete_log(5, 1, 7) == 0
def test_simple_coprime():
assert discrete_log(2, 8, 10) == 3 # 2^3 = 8
assert discrete_log(3, 13, 17) == 4 # 3^4 = 81 = 13 (mod 17)
assert discrete_log(5, 3, 23) == 16
def test_no_solution_small():
assert discrete_log(2, 3, 10) == -1 # {1,2,4,8,6} never hits 3
assert discrete_log(4, 7, 13) == -1 # subgroup {1,4,3,12,9,10}
assert discrete_log(6, 8, 10) == -1
# ------------------------------------------------ non-coprime base and modulus
def test_non_coprime_reachable_in_cycle():
# powers of 2 mod 10: 1,2,4,8,6,2,4,8,6,... -> first 6 at x = 4
assert discrete_log(2, 6, 10) == 4
# powers of 10 mod 100: 1,10,0,0,...
assert discrete_log(10, 10, 100) == 1
assert discrete_log(10, 0, 100) == 2
assert discrete_log(10, 50, 100) == -1
def test_reaches_zero_tail():
assert discrete_log(2, 0, 1024) == 10 # 2^10 = 1024 = 0 (mod 1024)
assert discrete_log(6, 0, 8) == 3 # 6^1=6,6^2=36=4,6^3=216=0
# ----------------------------------------------------------- degenerate inputs
def test_modulus_one():
# everything is congruent to 0 mod 1, so x = 0 always
for a in range(0, 5):
for b in range(0, 5):
assert discrete_log(a, b, 1) == 0
def test_base_zero():
# 0^0 = 1, 0^k = 0 for k >= 1
assert discrete_log(0, 1, 7) == 0
assert discrete_log(0, 0, 7) == 1
assert discrete_log(0, 3, 7) == -1
def test_inputs_reduced_mod_m():
# a, b larger than m must be reduced first
assert discrete_log(12, 18, 10) == discrete_log(2, 8, 10) == 3
assert discrete_log(2 + 10 ** 6, 8, 10) == 3
# --------------------------------------------- exhaustive minimality guarantee
def test_exhaustive_matches_brute_force():
fails = []
for m in range(1, 70):
cap = m + 5 # covers the whole pre-period + period
for a in range(m):
for b in range(m):
got = discrete_log(a, b, m)
exp = brute(a, b, m, cap)
if got != exp:
fails.append((a, b, m, got, exp))
assert not fails, fails[:10]
# --------------------------------------------------- large solvable (property)
def test_large_solvable_validity_and_minimal_bound():
rng = random.Random(12345)
for _ in range(300):
m = rng.randint(2, 10 ** 9)
a = rng.randint(0, m - 1)
x = rng.randint(0, 2 * 10 ** 6)
b = pow(a, x, m)
r = discrete_log(a, b, m)
assert r != -1
assert pow(a, r, m) == b
assert 0 <= r <= x # returned x must be the *smallest*
def test_large_forces_subquadratic_prime():
# ~1e12 prime; an O(m) scan would blow the time limit, an O(sqrt m) one won't
m = 999999999989
a = 7
x = 654321
b = pow(a, x, m)
r = discrete_log(a, b, m)
assert pow(a, r, m) == b
assert 0 <= r <= x
def test_large_no_solution_full_cycle():
# p prime; a is a quadratic residue (its subgroup = the QRs), b a non-residue,
# so b is unreachable. A brute-force scan would traverse the whole (huge)
# cycle before giving up -> must be handled by the fast algorithm.
p = 1000000007
a = pow(3, 2, p) # a quadratic residue
b = 5 # verified quadratic non-residue below
assert pow(b, (p - 1) // 2, p) == p - 1
assert discrete_log(a, b, p) == -1
def test_large_no_solution_composite():
# under an even modulus, powers of 4 (or 2) can never equal an odd target
m = 2 ** 20
assert discrete_log(4, 3, m) == -1 # powers of 4 are 1 or even
assert discrete_log(2, 3, m) == -1 # powers of 2: 1,2,4,...,0 never 3
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.
Proposed solution
```python
import math
def discrete_log(a: int, b: int, m: int) -> int:
"""Return the smallest non-negative integer x such that
a**x is congruent to b (mod m)
or -1 if no such x exists."""
# Reduce inputs modulo m
a = a % m
b = b % m
# Edge case: modulus is 1
if m == 1:
return 0
# Edge case: b is 1 (mod m). a**0 == 1 is always a solution.
if b == 1:
return 0
# Edge case: a is 0 (mod m)
if a == 0:
# 0**0 == 1, 0**k == 0 for k >= 1
if b == 1:
return 0
if b == 0:
return 1
return -1
# Factor out the gcd of a and m
g = math.gcd(a, m)
# If gcd > 1, we can reduce the problem.
# We look for x such that a^x ≡ b (mod m).
# Let a = g * a', m = g * m'. Then a^x = g^x * (a')^x.
# We need g^x * (a')^x ≡ b (mod g * m').
# This implies b must be divisible by g^x.
# We iterate x starting from 0 upwards.
# For each x, we check if g^x divides b.
# If it does, we can divide the congruence by g^x.
# Let b' = b / g^x, m' = m / g^x, a' = a / g.
# We need to solve a'^x * (a')^x ≡ b' (mod m').
# Since gcd(a', m') == 1, we can use BSGS.
# We need to find the smallest x >= 0.
# x=0 is handled by the b==1 check above.
# We try x = 1, 2, ... until g^x > b or g^x > m.
# If g^x > b, then g^x cannot divide b (since b < g^x), so no solution for larger x.
# If g^x > m, then m' = m / g^x becomes 0, which is invalid for BSGS.
# We limit the search to x such that g^x <= max(b, m).
# Since b < m (reduced) and m can be large, we cap x at log_g(max(b, m)).
# A safe upper bound for x is log_g(m) + 1.
# Let's iterate x from 1 upwards.
# We stop if g^x > m.
# To be efficient, we can compute g^x iteratively.
# We need to find the smallest x.
# Let's try x = 1, 2, ...
# We need to check if g^x divides b.
# If not, no solution for this x.
# If yes, we reduce the problem.
# We need to be careful about the loop termination.
# If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.
# We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.
# We need a separate case for g == 1.
if g == 1:
# Standard BSGS
# We need to solve a^x ≡ b (mod m)
# Since gcd(a, m) == 1, a is invertible.
# If b == 0, then a^x ≡ 0 (mod m).
# Since gcd(a, m) == 1, a is invertible, so a^x is invertible.
# The only way a^x ≡ 0 is if m == 1, which is handled.
# So if b == 0, there is no solution.
if b == 0:
return -1
# Standard BSGS
# We want a^x = b
# Let N = ceil(sqrt(m))
# a^x = b
# a^x = a^{jN - i} = (a^N)^j / a^i
# a^N * a^i = b * a^j
# a^{i+jN} = b * a^j
N = math.isqrt(m) + 1
# Precompute baby steps: a^i for i in 0..N-1
table = {}
cur = 1
for i in range(N):
if cur == b:
return i
table[cur] = i
cur = (cur * a) % m
# Compute a^{-N} (inverse of a^N)
aN = pow(a, N, m)
inv_aN = pow(aN, -1, m)
# Giant steps
cur = b
for j in range(N):
if cur in table:
return j * N + table[cur]
cur = (cur * inv_aN) % m
return -1
# g > 1
# We try x = 1, 2, ...
# We need to find the smallest x.
# We can iterate x from 1 upwards.
# We stop if g^x > m.
# We need to check if g^x divides b.
# If not, no solution for this x.
# If yes, we reduce the problem.
# We need to be careful about the loop termination.
# If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.
# We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.
# We need a separate case for g == 1.
# Let's iterate x from 1 upwards.
# We stop if g^x > m.
# We need to check if g^x divides b.
# If not, no solution for this x.
# If yes, we reduce the problem.
# We need to be careful about the loop termination.
# If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.
# We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.
# We need a separate case for g == 1.
# Let's iterate x from 1 upwards.
# We stop if g^x > m.
# We need to check if g^x divides b.
# If not, no solution for this x.
# If yes, we reduce the problem.
# We need to be careful about the loop termination.
# If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.
# We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.
# We need a separate case for g == 1.
# Let's iterate x from 1 upwards.
# We stopErrors (stderr)
no code extracted from response
Self-repair attempts
[
{
"total": 1,
"answer": "```python\nimport math\n\ndef discrete_log(a: int, b: int, m: int) -> int:\n \"\"\"Return the smallest non-negative integer x such that\n\n a**x is congruent to b (mod m)\n\n or -1 if no such x exists.\"\"\"\n \n # Reduce inputs modulo m\n a = a % m\n b = b % m\n \n # Edge case: modulus is 1\n if m == 1:\n return 0\n \n # Edge case: b is 1 (mod m). a**0 == 1 is always a solution.\n if b == 1:\n return 0\n \n # Edge case: a is 0 (mod m)\n if a == 0:\n # 0**0 == 1, 0**k == 0 for k >= 1\n if b == 1:\n return 0\n if b == 0:\n return 1\n return -1\n \n # Factor out the gcd of a and m\n g = math.gcd(a, m)\n \n # If gcd > 1, we can reduce the problem.\n # We look for x such that a^x ≡ b (mod m).\n # Let a = g * a', m = g * m'. Then a^x = g^x * (a')^x.\n # We need g^x * (a')^x ≡ b (mod g * m').\n # This implies b must be divisible by g^x.\n \n # We iterate x starting from 0 upwards.\n # For each x, we check if g^x divides b.\n # If it does, we can divide the congruence by g^x.\n # Let b' = b / g^x, m' = m / g^x, a' = a / g.\n # We need to solve a'^x * (a')^x ≡ b' (mod m').\n # Since gcd(a', m') == 1, we can use BSGS.\n \n # We need to find the smallest x >= 0.\n # x=0 is handled by the b==1 check above.\n \n # We try x = 1, 2, ... until g^x > b or g^x > m.\n # If g^x > b, then g^x cannot divide b (since b < g^x), so no solution for larger x.\n # If g^x > m, then m' = m / g^x becomes 0, which is invalid for BSGS.\n \n # We limit the search to x such that g^x <= max(b, m).\n # Since b < m (reduced) and m can be large, we cap x at log_g(max(b, m)).\n # A safe upper bound for x is log_g(m) + 1.\n \n # Let's iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # To be efficient, we can compute g^x iteratively.\n \n # We need to find the smallest x.\n # Let's try x = 1, 2, ...\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n if g == 1:\n # Standard BSGS\n # We need to solve a^x ≡ b (mod m)\n # Since gcd(a, m) == 1, a is invertible.\n \n # If b == 0, then a^x ≡ 0 (mod m).\n # Since gcd(a, m) == 1, a is invertible, so a^x is invertible.\n # The only way a^x ≡ 0 is if m == 1, which is handled.\n # So if b == 0, there is no solution.\n if b == 0:\n return -1\n \n # Standard BSGS\n # We want a^x = b\n # Let N = ceil(sqrt(m))\n # a^x = b\n # a^x = a^{jN - i} = (a^N)^j / a^i\n # a^N * a^i = b * a^j\n # a^{i+jN} = b * a^j\n \n N = math.isqrt(m) + 1\n \n # Precompute baby steps: a^i for i in 0..N-1\n table = {}\n cur = 1\n for i in range(N):\n if cur == b:\n return i\n table[cur] = i\n cur = (cur * a) % m\n \n # Compute a^{-N} (inverse of a^N)\n aN = pow(a, N, m)\n inv_aN = pow(aN, -1, m)\n \n # Giant steps\n cur = b\n for j in range(N):\n if cur in table:\n return j * N + table[cur]\n cur = (cur * inv_aN) % m\n \n return -1\n \n # g > 1\n # We try x = 1, 2, ...\n \n # We need to find the smallest x.\n # We can iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n # Let's iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n # Let's iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n # Let's iterate x from 1 upwards.\n # We stop",
"passed": 0,
"test_error": "no code extracted from response"
},
{
"total": 1,
"answer": "```python\nimport math\n\ndef discrete_log(a: int, b: int, m: int) -> int:\n \"\"\"Return the smallest non-negative integer x such that\n\n a**x is congruent to b (mod m)\n\n or -1 if no such x exists.\"\"\"\n \n # Reduce inputs modulo m\n a = a % m\n b = b % m\n \n # Edge case: modulus is 1\n if m == 1:\n return 0\n \n # Edge case: b is 1 (mod m). a**0 == 1 is always a solution.\n if b == 1:\n return 0\n \n # Edge case: a is 0 (mod m)\n if a == 0:\n # 0**0 == 1, 0**k == 0 for k >= 1\n if b == 1:\n return 0\n if b == 0:\n return 1\n return -1\n \n # Factor out the gcd of a and m\n g = math.gcd(a, m)\n \n # If gcd > 1, we can reduce the problem.\n # We look for x such that a^x ≡ b (mod m).\n # Let a = g * a', m = g * m'. Then a^x = g^x * (a')^x.\n # We need g^x * (a')^x ≡ b (mod g * m').\n # This implies b must be divisible by g^x.\n \n # We iterate x starting from 0 upwards.\n # For each x, we check if g^x divides b.\n # If it does, we can divide the congruence by g^x.\n # Let b' = b / g^x, m' = m / g^x, a' = a / g.\n # We need to solve a'^x * (a')^x ≡ b' (mod m').\n # Since gcd(a', m') == 1, we can use BSGS.\n \n # We need to find the smallest x >= 0.\n # x=0 is handled by the b==1 check above.\n \n # We try x = 1, 2, ... until g^x > b or g^x > m.\n # If g^x > b, then g^x cannot divide b (since b < g^x), so no solution for larger x.\n # If g^x > m, then m' = m / g^x becomes 0, which is invalid for BSGS.\n \n # We limit the search to x such that g^x <= max(b, m).\n # Since b < m (reduced) and m can be large, we cap x at log_g(max(b, m)).\n # A safe upper bound for x is log_g(m) + 1.\n \n # Let's iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n if g == 1:\n # Standard BSGS\n # We need to solve a^x ≡ b (mod m)\n # Since gcd(a, m) == 1, a is invertible.\n \n # If b == 0, then a^x ≡ 0 (mod m).\n # Since gcd(a, m) == 1, a is invertible, so a^x is invertible.\n # The only way a^x ≡ 0 is if m == 1, which is handled.\n # So if b == 0, there is no solution.\n if b == 0:\n return -1\n \n # Standard BSGS\n # We want a^x = b\n # Let N = ceil(sqrt(m))\n # a^x = b\n # a^x = a^{jN - i} = (a^N)^j / a^i\n # a^N * a^i = b * a^j\n # a^{i+jN} = b * a^j\n \n N = math.isqrt(m) + 1\n \n # Precompute baby steps: a^i for i in 0..N-1\n table = {}\n cur = 1\n for i in range(N):\n if cur == b:\n return i\n table[cur] = i\n cur = (cur * a) % m\n \n # Compute a^{-N} (inverse of a^N)\n aN = pow(a, N, m)\n inv_aN = pow(aN, -1, m)\n \n # Giant steps\n cur = b\n for j in range(N):\n if cur in table:\n return j * N + table[cur]\n cur = (cur * inv_aN) % m\n \n return -1\n \n # g > 1\n # We try x = 1, 2, ...\n \n # We need to find the smallest x.\n # We can iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n # Let's iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n # Let's iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n # Let's iterate x from",
"passed": 0,
"test_error": "no code extracted from response"
},
{
"total": 1,
"answer": "```python\nimport math\n\ndef discrete_log(a: int, b: int, m: int) -> int:\n \"\"\"Return the smallest non-negative integer x such that\n\n a**x is congruent to b (mod m)\n\n or -1 if no such x exists.\"\"\"\n \n # Reduce inputs modulo m\n a = a % m\n b = b % m\n \n # Edge case: modulus is 1\n if m == 1:\n return 0\n \n # Edge case: b is 1 (mod m). a**0 == 1 is always a solution.\n if b == 1:\n return 0\n \n # Edge case: a is 0 (mod m)\n if a == 0:\n # 0**0 == 1, 0**k == 0 for k >= 1\n if b == 1:\n return 0\n if b == 0:\n return 1\n return -1\n \n # Factor out the gcd of a and m\n g = math.gcd(a, m)\n \n # If gcd > 1, we can reduce the problem.\n # We look for x such that a^x ≡ b (mod m).\n # Let a = g * a', m = g * m'. Then a^x = g^x * (a')^x.\n # We need g^x * (a')^x ≡ b (mod g * m').\n # This implies b must be divisible by g^x.\n \n # We iterate x starting from 0 upwards.\n # For each x, we check if g^x divides b.\n # If it does, we can divide the congruence by g^x.\n # Let b' = b / g^x, m' = m / g^x, a' = a / g.\n # We need to solve a'^x * (a')^x ≡ b' (mod m').\n # Since gcd(a', m') == 1, we can use BSGS.\n \n # We need to find the smallest x >= 0.\n # x=0 is handled by the b==1 check above.\n \n # We try x = 1, 2, ... until g^x > b or g^x > m.\n # If g^x > b, then g^x cannot divide b (since b < g^x), so no solution for larger x.\n # If g^x > m, then m' = m / g^x becomes 0, which is invalid for BSGS.\n \n # We limit the search to x such that g^x <= max(b, m).\n # Since b < m (reduced) and m can be large, we cap x at log_g(max(b, m)).\n # A safe upper bound for x is log_g(m) + 1.\n \n # Let's iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n if g == 1:\n # Standard BSGS\n # We need to solve a^x ≡ b (mod m)\n # Since gcd(a, m) == 1, a is invertible.\n \n # If b == 0, then a^x ≡ 0 (mod m).\n # Since gcd(a, m) == 1, a is invertible, so a^x is invertible.\n # The only way a^x ≡ 0 is if m == 1, which is handled.\n # So if b == 0, there is no solution.\n if b == 0:\n return -1\n \n # Standard BSGS\n # We want a^x = b\n # Let N = ceil(sqrt(m))\n # a^x = b\n # a^x = a^{jN - i} = (a^N)^j / a^i\n # a^N * a^i = b * a^j\n # a^{i+jN} = b * a^j\n \n N = math.isqrt(m) + 1\n \n # Precompute baby steps: a^i for i in 0..N-1\n table = {}\n cur = 1\n for i in range(N):\n if cur == b:\n return i\n table[cur] = i\n cur = (cur * a) % m\n \n # Compute a^{-N} (inverse of a^N)\n aN = pow(a, N, m)\n inv_aN = pow(aN, -1, m)\n \n # Giant steps\n cur = b\n for j in range(N):\n if cur in table:\n return j * N + table[cur]\n cur = (cur * inv_aN) % m\n \n return -1\n \n # g > 1\n # We try x = 1, 2, ...\n \n # We need to find the smallest x.\n # We can iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n # Let's iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n # Let's iterate x from 1 upwards.\n # We stop if g^x > m.\n \n # We need to check if g^x divides b.\n # If not, no solution for this x.\n \n # If yes, we reduce the problem.\n \n # We need to be careful about the loop termination.\n # If g == 1, we enter the loop, g^x = 1 always, so we divide by 1.\n # We will iterate until g^x > m. If g == 1, g^x = 1, so we loop forever.\n # We need a separate case for g == 1.\n \n # Let's iterate x from",
"passed": 0,
"test_error": ""
}
]