Tonelli-Shanks Algorithm
Tonelli-Shanks は素数 p を法とする平方剰余の平方根、つまり x^2≡n (mod p) の解 x を計算する。
目的
素数法での平方根を計算する。楕円曲線の点圧縮や数論で使われる。
メカニズム
p=2 または p≡3 (mod 4) なら直接解がある。一般には p-1=2^s*q と書き、平方非剰余 z を見つけて c=z^q と置き、指数が 1 に下がるまで反復的に調整する。計算量は O(s^2 log p) である。
ユースケース
- 楕円曲線上の点のデコード
- モジュラー平方根の計算
- 数論的アルゴリズム