情報処理学会 第86回全国大会 会期:2024年3月15日~17日

6K-02
CPythonへのToom-Cook乗算の実装
○山口進人,松尾和人(神奈川大)
プログラミング言語Pythonの標準インタープリター実装であるCPythonは,公開鍵暗号計算や数論アルゴリズムの計算に多用される多倍長整数演算を行うことができる.しかし,実装されている多倍長整数乗算アルゴリズムは筆算法とKaratusba法のみであり,より大きな整数に対して高速乗算が期待できるToom-Cook法は実装されていない.そこで,本研究ではToom-Cook法をCPythonに実装し,有効性を確認した.また,標準的なToom-Cook法に加え,Knuthの手法も実装し効率を比較した.