Question

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

Answer 1

这通常是一个算法,没有确切的公式,但有一下确切的过程如下：

设s=4m

a^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或者n^s*a^s/2=1

二、

如果s/2是奇数,同前求出解

如果s/2是偶数,同前,继续往下使a的指数变为s/4,s/8,...直到a的指数是奇数,即可以求出解来.

设s=2^r*J,J是奇数则最后一定出现：

a^J *n^(2k)=1(mod p)

两边乘以a求得解的形式为：+-a^(J+1)/2 *n^k

这有点象辗转相除法,程序会很快到达J（s每次除以2）