根存在性与数量
计算模 $n$ 的平方根其实就是求解方程
$$
x^2=y\ mod\ n\ ,\ gcd(y,n)=1
$$
那么显然,方程要有解,$y$ 必须是模 $p$ 的二次剩余。
当 $n$ 是素数时,根据欧拉判别法,$y$ 需要满足:
$$
y^{\frac{p-1}{2}}=1\ mod\ p
$$
否则无解。
对于 $n$ 是素数的情况,方程有 0 或 2 个解
对于 $n$ 是奇合数的情况,方程有 0 或 $2^l$ 个解( $n=\sum_{i=1}^lp_i^{e_i}$ )
$p=3\ mod\ 4$
关于这类素数,有一个通用公式
$$
x=\pm y^{\frac{p+1}{4}}\ mod\ p
$$
这个很好理解。其实我不会证明,但是可以用反证法(指反过来证明),计算一下 $x^2$ 发现正好是 $y$ 。
$p=1\ mod\ p$
这类素数的公式其实也是上面那个,但是问题是当 $p=1\ mod\ p$ 时,$\frac{p+1}{4}$ 并不是整数,而我们无法在模 $p$ 的情况下直接计算分数次幂(不然这篇东西就不必要存在了)。
于是我们有了 $Cipolla$ 算法。(下面是魔法)
首先我们对方程进行亿些变形
$$
x=\sqrt y=(a^2-(a^2-y))^{1/2}\ mod\ p
$$
令 $w^2 =a^2-y\ mod\ p$ ,并且 $(a^2-y)^{\frac{p-1}{2}}=-1\ mod\ p$ ,得到
$$
x=(a^2-w^2)^{1/2}=((a+w)(a-w))^{1/2}\ mod\ p
$$
又有
$$
w^p=w^{p-1}*w=(a^2-n)^{\frac{p-1}{2}}*w=-w\ mod\ p
$$
$$
a^p=a^{p-1}*a=a\ mod\ p
$$
所以
$$
x=((a^p+w^p)(a+w))^{1/2}\ mod\ p
$$
还有 $(a+w)^p=a^p+w^p\ mod\ p$ ,故
$$
x=(a+w)^{\frac{p+1}{2}}\ mod\ p
$$
现在我们的指数已经变成整数了,但问题是能不能求出这样的 $a$ 、$w$ ?
先来看 $a$ , $a$ 是由 $(a^2-y)^{\frac{p-1}{2}}=-1\ mod\ p$ 决定的,换句话说, $a^2-y$ 是 $p$ 的二次非剩余。这样的 $a$ 是很好找的,因为模 $p$ 的既约剩余系中有一半是它的二次非剩余,我们只要随机找一个 $a$ ,然后带入检验即可,这一步不会花费太久。
然后来看 $w$ ,根据前面提到的, $w$ 是二次非剩余 $a^2-y$ 的平方根,显然 $w$ 不存在。另一方面, $w^2$ 是确确实实存在的。那我们就算不下去了吗?显然不是,我们再回头看看 $x=(a+w)^{\frac{p+1}{2}}\ mod\ p$ ,如果我们对其进行展开,会得到 $c+wd\ ,\ c、d\in R$ 这样的一个数(是不是很像复数)。按道理 $w$ 是不存在的,所以 $c+wd$ 也不应该存在,但事实是 $x$ 是存在的(否则相当于方程无解),那么答案只有一个——虚部为零,即 $d=0$ 。
所以我们得出结论,计算结果与$w$ 无关。
至于结果的计算方法,我们可以对它直接按照二项式定理计算。当然了,还有一种比较有趣的算法。前面说了 $c+dw$ 的形式很像复数,那我们也可以按照复数的计算来做。只不过这样我们需要自定义一个“复数”乘法的规则(毕竟计算机不知道),由于还涉及到了乘方,所以我们还需要定义一下快速幂算法。综合来看两种计算过程应该差不多,后者可以将更多复杂的计算过程交给计算机处理,个人感觉好一点。
下面放上脚本
1 | #x^2=c mod p |
$n=pq$
这里拿它做一个示例,对于多因子 $n$ 的解法也差不多的。
首先根据中国剩余定理,方程 $x^2=y\ mod\ n\ ,\ n=pq$ 可以写成下面方程组
$$
\begin{cases}x^2=y\ mod\ p\\
x^2=y\ mod\ q\end{cases}
$$
然后分别解出来,我们得到了2组(4个)解(对于有 $l$ 种因子的 $n$ ,得到 $l$ 组),按照中国剩余定理的操作,我们需要从每一组解中选出一个来进行最后的运算,所有最后一共可以得到 $2^l$ 个解。
不难看出,只有中国剩余定理的每个方程都有解,原方程才有解。