[数论]二次剩余及计算方法

二次剩余(Quadratic residue)问题是要求解以下同余方程:


\begin{equation}
\label{quadratic}
x^2 \equiv a \pmod p~~(p \nmid a)
\end{equation}

下面对 p奇素数奇素数的幂2的幂以及合数的情况分别考虑

奇素数


先来考虑当 p 是奇素数时的情况。

根据欧拉准则,当 a\bmod p 的平方剩余时有

 a^{\frac{p - 1}{2}} \equiv 1 \pmod p

首先设 p - 1 = 2^t \cdot s, (2 \nmid s)

1^\circt = 1 时,显然有

 \sqrt{a} = \sqrt{a^{\frac{p - 1}{2}}\cdot a} = a^{\frac{s+1}{2}}

所以 x = a^{\frac{s+1}{2}} 就是方程的一个解了(因为 s 是奇数,所以 \frac{s+1}{2} 是整数可以直接计算)

2^\circt > 1

x_{t-1} = a^{\frac{s+1}{2}}

注意到

 (a^{-1}\cdot x_{t-1}^2)^{2^{t-1}} = a^{\frac{p-1}{2}} \equiv 1 \pmod p

所以 a^{-1}\cdot x_{t-1}^2 就是 \bmod p2^{t-1} 阶单位根

而我们要求的可以认为是

 (a^{-1}\cdot x^2)^{2^0} \equiv 1 \pmod p

也就是 \bmod p1 阶单位根

现在来考虑有没有办法把从 x_{t-k} 递推到 x_{t-(k+1)}

\bmod p2^i 阶单位根为 \epsilon_i = a^{-1}\cdot x_i^2

(根据上面的讨论 x_{t-1} = a^{\frac{s+1}{2}}

显然 \epsilon_{t-k}^{2^{t-(k+1)}} \equiv \pm 1 \pmod p

 a)~\epsilon_{t-k}^{2^{t-(k+1)}} \equiv 1 \pmod p

这样的话只要 x_{t-(k+1)} = x_{k} 即可

 b)~\epsilon_{t-k}^{2^{t-(k+1)}} \equiv -1 \pmod p

在这种情况下我们看看能不能找到一个 \lambda,使得

 \epsilon_{t-(k+1)}^{2^{t-(k+1)}} 
= \left [a^{-1}\cdot (\lambda \cdot x_{t-k})^2 \right ]^{2^{t-(k+1)}}
\equiv 1 \pmod p

如果找到这个 \lambda 那么,x_{t-(k+1)}=\lambda\cdot x_{t-k}

\lambda 满足条件时就需要

 (\lambda^2)^{2^{t-(k+1)}} = \lambda^{2^{t-k}} \equiv -1 \pmod p

又会想到根据欧拉准则,假设 b\bmod p 的二次非剩余,那么会有

 b^{\frac{p-1}{2}} = b^{2^{t-1}\cdot s} = (b^{2^{k-1}\cdot s})^{2^{t-k}} \equiv -1 \pmod p

所以我们只需要找一个 \bmod p 的二次非剩余 b,再令 \lambda = b^{2^{k-1}\cdot s} 就可以从 x_{k} 推到 x_{t-(k+1)}

以此类推,便可最终得到 x_{0},然后方程 (\ref{quadratic}) 的解就是 x \equiv \pm t_0 \pmod p

最后这个方法的时间复杂度是 O(t^2),大约会是 O(\log^2 p)

下面给出核心部分的伪代码

x \leftarrow a^{\frac{s+1}{2}} \bmod p

e \leftarrow a^s \bmod p

k \leftarrow 1

while(k < t)     if(e^{2^{t-(k+1)}} \bmod p \neq 1)         x \leftarrow x \cdot b^{2^{k-1}\cdot s} \bmod p         e \leftarrow a^{-1}\cdot x^2 \bmod p

奇素数的幂


再来考虑 p^q 的情况,其中 p 为奇素数

首先,记 a = p^k\cdot A, ~p \nmid A, ~k < q 1^\circ 如果 2 \nmid kk < q,在这种情况下,a\bmod p^q 的二次非剩余 假设不是这样,那么存在 r, s 使得 \left(p^r\cdot s\right)^2 \equiv p^k \cdot A \pmod{p^q}, ~s \nmid p^q 因为 s \nmid p^q, s < p^q,所以 s 不含因子 p,因此 s^2 也不含 所以 p^k \equiv p^{2r} \pmod{p^q},这显然不成立 所以 a\bmod p^q 的二次非剩余 2^\circ 如果 2 \mid kk < q,在这种情况下,如果 A\bmod p^q 的二次剩余,那么 a 就是,否则就不是


然后我们知道答案肯定会是 x = p^{\frac{k}{2}} \cdot x_0 的形式,所以


\begin{eqnarray*}
&x^2 &\equiv& a &\pmod{p^q}\\
\Rightarrow &(p^{\frac{k}{2}} \cdot x_0)^2 &\equiv& p^k\cdot A &\pmod{p^q}\\
\Rightarrow &x_0^2 &\equiv& A &\pmod{p^{q-k}}\\
\end{eqnarray*}

