Division Step改良による逆元計算の効率化


          

刊名：電子情報通信学会技術研究報告
作者：池田暢哉（大阪大学工学研究科）
宮地充子（大阪大学工学研究科）
刊号：734D0133-44
ISSN：0913-5685
出版年：2019
年卷期：2019, vol.119, no.475
页码：45-50
总页数：6
分类号：TN91
关键词：ユークリッドアルゴリズム；Gcd；逆元計算；定数時間計算
参考中译：
语种：jpn
文摘：有限体上の逆元計算は公開鍵暗号の暗号化や復号に用いられる重要な数学的演算の一つである．逆元計算は他の数学的演算と比べて計算量が大きいため，多くの暗号計算において計算量の大きな割合を占めている．このため，逆元計算の高速化は暗号化や復号全体の高速化において重要な課題である．有限体上の逆元を計算するための手法はフェルマーの小定理を用いる手法と拡張ユークリッドの互除法を用いる手法が存在する．最近まで，フェルマーの小定理を用いる手法は他方と比べてより効率的であると考えられていたが，BernsteinとYangの研究によってフェルマー法ベースの手法より高速なユークリッドベースの手法が新たに示された．今回の研究では，この手法を改良して逆元計算を従来より高速に行うためのアルゴリズムを示し，これらの性能評価を行う．



©2016机械工业出版社（机械工业信息研究院） 京ICP备05055788号-35