公開鍵暗号に用いられるRSAや楕円曲線暗号などでは， 多倍精度計算が用いられるとはいえ，比較的小さな整数計算を扱うため， 漸近計算量通りにアルゴリズムの速度が出るとは限らない． 逆にいうと，漸近計算量がたとえ悪くても，性能のよい 数論アルゴリズムの登場の余地が多いにあるといえる． そこで，公開鍵暗号に用いられる主要な方法において， この比較的小さい整数の倍精度計算について を中心に解説する．
プログラムに戻る ．