二次剩余

最近在做一些关于椭圆曲线的优化，其中message到点的映射需要用到二次剩余相关的知识，也是第一次接触相关算法，查了一些资料之后自己在GPU端实现了一下，记录一下相关的心得。

一个整数X的平方 $X^{2}$ 除以另一个整数p的余数，就叫做X对于整数p的二次剩余。也就是当存在某个X使得

$X^{2} \equiv d (mod p)$

则d就是模p的二次剩余。一般来说，p都是大素数。

当需要判断一个x是否在椭圆曲线上时，需要计算 $y^{2} = x^{3} +ax +b$
是否成立，也就是算 $x^{3} +ax +b$ 是不是模p上的二次剩余

判断二次剩余

判断二次剩余可以用欧拉准则，但是欧拉准则也只能判断是不是，但是不能求解出具体的结果，用来验证足够了。

欧拉准则提出，d是模p的二次剩余的充要条件就是

$d^{(p-1)/2} \equiv 1 (modp)$

d是模p的非二次剩余的充要条件就是

$d^{(p-1)/2} \equiv -1 (modp)$

这里由于椭圆曲线域上的这个素数p都是提前知道的，所以我们可以预先算出来(p-1)/2,这样就可以方便的计算，省掉了很多计算的步骤。对于模幂操作可以用蒙哥马利模乘来实现模幂。

求解二次剩余

欧拉准则只能做判断，当判断这个x的坐标在椭圆曲线上时，我们需要求得y的坐标，所以还需要求解二次剩余，这里两种方法，一种是Tonelli-Shanks算法，我在程序中采用了这种方法(由于素数p满足其中的特殊条件)，所以计算很快，只需要算一次模幂操作。。

Tonelli-Shanks

这个算法其实网上有很多的介绍，这里多介绍，只说我在实现的时候看到的特殊情况
算法开始部分如下

输入为模p的一个二次剩余d，我们想得到的则是这个二次剩余的解X，使得 $X^{2} \equiv d (mod p)$

1.首先我们先算p-1，之后设 $p-1=Q*2^S$ ,也就是把p-1不停的除以2，除到结果为奇数为止。如果S=1，也就是p-1除以2为奇数(也可以表示为p-1不能被4整除),则直接返回 $X=\pm d^{(p+1)/4}$ 。

到这里我们可以发现如果素数p不能被4整除，则可以很快的返回结果。其实也就是素数二进制的最后一位如果是11则不行，16进制则是最后一位是3,7,B,F.很多大素数都满足这几个条件，SECP256K1的曲线，还有国密的SM2曲线都满足这个，所以可以直接返回。
具体的算法的步骤可以百度，有超级超级多介绍的。