Người viết:
Reviewer:
Với , xét phương trình:
Ta cần tìm
Vì , ta có:
Đặt và , phương trình trở thành:
Nếu tìm được thỏa mãn, ta sẽ tìm ra nghiệm .
Nếu bạn đọc chỉ cần tìm nghiệm dương nhỏ nhất, hãy chú ý nhận xét sau:
Nhận xét: Nếu thì .
Điều này có thể chứng minh dễ dàng bằng phản chứng.
Từ nhận xét này, ta có thuật toán sau bao gồm 3 bước:
Bước 1:
Bước 2:
Bước 3:
Tổng kết lại, độ phức tạp thuật toán là: .
Chọn , ta được độ phức tạp: .
Code C++ minh họa:
int binpow(long long a, long long k, int mod){
long long res = 1;
for (; k; k >>= 1, a = a * a % mod){
if (k & 1)
res = res * a % mod;
}
return res;
}
int discrete_log_BSGS_naive(int a, int b, int m) {
a %= m;
b %= m;
int n = sqrt(m) + 1;
vector<pair<int, int>> f2(n + 1);
for (int q = 0, cur = b; q <= n; q++) {
f2[q] = make_pair(cur, q);
cur = 1LL * cur * a % m;
}
sort(f2.begin(), f2.end());
int step = binpow(a, n, m);
for (int p = 1, f1 = 1; p <= n; p++) {
f1 = 1LL * f1 * step % m;
auto res = *lower_bound(f2.begin(), f2.end(), make_pair(f1, 0));
if (res.first == f1) {
return n * p - res.second;
}
}
return -1;
}
Để cải tiến thuật toán, ta sử dụng cấu trúc dữ liệu bảng băm (Hash Table).
Với C++, ta có thể sử dụng std::unordered_map.
Xét hàm băm thỏa mãn:
có giá trị là .
Nếu không tồn tại để thì không được gán giá trị nào.
Tổng kết lại, độ phức tạp bài toán là: .
Tương tự, chọn , ta được độ phức tạp: .
Code C++ minh họa:
Trong C++, ta sử dụng unordered_map như một bảng băm:
vals.count(x) > 0 sẽ kiểm tra xem có tồn tại khôngvals[x] có là giá trị thỏa mãn int discrete_log_BSGS_coprime(int a, int b, int m) {
a %= m, b %= m;
int n = sqrt(m) + 1;
unordered_map<int, int> vals;
for (int q = 0, cur = b; q <= n; ++q) {
vals[cur] = q;
cur = 1LL * cur * a % m;
}
int step = binpow(a, n, m);
for (int p = 1, f1 = 1; p <= n; p++) {
f1 = 1LL * f1 * step % m;
if (vals.count(f1)) {
return n * p - vals[f1];
}
}
return -1;
}
Code C++ minh họa:
// Trả về x nhỏ nhất thỏa mãn a ^ x % m = b % m.
int discrete_log_BSGS(int a, int b, int m) {
a %= m, b %= m;
int n = sqrt(m) + 1;
int k = 1, add = 0, g;
while ((g = __gcd(a, m)) > 1) {
if (b == k) return add;
if (b % g) return -1;
b /= g, m /= g, ++add;
a %= m;
k = (k * 1ll * a / g) % m;
}
unordered_map<int, int> vals;
for (int q = 0, cur = b; q <= n; ++q) {
vals[cur] = q;
cur = 1LL * cur * a % m;
}
int step = binpow(a, n, m);
for (int p = 1, f1 = k; p <= n; p++) {
f1 = 1LL * f1 * step % m;
if (vals.count(f1)) {
int ans = n * p - vals[f1] + add;
return ans;
}
}
return -1;
}
Như bạn đọc thấy, thuật toán vẫn khá giống Cải tiến với bảng băm. Để đưa về trường hợp , ta chỉ tốn thêm bước xử lý sau:
while ((g = __gcd(a, m)) > 1) {
...
m /= g;
...
}
Mỗi vòng ta chia cho một số , nên chỉ có tối đa vòng. Mà mỗi vòng ta tính , nên tổng ĐPT cho phần xử lý này xấu nhất là .
Tổng kết lại, độ phức tạp thuật toán vẫn là .
Cho . Gọi là số nguyên dương nhỏ nhất thỏa mãn
Khi này được gọi là cấp của số nguyên modulo . Ký hiệu:
Bài toán: Cho . Tìm hay số nguyên dương nhỏ nhất thỏa mãn
Tương tự như trên, ta có thể sử dụng thuật toán Baby step - Giant step bên trên. Tuy nhiên với tính chất nêu trên của , ta có thuật toán tốt hơn dưới đây:
Bước 1: Tính và phân tích thừa số nguyên tố của trong đó nguyên tố và không cần phân biệt.
Thuật toán phân tích thừa số nguyên tố Pollard's rho sẽ giúp bước này có ĐPT tổng thể là .
Bước 2: Gán .
Duyệt từ đến :
Nếu thì gán .
Do nên ĐPT bước này là .
Sau cùng, chính là cần tìm.
Tổng độ phức tạp thuật toán trên là .
Code C++ minh họa:
using ll = long long;
ll powMod(ll x, ll p, ll md);
ll gcd(ll x, ll y);
// danh sách các ước nguyên tố của x (có thể trùng nhau)
vector<ll> factorize(ll x);
// hàm phi Euler
ll phi(ll n) {
auto ps = factorize(n);
ll res = n;
ll last = -1;
for (auto p : ps) {
if (p != last) {
res = res / p * (p - 1);
last = p;
}
}
return res;
}
// Cấp của a mod m
ll ord(ll a, ll m) {
if (gcd(a, m) != 1) return -1;
ll res = phi(m);
auto ps = factorize(res);
for (auto p : ps)
if (powMod(a, res / p, m) == 1) res /= p;
return res;
}
#include <bits/stdc++.h>
using namespace std;
// Copied from
// https://github.com/ngthanhtrung23/ACM_Notebook_new/blob/master/Math/NumberTheory/Pollard_factorize.h
using ll = long long;
using ull = unsigned long long;
using ld = long double;
ll mult(ll x, ll y, ll md) {
ull q = (ld)x * y / md;
ll res = ((ull)x * y - q * md);
if (res >= md) res -= md;
if (res < 0) res += md;
return res;
}
ll powMod(ll x, ll p, ll md) {
if (p == 0) return 1;
if (p & 1) return mult(x, powMod(x, p - 1, md), md);
return powMod(mult(x, x, md), p / 2, md);
}
bool checkMillerRabin(ll x, ll md, ll s, int k) {
x = powMod(x, s, md);
if (x == 1) return true;
while (k--) {
if (x == md - 1) return true;
x = mult(x, x, md);
if (x == 1) return false;
}
return false;
}
bool isPrime(ll x) {
if (x == 2 || x == 3 || x == 5 || x == 7) return true;
if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0) return false;
if (x < 121) return x > 1;
ll s = x - 1;
int k = 0;
while (s % 2 == 0) {
s >>= 1;
k++;
}
if (x < 1LL << 32) {
for (ll z : {2, 7, 61}) {
if (!checkMillerRabin(z, x, s, k)) return false;
}
} else {
for (ll z : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
if (!checkMillerRabin(z, x, s, k)) return false;
}
}
return true;
}
ll gcd(ll x, ll y) { return y == 0 ? x : gcd(y, x % y); }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long get_rand(long long r) {
return uniform_int_distribution<long long>(0, r - 1)(rng);
}
void pollard(ll x, vector<ll> &ans) {
if (isPrime(x)) {
ans.push_back(x);
return;
}
ll c = 1;
while (true) {
c = 1 + get_rand(x - 1);
auto f = [&](ll y) {
ll res = mult(y, y, x) + c;
if (res >= x) res -= x;
return res;
};
ll y = 2;
int B = 100;
int len = 1;
ll g = 1;
while (g == 1) {
ll z = y;
for (int i = 0; i < len; i++) {
z = f(z);
}
ll zs = -1;
int lft = len;
while (g == 1 && lft > 0) {
zs = z;
ll p = 1;
for (int i = 0; i < B && i < lft; i++) {
p = mult(p, abs(z - y), x);
z = f(z);
}
g = gcd(p, x);
lft -= B;
}
if (g == 1) {
y = z;
len <<= 1;
continue;
}
if (g == x) {
g = 1;
z = zs;
while (g == 1) {
g = gcd(abs(z - y), x);
z = f(z);
}
}
if (g == x) break;
assert(g != 1);
pollard(g, ans);
pollard(x / g, ans);
return;
}
}
}
// return list of all prime factors of x (can have duplicates)
vector<ll> factorize(ll x) {
vector<ll> ans;
for (ll p : {2, 3, 5, 7, 11, 13, 17, 19}) {
while (x % p == 0) {
x /= p;
ans.push_back(p);
}
}
if (x != 1) {
pollard(x, ans);
}
sort(ans.begin(), ans.end());
return ans;
}
//-----------------END OF POLLARD-----------------
ll phi(ll n) {
auto ps = factorize(n);
ll res = n;
ll last = -1;
for (auto p : ps) {
if (p != last) {
res = res / p * (p - 1);
last = p;
}
}
return res;
}
ll ord(ll a, ll m) {
if (gcd(a, m) != 1) return -1;
ll res = phi(m);
auto ps = factorize(res);
for (auto p : ps)
if (powMod(a, res / p, m) == 1) res /= p;
return res;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
if (fopen(".inp", "r")) {
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
int nt;
cin >> nt;
while (nt--) {
ll a, m;
cin >> a >> m;
cout << ord(a, m) << '\n';
}
return 0;
}