二次剩余

信息学奥林匹克数学竞赛

我退学吧

算法概述

二次剩余求的其实是x^2 \equiv n (\mod p)要求求得x的值。

信息学竞赛没有证明!!

判断n\bmod p是否存在二次剩余,需要用到欧拉准则:
因为欧拉定理是x^{\varphi(p)} \equiv 1 (\mod p)因为这里的p是奇质数,因此x^{p-1} \equiv 1(\mod p),然后对x^{p-1}进行开方操作x^{\frac{p-1}{2}},在虚数域中x^{\frac{p-1}{2}} \equiv \pm 1 (\mod p) 如果等于1则可以开方,如果等于-1显然不可以开方,所以这样子判断是否有二次剩余就好了。

算法流程

给出n,p,我们首先取一个数a,这个a是随机取得。然后我们对a^2-n进行开方操作,直到开不了方为止。即找到一个a满足(a^2-n)^{\frac{p-1}{2}} \equiv -1 (\mod p)

即使是随机找a,也不会找很久

定理1:

x^2 \equiv n (\mod p)中有\frac{p-1}{2}n能使方程有解

\to : x^2 \equiv n (\mod p),如果存在不同的数u,v,使他们带入x后可以有解,那么很显然满足p|u^2-v^2,所以满足p|(u+v)(u-v),因为p|u^2-v^2p不可能整除u-v,所以p可以整除u+v,那么这样的数有\frac{p-1}{2}个。因此随机到一个需要的a的期望是2

然后我们需要建立一个类似复数域的东西。我们平常的数学中有i^2=-1,我们需要建立一个类似的域,因此定义\omega=\sqrt {a^2-n},所以满足\omega^2=a^2-n,像正常复数那样开一个结构体重载一下运算符就好了。注意要使\omega^2=a^2-n

定义出这个复数域的作用是x \equiv (a+\omega)^{\frac{p-1}{2}} (\mod p)

然后需要证明一些东西。。。

定理2:
\omega^p \equiv -\omega (\mod p)

证明:\omega^p \equiv \omega \times \omega^{p-1}\equiv \omega \times \omega^{2^{\frac{p-1}{2}}} \equiv \omega \times (a^2-n)^{\frac{p-1}{2}}\equiv -\omega (\mod p)

定理3:
(a+b)^p \equiv a^p+b^p (\mod p) (p \in P)

证明:直接用二项式定理化简得a^p+b^p+\sum_{i=1}^{n}{C_{n}^{i}a^ib^{n-i}} (\mod n) 然后把右边的组合数写成阶乘的形式发现总是会出现n的倍数,然后在同余n的意义下,就化成0了。即得证。

然后我们就可以操作一番了。
x^2 \equiv (a+\omega)^{p+1}
x^2 \equiv (a+\omega)\times(a+\omega)^p
x^2 \equiv (a+\omega)\times(a^p+\omega^p)
x^2 \equiv (a+\omega)\times(a-\omega) Notice:(a^{p-1}\equiv1(\mod p))
x^2 \equiv a^2 - \omega^2
x^2 \equiv n (\mod p)

由于本人是个蒟蒻。所以会的只有这么多了。
贴一个大爷对于素数,奇素数的幂,2的幂,合数的讨论的博客

6 thoughts on “二次剩余

  1. zjq!提问!
    定理1的$u^2-v^2 \mid p$,是$p \mid u^2 – v^2 $吧
    定理3公式倒数第二行…中间是不是减号

    1. 2333 , 我这个markdown很奇怪 , $这个符号要打两遍, \这个符号也要打两遍。
      谢谢指正,已修复QAQ

发表评论

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