メモ

yukicoderでゆるふわgolf

Tonelli–Shanks algorithm

この記事ではTonelli–Shanks algorithmの原理の「気持ち」を説明します。
間違った説明はしていないつもりですが、(故意に)不正確な記述があるかもしれません。
ループ不変量に着目する考え方はmod_sqrtについて.md · GitHubを参考にしました。
(追記:上記サイトの更に参考元である英語版wikipediaにも同様の記述がありました)
アルゴリズムの説明のみであり、実装については一切説明していません。


まずは次のような問題を考える
問題:群(G,+)G\cong\mathbb{Z}/2^s\mathbb{Z}とする(s>0)。x \in Gが与えられる。g+g=xとなるg \in Gを求めよ。
(そのようなgが存在するようなxが与えられるものとする)
計算できるのは加法(定数倍)のみであり、割り算はできない。ではどうすればよいか。

\mathbb{Z}/2^s\mathbb{Z}の代表元を0~2^s-1とし、Gの元をこれらと同一視する。
 補題t \in Gが与えられた時、tの末尾に0が何bit続くか求めることができる。
 証明:0になるまで2倍して(=左ビットシフトして)、その回数をsから引くことで分かる。
この補題から「xの下位bitを見ながら順にgを構成する」という方針を思いつくが、これはうまくいかない。
例えばs=6、x=44で考える。(x=0b101100)
まずxの1bit目が0なのでgの0bit目は0。
次にxの2bit目が1なのでgの1bit目は1。
そしてxの3bit目は……と考えたいが、2bit目を0にしないと3bit目は見れない。しかし、2bit目だけを変える元(2^s-4)を見つけるのは難しい。困った……。

そこで発想を転換して「誤差項tを用意して、2r=x+tが常に保たれている状態のまま、tを0にする」という方法を考える。
等式を満たす初期値としてr=t=xが取れる。tを0にするには下位bitから消していけば良い。
まず奇数c \in Gを勝手にとる。奇数か偶数かの判定は上述の補題により行う。Gの元の半分は奇数なので、ランダムに選ぶことで十分すばやくそのようなものが取れる。
tのk bit目を消すためにcの2^k倍をtに加えるが、この時、rにもcの2^(k-1)倍を加えることで等式2r=x+tを保ったままにすることができる。
(tの初期値はxなので最下位bitは0であるから、k>0であることに留意する)
先ほど同様s=6、x=44を例としよう。cは奇数から勝手にとって良いので例えば13とする。
c=001101 ←適当に選ぶ
t=101100 ←初期値はx
r=101100 ←初期値はx
まずtの2bit目を消したいのでtにcを2^2倍して加える。同時にrにcを2^1倍して加える
c=001101
t=100000
r=000110
次にtの5bit目を消したいのでtにcを2^5倍して加える。同時にrにcを2^4倍して加える
c=001101
t=000000
r=010110
t=0となったのでこうして2r=xとなるrが求められた。
(当たり前だがもう1つの解は最上位bitを反転させることで得られるのでcの2^(s-1)倍を加えれば良い)


ではTonelli-Shanks Algorithmを使う元の問題を考えてみよう
問題:pを奇素数とし、群GをG=(\mathbb{Z}/p\mathbb{Z})^*とする。x \in Gが与えられる。g^2=xとなるg \in Gを求めよ。
(そのようなgが存在するようなxが与えられるものとする)
p-1=q2^sとする(qは奇数)
pが奇素数のとき(\mathbb{Z}/p\mathbb{Z})^*\cong \mathbb{Z}/(p-1)\mathbb{Z}なのでq=1なら、先ほどの問題と全く同じ状況になることが分かる。
q≠1の場合も、次のように細部を調整することで先ほどの場合に帰着できる。(以下ではGを\mathbb{Z}/q2^s\mathbb{Z}とみてその演算を加法的に書いている)
tの初期値をqx、rの初期値を((q+1)/2)xとする(qは奇数なので((q+1)/2)は整数)
cは(奇数)*(q)から勝手にとる。(奇数を取ったのちq倍すればよい)
こうすると、c,t,rはいずれも位数2^sの元となる。