#include <bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
typedef pair<int, int> PII;

#include "Euclid.cpp"
#include "DiscreteLog.cpp"

int main() {
  srand(time(NULL));
  assert(log_mod(407, 2891, 1459) == 276);
  for(int t = 0; t < 100; t++) {
    int a = rand()%5000;
    int b = rand()%5000;
    int n = rand()%5000;
    b %= n;
    int r = log_mod(a, b, n);
    assert(r == -1 || pow_mod(a, r, n) == b);
  }
}