tonelli-shanks algorithmとは 意味・読み方・使い方

意味・対訳 トネリ・シャンクスのアルゴリズム (英：Tonelli-Shanks algorithm、シャンクス自身は RESSOL アルゴリズムと呼んでいる) は、奇素数 p {\displaystyle p} を法とする合同算術(剰余算、モジュラー算法、mod算) において、与えられた整数 n {\displaystyle n} (平方剰余) について合同式 r 2 = n ( mod p ) {\displaystyle r^{2}=n{\pmod {p}}} の解(つまり n {\displaystyle n} の平方根 r {\displaystyle r} )を多項式時間( O ( ( log 2 ⁡ p ) 4 ) {\displaystyle O({(\log _{2}p)}^{4})} のオーダー)で求めるためのアルゴリズムである。