トネリ・シャンクスの
アルゴリズム (
英: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})} の
オーダー)で
求めるためのアルゴリズムである。