现在问题就变成了求解 x_0^2 \equiv A \pmod{p^{q-k}},~ (A, p)=1

最后,当我们求出 x_0 时,因为 x_0 是在 \bmod p^{q-k} 意义下的,所以最后方程 (\ref{quadratic}) 的解可以表示为

x \equiv p^{\frac{k}{2}}\cdot \left(x_0 + t \cdot p^{q-k}\right) \pmod{p^q}, ~t \in \mathbb{Z}


为了方便我们在下面仍然当作在求 x^2 \equiv A \pmod{p^q},~ (A, p)=1

我们尝试将 A 套用 p 是奇素数时的推理,首先是欧拉准则

现在来看欧拉准则在 \bmod p^q 时是否仍然成立

首先,由于 \bmod p^q 的原根一定存在,所以我们找一个原根 g,用 g^r~(1 \leq r \leq \phi(p^q)) 来表示 \bmod p^q 中与 p^q 互质的所有数

1^\circ2 \mid r 时,g^r\bmod p^q 的二次剩余

2^\circ2 \nmid r

假设存在 m 使得 g^r \equiv g^{2m} \pmod{p^q}

这样就会有 r \equiv 2m \pmod{\phi(p^q)} \Rightarrow r = 2m + k\cdot \phi(p^q)

因为 r 是奇数,2mk\cdot \phi(p^q) 是偶数,所以与假设矛盾

又因为 (g^r, p^q)=1,所以不存在 v 使得 g^r \equiv g^{2m}\cdot p^v \pmod{p^q}

这样所有的 g^r, 2 \nmid r 都是二次非剩余

然后对于 \bmod p^q 中与 p^q 互质的所有数中的一个二次剩余 g^{2k},有

 \left(g^{2k}\right)^{\frac{\phi(p^q)}{2}} = \left(g^k\right)^{\phi(p^q)} \equiv 1 \pmod{p^q}

对于 \bmod p^q 中与 p^q 互质的所有数的一个二次非剩余 g^{2k+1},有

 \left(g^{2k+1}\right)^{\frac{\phi(p^q)}{2}} = \left(g^k\right)^{\phi(p^q)}\cdot g^{\frac{\phi(p^q)}{2}} \equiv g^{\frac{\phi(p^q)}{2}} \pmod{p^q}

然而因为 g\bmod p^q 的原根,因此 g^{\frac{\phi(p^q)}{2}}g^{\phi(p^q)} 不同余,又因为后者为 1,所以前者为 -1

至此,证明了在 \bmod p^q 下的欧拉准则为

 a^{\frac{\phi(p^q)}{2}} \equiv \left(\frac{a}{p^q}\right) \pmod{p^q}, ~~(a, p)=1

因此,只要在奇素数的情况证明中设 \phi(p^q)=2^t\cdot s, (2 \nmid s),然后将 p-1 换成 \phi(p^q),剩下步骤完全相同!

2的幂


现在是 \bmod 2^q 的情况

仿照奇素数的幂的情况我们设 a = 2^k\cdot A, ~2 \nmid A, ~k < q 类似的可以证明 1^\circ 如果 2 \nmid kk < q,在这种情况下,a\bmod 2^q 的二次非剩余 2^\circ 如果 2 \mid kk < q,在这种情况下,如果 A\bmod 2^q 的二次剩余,那么 a 就是,否则就不是 类似的,把问题变成求 x_0^2 \equiv A \pmod{2^{q-k}},~ (A, 2)=1 最终方程 (\ref{quadratic}) 的解将会是

x \equiv 2^{\frac{k}{2}}\cdot \left(x_0 + t \cdot 2^{q-k}\right) \pmod{2^q}, ~t \in \mathbb{Z}


那现在就来解这样的方程


\begin{equation}
\label{mod2}
x^2 \equiv A \pmod{2^q},~(A, 2) = 1
\end{equation}

1^\circq = 1 时,当且仅当 A = 1 时有一个解 x \equiv 1 \pmod 2

2^\circq = 2 时,当且仅当 A = 1 时有两个解 x \equiv \pm 1 \pmod{2^2}

3^\circq > 2 时,我们找几个 q 值列举出使得方程 (\ref{mod2}) 有解的 A

q = 3 1
q = 4 1,~9
q = 5 1,~9,~17,~25
q = 6 1,~9,~17,~25,~33,~41,~49,~57

我们发现方程 (\ref{mod2}) 有解的充要条件似乎是 A \equiv 1 \pmod 8

必要性:若方程 (\ref{mod2}) 有解,那么存在正整数 z 使得 z^2 \equiv A \pmod{2^q}

因为 (2, A) = 1 所以有 (2, z) = 1

z = 2k + 1,那么 (2k+1)^2 = 4k^2+4k+1 \equiv A \pmod{2^q}

因为 2^q \geq 8 所以 4k^2+4k+1 \equiv A \pmod 8

又因为 4k^2+4k = 4k(k+1) \equiv 0 \mod 8 所以 A \equiv 1 \pmod 8

