Question

信息安全数学基础 x平方=41（mod 64）

Answer 1

先解xx=41 mod 8,x==k mod 8,k=±1,±3.亦即x=1 mod 2即可.

取x=2y+1代入得

4yy+4y+1-41== 0 mod 64

于是yy+y-10==0 mod 16

先解yy+y-10==0 mod 4,易得y=1或2 mod 4

即y=1,2,5,6,9,10,-3,-2mod 16

检验,yy+y-10=0 mod 16的解是 y=6,9 mod 16

转换,x==13,19 mod 32.此即原同余式的解.转化为模64,即

x=13,19,35,51 mod 64