计算模m的k次根

2019-04-13 12:48发布生成海报

站内文章 / 模拟电子

15882 0

已知：

k, b, m

求解同余式：

x^{k} \equiv b (m o d m)

如果我们满足两个限制
1.

g c d (b, m) = 1

g c d (k, ϕ (m)) = 1

那么我们是有快速的方法求解x的 1.先计算

ϕ (m)

2.然后求

k u - ϕ (m) v = 1

得到

u

那么

x \equiv b^{u} (m o d m)

但是这种求法有两个限制的因素，所以也很少遇到，其实第一个条件可以适当放宽，如果m是若干个不同质数的乘积，那么可以使得

g c d (b, m) > 1

,但是第二条件还是要满足的。
bonus：这个东西对于RSA公钥密码体制很重要。