一、问题引入

二次剩余是数论基本概念之一。它是初等数论中非常重要的结果，不仅可用来判断二次同余式是否有解，还有很多用途。C.F.高斯称它为算术中的宝石，他一人先后给出多个证明。 [1] 

研究二次剩余的理论称为二次剩余理论。二次剩余理论在实际上有广泛的应用，包括从噪音工程学到密码学以及大数分解。

即关于方                                          x^2 ≡ a (mod p)

对于这个方程，求出满足条件的x。

二、x的求解

在上述问题下，根据p值的不同性质，可以将求解过程分为两种：

1、p = 3 mod 4情况：

解得 x=+-(a ^ ((a+1) / 4)

证明：

x^2 = a (mod p)

       =>a*1 (mod p)          可知 a^((p-1)/2)=1 (mod p)

       =>a ^ a^((p-1)/2) (mod p)

       =>a^((p+1)/2) (mod p)

x=+-a^((p+1)/4) (mod p)

if p%4==3:print(gmpy2.powmod(a,int((p+1)/4),p))print(-gmpy2.powmod(a,int((p+1)/4),p))

2、p = 1 mod 4  

 引入理论基础：（来自信安数学基础）

 

 由此可见，我们需要在求解中写出以下几个关键模块：

一、将质因数p转化为 p-1=2^t *P 其中，P为一个奇数，t则为为p-1中所含2的个数

while P%2==0:P=P//2k=k+1q=2

二、求出一个满足模p平方非剩余的数q，可以采取设置一个较小的质数q，验证它的 q^(p-1)/2==-1 （mod）p是否恒成立，即可的解：

q=2while q: l=gmpy2.powmod(q,int((p-1)/2),p)if l==p-1:breakq=sympy.nextprime(q)

 三、在k-1个循环中判断gmpy2.powmod(m,n,p)==p-1为0还是为1，其中：

如果为1，则x[k-i-1]=x[k-i]*pow(b,j0*(2**(i-1)))%p

如果为0，则x[k-i-1]=x[k-i]%p

最终输出x=x[0]即为我们所求解

for i in range(1,k):m=re_a*pow(x[k-i],2)n=pow(2,(k-i-1))if gmpy2.powmod(m,n,p)==p-1:j0=1x[k-i-1]=x[k-i]*pow(b,j0*(2**(i-1)))%pelse:j1=0x[k-i-1]=x[k-i]%p

 所以我们可以写出以下代码用于求解二次剩余定理：

p=
a=k=0
import gmpy2
import sympyP=(p-1)
if p%4==3:print(gmpy2.powmod(a,int((p+1)//4),p))print(-gmpy2.powmod(a,int((p+1)//4),p))
else:while P%2==0:P=P//2k=k+1q=2while q: l=gmpy2.powmod(q,int((p-1)//2),p)if l==p-1:breakq=sympy.nextprime(q)b=gmpy2.powmod(q,P,p)x=[0 for i in range(k)]re_a=gmpy2.invert(a,p)x[k-1]=gmpy2.powmod(a,int((P+1)//2),p)for i in range(1,k):m=re_a*pow(x[k-i],2)n=pow(2,(k-i-1))if gmpy2.powmod(m,n,p)==p-1:j0=1x[k-i-1]=x[k-i]*pow(b,j0*(2**(i-1)))%pelse:j1=0x[k-i-1]=x[k-i]%pprint(x[0])

带入

p=401

a=41

进行测试：

344