Tonelli–Shanks算法

Tonelli-Shanks算法是一个求解二次平方根的算法。即,对于奇素数p,和p的一个二次剩余n,求解x^2≡n (mod p)这样的方程。“n是二次剩余”是什么意思呢?就是这个方程有解,如果没解,就叫“二次非剩余”……


关于二次剩余,有一个叫“勒让德符号”(Legendre symbol)的玩意,它能判断对于奇素数p,a是否为p的二次剩余。懒得贴图片,把它写成L(a,p),其定义就是:

L(a,p)≡a^(
(p-1)/2 ) (mod p),这个值有-1,0,1三种可能。如果a不是p的二次剩余,这个值就是-1;如果a是0,这个值就是0;如果a是p的二次剩余,这个值就是1。

这叫做“欧拉判别法”(Euler’s criterion)。证明如下:

如果a=0,结论是显然的。

否则,由费马小定理,a^(p-1)≡1
(mod p),即:

(
a^( (p-1)/2 )-1 )*( a^( (p-1)/2 )+1 )≡0 (mod p)

由于p是素数,等式左边的两项中有一项模p余0.(p≠2,所以不可能两项都模p余0)

如果a是二次剩余,即存在x使得a≡x^2
(mod p),则显然x≠0,

a^( (p-1)/2 )≡x^2^(
(p-1)/2 )≡x^(p-1)≡1
(mod p).

因此,模p的每个二次剩余a都能使第一项为零。自然地,每个二次非剩余都会使第二项为零。

证毕。


回到我们的Tonelli-Shanks算法。算法如下:

输入:奇素数p,模p的一个二次剩余n(意味着勒让德符号L(n,p)=1).

输出:整数R,使得R^2≡n
(mod p,以下默认)

算法步骤:

①从p-1中除去所有因子2,设p-1=Q*2^S,其中Q是奇数(也就是除去所有因子2的结果)。如果S=1,即p≡3
(mod 4),那么直接返回R=±n^( (p+1)/4 ).

②选择一个z,使得勒让德符号L(z,p)= -1(即,z是p的二次非剩余),令c≡z^Q.

③令Rn^(
(Q+1)/2 ), tn^Q, M=S.

④循环:

1.若t1,返回R,程序终止。

2.否则,找出最小的i,使得0≡1。可以重复做平方完成这一点。

3.令b≡c^2^(M-i-1),令R≡R*b,tt*b^2,c≡b^2,M=i.

如果得到了一个解R,另一个解就是p-R。


算法正确性证明:

我们知道p-1=Q*2^S。令r≡n^(
(Q+1)/2 ),t≡n^Q,注意到r^2≡nt,这一同余式在每次循环中都保持正确。如果某时刻t≡1,那就有r^2≡n,于是我们找到了n的二次平方根R≡±r,算法终止。

如果t模p不等于1,那么考虑二次非剩余z。令c≡z^Q。则c^2^S≡(z^Q)^2^S≡z^(Q*2^s)≡z^(p-1)≡1.并且c^2^(S-1)≡z^(
(p-1)/2 )≡-1.这意味着c的阶是2^S.

类似地,t^2^S≡1,故t的阶能整除2^S.设t的阶是2^S’,由于n是模p的二次剩余,S’<=S-1.

现在令b≡c^2^(S-S’-1),r’≡b*r,c’≡b^2,t’≡c’t。和先前一样,r’^2≡n*t’仍然成立。但现在t和c’的阶数都是2^S’。这意味着t’的阶数2^S”满足S”

若S”=0,则t’≡1,算法终止,返回二次平方根±r’。否则,我们重新执行循环,定义b’,r”,c”和t”……直到停止。由于S序列严格递减,算法一定能结束。


算法复杂度:

平均2m+2k+S(S-1)/4+1/(2^(S-1))-9次乘法取模,其中m是p的二进制位数,k是p的二进制表示中1的数量。如果二次非剩余z的取法是随机选数,那么平均需要计算2次勒让德符号。因为随机选取一个数,是二次剩余的概率为((p+1)/2)/p=(1+1/p)/2,这个数小于1但略大于1/2。因此计算勒让德符号的期望次数是2.

换言之,我们将复杂度粗略估计为log^2(p),其中p是素数。


本文主要译自wiki有关章节。很惭愧,做了一点微小的工作,谢谢大家。

发表评论

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