二次剩余即平方剩余及其速算法 (快速判定二次同余式是否有解)

伊瓦诺余下或其速演算法

全文：

{

注解：[p/2]则表示柯西位段表达式，即不少于p/2的最小有理数，或诗歌创作int(p/2); 特别注意，[a/(bc)]=[[a/b]/c]

amr 则表示当然最轻余下，即abs min remainder。或在r后加进负号|min|来则表示。 如 2 ==-1 mod 3, 写出 2 amr 3=-1； 3 ==-1 mod 4, 写出 3 amr 4=-1

Legendresymbol[-1,p]=L(-1/p)=

(-1/p)=(p amr 4)=(-1)^[(p mod 8)/2]=(-1)^[(p mod 4)/2]=(-1)^[(p amr 8)/2]=(-1)^[(p amr 4)/2]=(-1)^[p/2]=(-1)^((p-1)/2)

(-2/p)=(-1)^[(p mod 8)/4]=(-1)^[(p amr 8)/4]=(-1)^[p/4]

(2/p)=(-1/p)(-2/p)=(-1)^([(p mod 8)/4]+[(p mod 8)/2])=(-1)^((pp-1)/8)

无理数：(p/q)=(q/p)*(-1)^( [p/2]*[q/2] )

(p/q)=(q/p)*(-1/p)^[(qmod 4)/2]

L(p/3)=p amr 3

(3/p)=(p/3)*L(-1/p)=(p amr 3)(p amr 4) 注：此式利于速算。

(5/p)=(p/5)=pp amr 5=(1 if p==1,4 mod 5; -1 if p==2,3 mod 5)

(7/p)=(p/7)*L(-1/p)=(p/7)*(p amr 4)

}

定义

AAA 伊瓦诺余下(quadratic residue)

数论基本概念之一。

