两篇比较好的blog，第二篇介绍了一些拓展的东西
http://blog.csdn.net/a_crazy_czy/article/details/51959546
http://blog.miskcoo.com/2014/08/quadratic-residue 因为个人数学不好，学这东西很多东西感性的理解就过掉了qaq，这里的笔记并不严谨 以下讨论的是模数P为奇素数的情况 先定义一个勒让德符号
(ap)=1(a是二次剩余)/−1(a不是二次剩余)/0(a≡0 (Mod p))
然后这个东西要怎么算，有个公式
(ap)=ap−12
这个公式挺好证的：
a≡0时显然
a≠0 (Mod p)时
因为ap−1≡1，所以ap−12≡1/−1
ap−12≡1时，定义x≡a√，于是有xp−1≡1，根据费马小定理x存在（其实我也不知道为什么有这个就存在了..感受一下..捂脸）
ap−12≡−1时，同上，有xp−1≡−1，x就不存在了 结论1：有p−12个数的勒让德符号为-1即无模P下的二次剩余
证明的话，在Mod p下，a,P−a平方的结果是一样的，0 to P−1的平方就会有p+12个互不相同的数，剩下的就没有二次剩余了 结论2：(a+b)p≡ap+bp (Mod p)(p是质数)
证明直接展开二项式定理，因为p是质数，除了i=0和p的项，其他项分子的p分母都消不掉，会被模成0，剩下ap+bp −−−−−−−−−−−−−(我是分割线)−−−−−−−−−−−−−− 我们要求一个数x，使得x2≡a (Mod p)
先找一个数a使得a2