b429. 離散對數

1. Problem
1. 1.1. 背景
2. 1.2. 問題描述
2. Sample Input
3. Sample Output
4. Solution

Problem

背景

高中時上過對數，了解 $a^x = b$，則 $x = \log_{a}{b}$。這個問題很簡單，但是 log() 又是怎麼運作，當時是用查表法，不久在大學就會學到泰勒級數，藉由電腦運算，計算越多次就能更逼近真正的結果。

離散對數的形式如下：

$$a^x \equiv b \mod n$$

已知 $a, b, n$，通常會設定 $0 \le a, b < n$。這問題的難處在於要怎麼解出 $x$，沒有 log() 可以這麼迅速得知。

為什麼需要離散對數？不少的近代加密算法的安全強度由這個問題的難度決定，例如 RSA 加密、Diffie-Hellman 金鑰交換 … 等，實際運用需要套用許多數論原理。然而，加密機制要保證解得回來，通常會保證 $gcd(a, n) = 1$，讓乘法反元素 (逆元) 存在。

問題描述

$$a^x \equiv b \mod n$$

已知 $a, b, n$，解出最小的 $x$，若不存在解則輸出 NOT FOUND。

Sample Input

Sample Output

0
1
5
NOT FOUND

Solution

解決問題 $y = g^x \mod p$，當已知 $y, g, p$，要解出 $x$ 的難度大為提升，不像國高中學的指數計算，可以藉由 log() 運算來完成，離散對數可以的複雜度相當高，當 $p$ 是一個相當大的整數時，通常會取用到 256 bits 以上，複雜度則會在 $O(2^{100})$ 以上。

實際上有一個有趣的算法 body-step, giant-step algorithm，中文翻譯為 小步大步算法 ，在 ACM-ICPC 競賽中也可以找到一些題目來玩玩，算法的時間複雜度為 $O(\sqrt{p})$，空間複雜度也是 $O(\sqrt{p})$。相信除了這個外，還有更好的算法可以完成。

小步大步算法其實很類似塊狀表的算法，分塊處理，每一塊的大小為 $\sqrt{p}$，為了找尋答案計算其中一塊的所有資訊，每一塊就是一小步，接著就是利用數學運算，拉動數線，把這一塊往前推動 (或者反過來把目標搜尋結果相對往塊的地方推動)。因此需要走 $\sqrt{p}$ 大步完成。

#include <bits/stdc++.h> 
using namespace std;
// Baby-step Giant-step Algorithm
// a x + by = g
void exgcd(long long  x, long long y, long long &g, long long &a, long long &b) {
    if (y == 0)
        g = x, a = 1, b = 0;
    else
        exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
long long inverse(long long x, long long p) {
    long long g, b, r;
    exgcd(x, p, g, r, b);
    if (g < 0)	r = -r;
    return (r%p + p)%p;
}
long long BSGS(long long P, long long B, long long N) {
    unordered_map<long long, int> R;
    long long sq = (long long) sqrt(P);
    long long t = 1, f;
    for (int i = 0; i < sq; i++) {		
        if (t == N)	
            return i; 		
        if (!R.count(t))
            R[t] = i;
        t = (t * B) % P;
    }
    
    f = inverse(t, P);
    for (int i = 0; i <= sq+1; i++) {
        if (R.count(N))
            return i * sq + R[N];
        N = (N * f) % P;
    }
    return -1;
}
int main() {
    long long P, B, N; // find B^L = N mod P
    while (scanf("%lld %lld %lld", &B, &N, &P) == 3) {
        long long L = BSGS(P, B, N);
        if (L == -1)
            puts("NOT FOUND");
        else
            printf("%lld\n", L);
    }
    return 0;
}

Morris' Blog