二次剩余(Cipolla’s algorithm)学习笔记

先放资料。


 

前置技能点:
剩余系

剩余系:设模为m,则根据余数可将所有的整数分成m类,分别记成[0],[1],[2],[m-1]
m个数{0,1,2,m-1}称为一个完全剩余系,
每个数称为相应类的代表元。
当m=10(偶数)时候,则{0,1,2,3,4,5,6,7,8,9}是最小非负完全剩余系
{-5,-4,-3,-2,-1,0,1,2,3,4,5} 是绝对值最小完全剩余系
{-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小
{1,2,3,4,5,6,7,8,9,10}是最小正完全剩余系
简化剩余系:在每个剩余类选取至1个与m互素代表元构成简化剩余系。
当m=10则,{0,1,2,3,4,5,6,7,8,9} 完全剩余系
{1,3,7,9}是简化剩余系(x,10)=1
当m=5则,{0,1,2,3,4}为完全剩余系,
{1,2,3,4}是简化剩余系,因为除去余0(正好是倍数)外,其它都互素。
f(m)=欧拉函数=|{t|0<t<m, (t, m)=1}|
=简化剩余系的元素个数

维基百科_高斯引理

p为奇质数a是一个与p互质的整数。考虑以下数组:{\displaystyle a,2a,3a,\dots ,{\frac {p-1}{2}}a}以及它们对p最小非负剩余。这些剩余两两不等(kk:这些剩余两两不等的证明:可以考虑反证,假设两个不同的数x,y对于p同余, 那么x-y和0关于p同余,而x-y同时关于a同余,a与p互质,矛盾。因此这些剩余两两不等),因此我们共有\frac{p-1}{2}个两两不等的介于1和p(kk:这里似乎有问题,如果剩余是在1..p之间,那么前面应该是说最小正剩余而不是最小非负剩余,最小非负剩余应该是在0..p-1之间之间的整数:{\displaystyle t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}}}。设其中有n个数比p/2大,那么高斯引理声称:{\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n}}

上式左边是勒让德符号,当其值为+1时,表示a是模p的二次剩余;其值为-1时,表示a是模p的二次非剩余。

用通俗的语言来说,就是:{\displaystyle t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}}}里面比p/2大的有偶数个,那么a是模p的二次剩余,如果有奇数个,那么a是模p的二次非剩余。


正片:

维基百科_勒让德符号

定义:

勒让德符号({\tfrac {a}{p}})(有时为了印刷上的方便,写成(a|p))有下列定义:

\left({\frac {a}{p}}\right)={\begin{cases}\quad 0\\+1\\-1\end{cases}} 如果a\equiv 0{\pmod {p}}
如果a\not \equiv 0{\pmod {p}},且对于某个整数x,x^{2}\equiv \;a{\pmod {p}}
如果不存在整数x,使得x^{2}\equiv \;a{\pmod {p}}

如果(a|p) = 1,a 便称为二次剩余(mod p);如果(a|p) = −1,则 a 称为二次非剩余(mod p)。通常把零视为一种特殊的情况。

性质:

勒让德符号有许多有用的性质,可以用来加速计算。它们包括:

  • \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)(它是一个完全积性函数(kk:g(a)*g(b)=g(a*b)对于任意正整数a,b都成立,不需要gcd(a,b)=1,完全积性真是爽哭了。。。。)。这个性质可以进一步理解为:两个剩余或非剩余的乘积是剩余,一个剩余与一个非剩余的乘积是非剩余。(kk:因为负负得正,正正得正…))
  • 如果ab (mod p),则\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)
  • \left({\frac {a^{2}}{p}}\right)=1
  • {\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}+1{\mbox{ if }}p\equiv 1{\pmod {4}}\\-1{\mbox{ if }}p\equiv 3{\pmod {4}}\end{cases}}}

这个性质称为二次互反律的第一补充。

  • {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}7{\pmod {8}}\\-1{\mbox{ if }}p\equiv 3{\mbox{ or }}5{\pmod {8}}\end{cases}}}

这个性质称为二次互反律的第二补充。一般的二次互反律为:

  • 如果pq是奇素数,则\left({\frac {q}{p}}\right)=\left({\frac {p}{q}}\right)(-1)^{{{\frac {p-1}{2}}{\frac {q-1}{2}}}}.

参见二次互反律二次互反律的证明

