2019-09-18 | 研究与探索 | UNLOCK

密码学与二次剩余笔记

二次剩余

当 $x^2\equiv a \pmod{n}$ 有解,称 $a$ 是模 $n$ 的二次剩余,以下大多讨论 $n$ 是奇素数($\mathbb{P}_{odd}$)时的情况。

对于 $n \in \mathbb{P}_{odd}$,$1$ 到 $n-1$ 中正好有 $\frac{n-1}{2}$ 个二次剩余。

对于 $n \in \mathbb{P}_{odd}$,设 $a$,$b$ 为模 $n$ 的二次剩余,$i$,$j$ 不是模 $n$ 的二次剩余,则 $ab$,$ij$ 是二次剩余,而 $ai$ 不是二次剩余。证明过程要用到一点群论知识,$\mathbb{Z}^{+}_n$ 关于乘法成群,符合重排定理;易证两二次剩余之积为二次剩余,则 $a$ 的陪集中有一半($a$ 与二次剩余的积)为二次剩余,剩下一半($a$ 与非二次剩余的积)为非二次剩余,同理 $i$ 的陪集中有一半为非二次剩余,剩下的是二次剩余。

欧拉准则

对于 $n \in \mathbb{P}_{odd}$,$a$ 是一个模 $n$ 的二次剩余当且仅当

勒让德(Legendre)符号

$p \in \mathbb{P}_{odd}$,定义

对于 $n \in \mathbb{P}_{odd}$,有定理:

但等式成立时 $n$ 不一定为素数。

雅可比(Jacobi)符号

设 $n$ 为正奇数,且 $n$ 的因式分解为:

那么雅可比符号定义为:

右边为勒让德符号。

重要区别:

  • 勒让德符号是定义性的,只能用于奇素数;雅可比符号是计算性的,可以用于任何正奇数。
  • 雅可比符号下 $\left(\frac{a}{n}\right)$ 为 1 并不能保证 $a$ 是 $n$ 的二次剩余。
    设 $p$,$q$ 为素数,$a$ 是 $n=pq$ 的二次剩余,则 $a$ 必定也是 $p$ 和 $q$ 的二次剩余,因为 $(a-x^2)|n \Rightarrow (a-x^2)|p$,对 $q$ 同理,然而由雅可比符号定义可知,$a$ 同时是 $p$ 和 $q$ 的非二次剩余时,$\left(\frac{a}{n}\right)=(-1)\times(-1)=1$。

二次同余方程的解

$x^2\equiv n \pmod{p}\ , p \in \mathbb{P}_{odd}$ 的解为 $x\equiv (a+\sqrt{\omega})^{\frac{p+1}{2}}$,其中 $\omega=a^2-n$ 是 $p$ 的二次剩余,$a$ 可随机选取,期望次数为 2。

注意到 $\omega$ 虽然是非二次剩余,但只要 $n$ 的确是二次剩余,在最终计算结果中 $\sqrt{\omega}$ 就会消去,就像虚数一样。

密码学应用

用勒让德符号计算 $(\ast)$ 时,等式不成立则 $n$ 一定是合数,等式成立 $n$ 却不一定是素数,但是会增加 $n$ 是素数的概率。这样就有了区别于费马小定理的素数判别方法。

求解二次同余方程的算法可用于 Rabin 公钥密码系统。

雅可比符号计算方法及欧拉拟素数的讨论见《计算机安全与保密》(清华大学出版社,2013 年 2 月第 1 版)第 61 页。

参考:二次剩余入门 - Eiffel的博客 - CSDN博客