剰余系演算用高速アルゴリズムに関する研究

点击翻译按钮获取中文摘要

公開鍵暗号の暗号化・復号処理においては、大きな数を法とする剰余系演算が必要である。本研究では、種々の剰余系演算に対して、ハードウェア実現向きのアルゴリズムやカードコンピュータ等の超小型計算機向きの高速アルゴリズムを開発するとともに、これらの演算の計算複雑さを明らかにすることを目指して研究を行い、以下の成果を得た。1.剰余べき乗算の線形段回路アルゴリズムnビット剰余べき乗算が、理論的に、段数Ο((1+α)/αn)、素子数Ο(@S7n^<3+2α>@Kα log n@E7)(ただし、αは@S71@Klog n @E7以上の任意の数)の組合せ回路で計算できることを、実際に回路アルゴリズムを示すことにより明らかにした。この結果を第12回コンピュータ算術シンポジウムで発表するとともに、IEEE Transactions on Computers に投稿した。2.剰余除算のハードウェアアルゴリズム剰余除算に対して、ハードウェアア実現向きのアルゴリズムを二つ提案した。この成果の一方を電子情報通信学会英文論文誌に投稿し、他方を電子情報通信学会の研究会で発表した。3.多倍長剰余乗算の高速アルゴリズム多倍長の剰余乗算のためのカードコンピュータ向きの高速アルゴリズムを開発した。この成果を電子情報通信学会英文論文誌に発表した。