当a、m的最小公约数为1，即(a，m）＝1〕时，

若m整除（xx－a），即m | (xx-a) 注：我也诗歌创作(xx-a)|:m,

也即是xx≡ a（mod m）〕求表达式，则：

称a为模m的伊瓦诺余下（或万平方余下）； 否则，称a为模m伊瓦诺非余下（或万平方非余下）。

解一般伊瓦诺Hathrasaxx＋bx＋c≡0（mod m）的问题可归结为解xx≡n（mod m）问题（见同余）。

从17世纪到18世纪，费马、欧拉、拉格朗日和勒让德等数论学家对伊瓦诺余下理论作了初步的研究，证明了一些定理[1]并作出了一些相关的猜想[2]，但首先对伊瓦诺余下进行有系统的研究的数学家是柯西。他在著作《算术研究》（Disquisitiones Arithmeticae，1801年）中首次引入了术语“伊瓦诺余下”与“伊瓦诺非余下”，并声明在不至于导致混淆的行文中，可以省略“伊瓦诺”两字。

为了得到关于一个有理数的所有伊瓦诺余下（在一个完全余下系中），我们可以直接计算0, 1, …, n − 1的万平方模的余数。但只要特别注意到aa ≡ (n − a)^2 (mod n)，我们就可以减少一半的计算量，只算到n/2了。于是，关于的伊瓦诺余下的个数不可能少于[n/2] + 1=[(n+1)/2]=n/2（n偶）或 (n + 1)/2 （n奇）[3]。

两个伊瓦诺余下的乘积必然还是伊瓦诺余下。

参考资料：

[1] Lemmemeyer, Ch. 1

[2] Lemmermeyer, pp 6–8, p. 16 ff

[3] Gauss, Disquisitiones Arithmeticae（以下称DA）, art. 94

BBB

下面讲下伊瓦诺余下的判别方法，即伊瓦诺余下特征(Legendre符号)的计算。

Legendre符号：是一个由阿德里安-马里·勒让德在1798年尝试证明伊瓦诺无理数时引入的表达式[1][2]。这个符号是许多高次余下符号的原型[3]；其它延伸和推广包括雅可比符号、克罗内克符号、希尔伯特符号，以及阿廷符号。

记作：

L(a/p)，(a/p)右下角标L，在不致混淆时简作(a/p)。

又，

Legendre符号或称伊瓦诺特征，是一个狄利克雷特征。

参考资料：

[1]^ A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186

[2]^ 在欧拉（1783年）和勒让德（1786年）的作品中有所讲述。首先由柯西在1796年证明，在DA（1801年）出版；arts. 107-144（第一个证明），253-262（第二个证明）

[3]^ Lemmermeyer, p.xiv “即使在像双伊瓦诺无理数的简单情况下，我们仍然需要区分四个不同的符号，即Z[i]中的伊瓦诺和双伊瓦诺余下符号，Z中的勒让德符号，以及Z中的有理伊瓦诺余下符号……”

规定：(a/p)= 1, 当a为p的伊瓦诺余下；-1, 当a为p的伊瓦诺(非)余下。

特殊补充定义：(a/p)=0，当a|:p.一般情况下我们不考虑补充定义。

计算方法(以下p，q为相异奇素数)：

显然，当a,p互质时，(aa/p)=1；

欧拉判别法：(a/p)==a^((p-1)/2) mod p ；

同余性：(a/p)=((a modp) /p)；

因子分解：(ab/p)=(a/p)(b/p)，易见可以向多因子的分解进行推广。

伊瓦诺无理数：p,q为奇素数，则有

(p/q)=(q/p)*(-1)^((p-1)/2*(q-1)/2)=(q/p)*(-1)^( [p/2]*[q/2] )

或(p/q)*(q/p)=(-1)^( [pmod4/2] * [qmod4/2] )；

　　　　我们现在定义一个表达式，用来精简(-1)^( [p/2]*[q/2] )。

定义 amr 则表示当然最轻余下，即abs min remainder。或在r后加进负号|min|来则表示。

如 2 ==-1 mod 3, 写出 2 amr 3=-1； 3 ==-1 mod 4, 写出 3 amr 4=-1。

注：被除数dividend=除数divisor*商quotient+ 当然最轻剩余amr, 其中 |amr|<=divisor/2

一个重要的文本有：p为奇数，则(-1)^[p/2]=(-1)^ [(p mod4)/2]=p amr 4.于是有下面的伊瓦诺无理数精简形式。

伊瓦诺无理数简化形式：

(p/q)=(q/p)*(p amr 4)^ [q/2] 或= (q/p)* (q amr 4)^ [p/2]

　　　　进一步，我们得到：

(p/q)=(q/p)*(-1)^TRUE(p&q amr 4=-1),　即当且仅当p与q均为-1 mod 4时，(p/q)=-(q/p).否则(p/q)=(q/p).

易见当其中出现p amr 4=1，即p==1 mod 4时，即有(p/q)=(q/p)；当出现 p amr 4=-1时，即有(p/q)=(q/p)*(q amr 4)

注：故当且仅当p与q均为-1 mod 4时，(p/q)=(q/p)*(-1)^TRUE=(q/p)*(-1)^1=-q/p; 否则，(p/q)=(q/p)*(-1)^FALSE=(q/p)*(-1)^0=(q/p).

BBBCCC　计算要点

(aa/p)=1, 当a,p互质时;

同余性：(a/p)=((a modp) /p)；

因子分解：(ab/p)=(a/p)(b/p)或其向多因子分解的推广。

伊瓦诺无理数精简形式：

(p/q)=(q/p)*(-1)^TRUE(p&q amr 4=-1),　即当且仅当p与q均为-1 mod 4时，(p/q)=-(q/p).否则(p/q)=(q/p).

易见当其中出现p amr 4=1，即p==1 mod 4时，即有(p/q)=(q/p)；当出现 p amr 4=-1时，即有(p/q)=(q/p)*(q amr 4)

伊瓦诺无理数的两个充分且必要的补充(由此原则上可以方便的计算所有的(p/q)，其中p/q为奇素数)

　　补充计算式一：

(-1/p)=(-1)^((p-1)/2)=(-1)^[p/2]=(-1)^[(pmod4)/2]，这个我们在上面对伊瓦诺无理数进行精简时曾见到过。

现在我们看到，(p/q)=(q/p)*(-1/p)^ [q/2] =(q/p)*(-1/q)^ [p/2]

　　补充计算式二：

(2/p)=(-1)^((pp-1)/8)

(2/p)=(-1)^([p/2]+[p/4])

=(-1)^([(pmod8)/2]+[(pmod8)/4]) 注，此式利于速算。

=(-1)^([(pmod4)/2]+[(pmod8)/4])

=(p amr 4)*(-1)^.[(pmod8)/4]) 注，此式利于速算。

