電波通信

I'm on the Top. of the world.

The Tonelli-Shanks algorithm

有限素体において平方根を求めるアルゴリズムを紹介します.

 有限素体,すなわち整数を素数を法として割った体のことですが,その中で平方剰余になっている元の平方根を求めるアルゴリズムを紹介します.数学的には平方剰余だとわかっている時点で平方根が存在することがわかるので計算しなくても良いことが多いように思うし総当たりすればいつかは求められると思うのですが,最近プログラミングを勉強し始めて有限体で平方根を求めるTonelli--Shanksのアルゴリズムを知ったので紹介します.

ついでに平方根だけではなく一般に累乗根を求めるアルゴリズムも紹介します.(Adleman-Manders-Miler algorithm)

 

PDFはこちら

www.dropbox.com