poj 2417 Discrete Logging

这是个求离散对数的问题。以前学密码学基础的时候也接触过,但是没想到acm里面还会有这样的习题。问题的意思是给定素数P,给出方程a^x = b % p,注意有模的方程等式2边都是取模数的意思。解这样的方程有一个固定的算法,叫做baby-step算法。但是,注意限定条件是p必须是素数。
下面的图描述了这个算法:


意思很清楚,就是假设x = i * m + j,那么方程可以转化为b*(a^-m)^i = a^j % p。先计算出右边的值,存储在一张表里面,然后从小到大枚举左边的i(0<=i<m),率先满足等式的就是最小的解x。
poj上面这个题用map存储(a^j,j)对的时候会超时,改成hash表存储才能过,额,毕竟理论复杂度不是一个数量级的。我的hash表是开了2个数组,一个键,一个值,用来相互验证,槽冲突的话,一直往后找位置。感觉这样的做法没有链式hash复杂度平均的样子。
代码如下:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

#define MAX (1000000)
long long nData[MAX];
long long nKey[MAX];
long long egcd(long long a, long long b, long long x, long long y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
long long ret = egcd(b, a % b, x, y);
long long t = x;
x = y;
y = t - (a / b) * y;
return ret;
}

long long GetPos(long long key)
{
return (key ^ 0xA5A5A5A5) % MAX;
}

void Add(long long key, long long data)
{
long long nPos = GetPos(key);
while (nData[nPos] != -1)
{
nPos = (nPos + 1) % MAX;
}
nData[nPos] = data;
nKey[nPos] = key;
}

int Query(int key)
{
int nPos = GetPos(key);

while (nData[nPos] != -1)
{
if (nKey[nPos] == key)
{
return nData[nPos];
}
nPos = (nPos + 1) % MAX;
}
return -1;
}

long long BabyStep(long long nA, long long nB, long long nP)
{
long long nM = ceil(sqrt((double)(nP - 1)));
long long x, y;
egcd(nP, nA, x, y);//y是nA%p的乘法逆
y = (y + nP) % nP;
long long nTemp = 1;
long long c = 1;//c是nA的—m次
memset(nData, -1, sizeof(nData));
memset(nKey, -1, sizeof(nKey));
for (long long j = 0; j < nM; ++j)
{
Add(nTemp, j);
nTemp = (nTemp * nA) % nP;
c = (c * y) % nP;
}

long long r = nB;
for (int i = 0; i < nM; ++i)
{
long long j = Query(r);
if (j != -1)
{
return i * nM + j;
}
r = (r * c) % nP;
}
return -1;
}

int main()
{
long long nP, nB, nN;

while (scanf("%I64d%I64d%I64d", &nP, &nB, &nN) == 3)
{
long long nAns = BabyStep(nB, nN, nP);
if (nAns == -1)printf("no solution\n");
else printf("%I64d\n", nAns);
}

return 0;
}