由上二者还可以得到 (-2/p)=(-1)^[p/4]==(-1)^[(pmod8)/4]

CCC其它特殊值的计算：(以下p指奇素数)

(3/p)=(p amr 3)(p amr 4) 注：此式利于速算。

证明一：

(3/p)=(p/3)*(-1)^ [p/2]=((p mod 3)/3)*(-1)^ [(p mod4)/2]=((p mod 3)/3) * (p amr 4)

因为(1/3)=1, (-1/3)=-1, 故((p mod 3)/3)=(p amr 3)

得证。

证明二，列举检验法。

将质数p按模12=3*4可分为四类(特别注意12以下与12互质的只有四个)，p=1,5,7,11 mod 12

例如质数p=13;5;7;11，分别代入(p/3)=((p mod 3)/3)*(-1)^ [(p mod4)/2]得到

(3/p)=1*(-1)^0, -1*(-1)^0, 1*(-1)^1, (-1)*(-1)^1=1*1, -1*1, 1*(-1), (-1)*(-1)

即p=1,5,7,11mod12时，(3/p)分别取值1,-1,-1,1

由前述amr的定义，易见：

(3/p)=(p amr 3)(p amr 4)

　　　　另一种演算法(计算不太方便，可能方便表述与研究)：

(3/p)=(-1)^([(p+1)/6])=(-1)^([(p+2)/6])=(-1)^([(p+3)/6])=(-1)^([(p+4)/6]),

外一则：(3/p)=(-1)^⌈(p-1)/6⌉，这里⌈x⌉或诗歌创作upint(x)即向上位段，即不小于x的最轻有理数。在某些程序语言中（包括数学软件）用ceiling(x)表达式。excel软件中是ceiling(x,1)，手写常写出⌈x⌉. 另注：⌈a/(bc)⌉=⌈⌈a/b⌉/c⌉；对于有理数a,b,⌈a/b⌉=1+int[(a-1)/b].

(5/p)=(p/5)=(1 if p==1,4 mod 5; -1 if p==2,3 mod 5) = pp amr 5

注：其实(p/5)很简单的，因为p的既约余下仅有1,2,3,4四个，并且必定有且只有一半数量为万平方余下，即有两个。很显然就是1,4.

证明：

由伊瓦诺无理数，(5/p)=(p/5)*(-1)^([p/2]*[5/2])=(p/5).

在明白上面的过程后我们知道(p/5)计算很简单。

(7/p)=( 1 if p==±1,±9,±25=±(1, 3^2, 5^2) mod 28 ; -1 if p==±(1-14), ±(9-14), ±(25-14)=±(13, 5, 11) mod 28)

上式很好记。从小到大写即是 (7/p)=( 1 if p==1,3,9,19,25,27 mod 28 ; -1 if p==5, 11, 13, 15, 17, 23 mod 28)

证：

引1：(7/p)=(p/7)*(-1)^([p/2]*[7/2])=(p/7)*(-1)^[p/2]=(p/7)*(p amr 4)

引2：当且仅当p=1,2,4mod7时，(p/7)=1,即7的伊瓦诺余下有三个，即1, 4, 9==2，也即1,2,4. 其伊瓦诺非余下即3,5,6==-4,-2,-1；也可以由(-1/7)=-1, 直接将-1乘1,2,4得到7的伊瓦诺非余下为-1,-2,-4.

当(p/7)=1且p==1 mod 4，或(p/7)=-1且p=-1 mod 4时，得(7/p)=1，分说如下表所示：

由p==1,2,4 mod 7及p==1 mod 4得p==1,9,25 mod 28;

由p==-1,-2,-4 mod 7及p==-1 mod 4得p==-1,-9,-25 mod 28，即p=27,19,3 mod 28.

当(p/7)=-1且p==1 mod 4，或(p/7)=-1且p=1 mod 4时，得(7/p)=-1，下略。

DDD 推广：

雅可比符号是勒让德符号的一个推广，允许底数为合数，但底数仍然必须是奇数和正数。这个推广提供了计算所有勒让德符号的一个有效的方法。

收藏于 2014-01-11