以下是一些较小的p的值的公式:

  • 对于奇素数p\left({\frac {3}{p}}\right)=(-1)^{\left\lceil {\frac {p+1}{6}}\right\rceil }={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}11{\pmod {12}}\\-1{\mbox{ if }}p\equiv 5{\mbox{ or }}7{\pmod {12}}\end{cases}}
  • 对于奇素数p\left({\frac {5}{p}}\right)=(-1)^{\left\lfloor {\frac {p-2}{5}}\right\rfloor }={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}4{\pmod 5}\\-1{\mbox{ if }}p\equiv 2{\mbox{ or }}3{\pmod 5}\end{cases}},

但一般直接把剩余和非剩余列出更简便:

  • 对于奇素数p\left({\frac {7}{p}}\right)={\begin{cases}+1{\mbox{ if }}p\equiv 1,3,9,19,25,{\mbox{ or }}27{\pmod {28}}\\-1{\mbox{ if }}p\equiv 5,11,13,15,17,{\mbox{ or }}23{\pmod {28}}\end{cases}}

勒让德符号(a|p)是一个狄利克雷特征(mod p)。

计算勒让德符号的一个例子:

\left({\frac {12345}{331}}\right)

=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right) (完全积性)

=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right) (161和823关于331同余)

=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right) (完全积性)

=(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right) (二次互反律)

=-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right) (同余数)

=-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3}{23}}\right)^{2} (完全积性,平方的形式值一定为1)

=-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1. (分别计算,可以参考小素数时的分段函数,具体的计算方法见下文)

 

维基百科_欧拉准则(用来计算勒让德符号)

p是奇质数p不能整除d,则:

d是模p的二次剩余当且仅当{\displaystyle d^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}
d是模p的非二次剩余当且仅当:{\displaystyle d^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}

勒让德符号表示,即为: {\displaystyle d^{\frac {p-1}{2}}\equiv \left({\frac {d}{p}}\right){\pmod {p}}}

例子一:对于给定数,寻找其为二次剩余的模数

a = 17。对于怎样的质数p,17是模p的二次剩余呢?

根据判别法里给出的准则,我们可以从小的质数开始检验。

首先测试p = 3。我们有:17(3 − 1)/2 = 171 ≡ 2 (mod 3) ≡ -1 (mod 3),因此17不是模3的二次剩余。

再来测试p = 13。我们有:17(13 − 1)/2 = 176 ≡ 1 (mod 13),因此17是模13的二次剩余。实际上我们有:17 ≡ 4 (mod 13),而22 = 4.

运用同余性质和勒让德符号可以加快检验速度。继续算下去,可以得到:

对于质数p ={\displaystyle 13,19,\cdots },(17/p) = +1(也就是说17是模这些质数的二次剩余)。
对于质数p ={\displaystyle 3,5,7,11,23,\cdots },(17/p) = -1(也就是说17是模这些质数的二次非剩余)。
kk:简单得说,就是从小到大枚举质数p,验证a^((p-1)/2))%p等于1还是-1.)

 

例子二:对指定的质数p,寻找其二次剩余

哪些数是模17的二次剩余?

我们可以手工计算:(kk:手算考虑数的平方是因为,勒让德符号是完全积性函数&&\left({\frac {a^{2}}{p}}\right)=1

 

12 = 1
22 = 4
32 = 9
42 = 16
52 = 25 ≡ 8 (mod 17)
62 = 36 ≡ 2 (mod 17)
72 = 49 ≡ 15 (mod 17)
82 = 64 ≡ 13 (mod 17)

于是得到:所有模17的二次剩余的集合是{\displaystyle {1,2,4,8,9,13,15,16}}要注意的是我们只需要算到8,因为9=17-8,9的平方与8的平方模17是同余的:92 = (−8)2 = 82 ≡ 13 (mod 17).(同理不需计算比9大的数)。

但是对于验证一个数是不是模17的二次剩余,就不必将所有模17的二次剩余全部算出。比如说要检验数字3是否是模17的二次剩余,只需要计算3(17 − 1)/2 = 38 ≡ 812 ≡ ( − 4)2 ≡ − 1 (mod 17),然后由欧拉准则判定3不是模17的二次剩余。

 

 

维基百科_二次互反律

 

对于两个奇素数pq\left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)=(-1)^{{{\frac {(p-1)(q-1)}{4}}}}

其中\left({\tfrac {p}{q}}\right)勒让德符号

 

关于二次互反律的证明就不多说了。。。据说高斯一次给出了五个(还是七个?),到现在一共有200+种证明。

 

然后。。。感觉。。。。二次互反律。。。。太神了。。。。太美了。。。。真的被震撼到了orz

 

wiki_Cipolla’s algorithm

acdreamer_二次同余方程的解
二次剩余Cipolla算法学习小记

说点什么

您将是第一位评论人!

提醒
wpDiscuz