充分性:从下面的求解过程可以证明


a)q = 3

\begin{equation} \label{mod2_q3} x^2 \equiv A \pmod{2^3} \end{equation}

方程 (\ref{mod2_q3}) 仅当 A = 1 时有解 x \equiv \pm 1, \pm 5 \pmod{2^3}

或者我们可以表示为 x = \pm \left( x_3 + 2^2\cdot t_3 \right), ~t_3 \in \mathbb{Z}, ~x_3 = 1, 5

b) 假设当 3 \leq q < k 时方程 (\ref{mod2}) 有解且解为

\begin{equation} \label{mod2_x} x = \pm \left( x_k + 2^{k-1}\cdot t_k \right), ~t_k \in \mathbb{Z} \end{equation}

那么对于 q=k-1 以及 q=k

\begin{equation} \label{mod2_qk1} x^2 \equiv A \pmod{2^{k-1}} \end{equation}

\begin{equation} \label{mod2_qk0} x^2 \equiv A \pmod{2^k} \end{equation}

为了方便,后面开始记 A_i = A \bmod 2^i 我们知道方程 (\ref{mod2_qk1}) 的解是

\begin{equation}\label{mod2_sol} x = \pm \left( x_{k-1} + 2^{k-2}\cdot t_{k-1} \right), ~t_{k-1} \in \mathbb{Z} \end{equation}

对于一个满足 (\ref{mod2_qk1})x_0 来说,当在 \bmod 2^k 意义下时,x_0^2 有可能会是 A_{k-1}A_{k-1} + 2^{k-1} 又因为 A_{k-1}A_{k-1} + 2^{k-1}\bmod 2^{k-1} 意义下等价,所以在这时候就会出现一些 t_{k-1} 使得 x^2 \equiv A_{k-1} \pmod{2^k},另外一些使得 x^2 \equiv A_{k-1} + 2^{k-1} \pmod{2^k},现在要求的就是使得 x^2 \equiv A_k \pmod{2^k} 的那些 t_{k-1} 值 我们可以将 (\ref{mod2_sol}) 代入 (\ref{mod2_qk0})


\begin{eqnarray*}
\left( x_{k-1} + 2^{k-2}\cdot t_{k-1} \right)^2 &\equiv& A_k &\pmod{2^k} \\
x_{k-1}^2 + 2^{k-1}\cdot t_{k-1} &\equiv& A_k &\pmod{2^k} \\
2^{k-1}\cdot t_{k-1} &\equiv& A_k-x_{k-1}^2 &\pmod{2^k} \\
t_{k-1} &\equiv& \frac{A_k-x_{k-1}^2}{2^{k-1}} &\pmod 2 
\end{eqnarray*}

t_{k-1} = \frac{A_k-x_{k-1}^2}{2^{k-1}} + 2\cdot t_k, ~t_k \in \mathbb{Z}

然后把这个结果代入 (\ref{mod2_sol}) 就能得到

x = \pm \left( x_{k-1} + \frac{A_k-x_{k-1}^2}{2} + 2^{k-1}\cdot t_k \right)

因为 (A_k, 2) = 1x_{k-1}^2 \equiv 1 \pmod 8,所以 A_k-x_{k-1}^2 是偶数,所以 \frac{A_k-x_{k-1}^2}{2} 是整数,所以方程有解(这证明上面的充分性) 这样,记 x_k = x_{k-1} + \frac{A_k-x_{k-1}^2}{2},便得出

x = \pm \left( x_k + 2^{k-1}\cdot t_k \right), ~t_k \in \mathbb{Z}

最后为了要解方程 (\ref{mod2}),只需从 q=3 起往上递推就可以得到所有的解了(这里刚好会有 4 个解) 下面是核心部分的伪代码 x \leftarrow \pm 1, \pm 5 k \leftarrow 4 while(k \leq q)     x \leftarrow \frac{A \bmod 2^k - x^2}{2} \bmod p     k \leftarrow k + 1

合数


现在解决 p 是合数时的情况

首先我们对 p 分解质因子,得到 p = \prod p_i^{q_i}

然后列出如下同余方程组


\begin{eqnarray*}
\left\{
\begin{aligned}
x_1^2 \equiv & a  \pmod{p_1^{q_1}} \\
x_2^2 \equiv & a  \pmod{p_2^{q_2}} \\
           &\vdots                \\
x_n^2 \equiv & a  \pmod{p_n^{q_n}}
\end{aligned}
\right.
\end{eqnarray*}

分别解出 x_1, x_2, \cdots, x_n,使用中国剩余定理合并即可

即解同余方程组


\begin{eqnarray*}
\left\{
\begin{aligned}
x \equiv &x_1 \pmod{p_1^{q_1}} \\
x \equiv &x_2 \pmod{p_2^{q_2}} \\
&\vdots \\
x \equiv &x_n \pmod{p_n^{q_n}}
\end{aligned}
\right.
\end{eqnarray*}

至此,二次剩余问题已经完整解决

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2014/08/quadratic-residue

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

4 thoughts on “[数论]二次剩余及计算方法

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.