二次剩余问题 数论

题目

二次剩余问题 数论
若同余式 x^2≡a(mod p),p=8m+1有解,并且已知N是模P的平方非剩余,试举出上述同余式的一个解法

答案

这通常是一个算法,没有确切的公式,但有一下确切的过程如下：设s=4ma^s=1(mod p) n^s=-1(mod p),以下求解过程中若出现-1,则用n^s代替之（这是关键）一、如果s是奇数,则a^(s+1)=a(mod p) 解得+-a^(s+1)/2否则a^s/2=1或...