数论基础：模奇素数的二次剩余 (2)
x2≡a (mod p)的解法x^2 \equiv a\ (mod\ p)的解法x2≡a (mod p)的解法
我们假定 a∈QR(p)a \in Q_{R}(p)a∈QR(p)，即上面的方程有解
p≡3 (mod 4)的情形p \equiv 3\ (mod\ 4)的情形p≡3 (mod 4)的情形
实现思路：随机选取 aaa，计算Legendre符号。若Legendre符号等于111，那么 ap+14(mod p)a^{\frac{p+1}{4}}(mod\ p)a4p+1(mod p) 就是方程的一个解。
原创文章 16获赞 6访问量 1415
关注
私信
展开阅读全文
作者：随缘懂点密码学
