求𝑥** 2 = x mod m的解的个数

啊啊啊啊啊吖

2019-02-14 阅读量: 718

找到𝑥**2 = x (mod m)if 的解是多少是两个素数的乘法。（x ** 2 =平方x）（0≤x<m）

解决办法：

设p和q是素数。

如果因子是互质的，您可以将模块方程式分解为单独的方程式。

这意味着𝑥**2 = x (mod m)相当于𝑥**2 = x (mod p)和𝑥**2 = x (mod q)。

这些中的每一个都可以分解为x(x-1)=0 => x=0 or x=1。

所以你知道x是0或1模p，x是0或1模q。每个选择有1个解模数由中国余数定理，因此将有4个解。

2很容易（x = 0和x = 1）。另外两个可以使用扩展的欧几里德算法找到如下：

def egcd(a, b):

x,y = 0,1

lx,ly = 1,0

while b != 0:

q = a/b

(a, b) = (b, a%b)

(lx, x) = (x, lx-q*x)

(ly, y) = (y, ly-q*y)

return (lx, ly)

p=7

q=11

m=p*q

(lx, ly) = egcd(p,q)

print lx*p%m,ly*q%m

42.8571

关注作者

发表评论

暂无数据

CDA考试动态

CDA报考指南

推荐帖子