• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

『笔记』BSGS

开发技术 开发技术 1周前 (05-05) 8次浏览

写在前面

开始之前先来两首 (music)

简介

BSGS(baby-step giant-step),大步小步算法

又被称为拔山盖世算法,又被称为北上广深算法。。。。

作用

求解

[a^x equiv b pmod p
]

其中 (a perp p) ,方程的解 (x) 满足 $ 0 leq x < p$ 且数据范围较大,无法直接枚举在 (O(p)) 时间内通过。

[x=A left lceil sqrt{p} right rceil-B
]

其中

[0 leq A,B leq left lceil sqrt{p} right rceil
]

则有

[a^{left lceil sqrt{p} right rceil-B} equiv b pmod p
]

由费马小定理得

[a^{left lceil sqrt{p} right rceil} equiv b cdot a^B pmod p
]

我们已知 (a,b) 的取值,所以直接枚举 (B),计算 (b cdot a^B) ,将其插入 (hash) 表,然后计算 (a^{Aleft lceil sqrt{p} right rceil}),枚举所有 (A) 的值,看 (hash) 表中是否存在对应的 (b cdot a^B),即可得到所有的解 (x)

由于 (A,B) 均小于 (leq left lceil sqrt{p} right rceil) 所以总时间复杂度为 (O(sqrt{p})),若使用 (map) 则多一个 (log)

例题

T1

计算

[a^x equiv b pmod p
]

的最小非负整数解,无解时返回 (-1)

int BSGS(int a, int b, int p)
{
	map<int, int> h;
	b %= p;
	int t = (int)sqrt(p) + 1;
	for (int i = 1; i <= i; i++)
	{
		int tmp = (long long)b * Qpow(a, i, p) % p;
		h[tmp] = i;
	}
	a = Qpow(a, t, p);
	if (!a)
		return !b ? 1 : -1;
	for (int i = 0; i <= t; i++)
	{
		int tmp = Qpow(a, i, p);
		if (h.find(tmp) == h.end())
			return -1;
		else if (i * t - h[tmp] >= 0)
			return i * t - h[tmp];
	}
	return -1;
}

最后

掌握的不是很好哇,如果有错误欢迎向作者提出,蟹蟹!


程序员灯塔
转载请注明原文链接:『笔记』BSGS
喜欢 (0)