首页 > itarticle > b429. 離散對數

b429. 離散對數

admin 11月 11, 2020 0

contents

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

1
2
3
4
 
2 1 5
2 2 5
3 5 17
4 2 17

Sample Output

1
2
3
4
 
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}$ 大步完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
#include <bits/stdc++.h> 
using namespace std;
// 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("%lldn", L);
	}
	return 0;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能