二次剩余学习笔记

问题描述

给定一个式子\(x^2 \equiv n \pmod p\),求\(x\)的值。其中,如果\(x\)有解,则称\(n\)为\(p\)的二次剩余。

勒让德符号

首先,我们要先判断这个方成是否有根。在这里我们引入勒让德符号来进行判断。我们定义:

\[ \left( \frac{a}{p} \right) = \begin{cases} 1, a 为 p 的二次剩余 \\ -1, a 不是 p 的二次剩余 \\ 0, a \equiv 0 \pmod p \end{cases} \]

如何用运算来进行判别呢,接下来我们引入欧拉判别法:对于勒让德符号,有

\[ \left( \frac{a}{p} \right) = a^{\frac{p-1}{2}} \pmod p \]

证明:分类讨论以下几种情况

  • 当\(\left( \frac{a}{p} \right) \equiv 1 \pmod p \)时,转化式子为\(\sqrt{ a^{p-1} } \equiv 1 \pmod p\),根据费马小定理,得证。
  • 当\(\left( \frac{a}{p} \right) \equiv -1 \pmod p\)时,二次剩余不存在。化简为\( a^{\frac{p-1}{2}} \equiv -1 \pmod p\),不存在二次剩余时存在\(ij \equiv a \pmod p, i != j, i, j \in [1, p-1]\)。可以知道在数论中,有一共\(\frac{p-1}{2}\)对这样的\((i,j)\),所以勒让德式可进一步转换为\( (p-1)! \equiv -1 \pmod p \),根据威尔逊定理,得证。

Cipolla 算法

讲完了上面玄学判别式之后,我们来引进能计算二次剩余的 Cipolla 算法。首先,就像所有的二次方程一样,我们先需要验根,根据上面的判别法计算即可。之后,我们随机枚举一个\(c\),满足\(c^2-n\)的勒让德符号为\(-1\),并且设\(i=\sqrt{c^2-n}\)进行强行开根号(有点类似于虚数)。然后以下引理可以得出答案。

\[ x \equiv (n+i)^{\frac{p+1}{2}} \pmod p \]

证明:

\[ \begin{aligned} x^2 & \equiv (n+i)^{p+1} \\ & \equiv (n+i)(n+i)^p \\ & \equiv (n+i)(n^p+i^p) \\ & \equiv (n+i)(n^p + (c^2-n)^{\frac{p-1}{2}} * i) \\ & \equiv (n+i)(n^p – i) \\ & \equiv (n+i)(n-i) \\ & \equiv n \end{aligned} \]

在证明中有一些简便步骤,我在这里做一个解释和证明:

  • \((a+b)^n \equiv \sum^n_{i=0} C_n^i a^ib^{n-i} \equiv a^n+b^n \pmod p\),消去中间项的原因是组合数\(C_n^i\)的存在,提供了因子\(n\)。
  • 根据费马小定理,有\(a^p \equiv a \pmod p\)。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注