べき乗剰余に適したモンゴメリ法による剰余乗算法とそれを実現するシストリックアレー

岩村 恵市  松本 勉  今井 秀樹  

誌名
電子情報通信学会論文誌 A   Vol.J76-A   No.8   pp.1214-1223
発行日: 1993/08/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: 情報セキュリティ基礎
キーワード: 
剰余乗算,  べき乗剰余演算,  モンゴメリ法,  RSA暗号,  シストリックアレー,  並列処理,  高速化,  装置化,  

本文: PDF(641.1KB)>>
論文を購入




あらまし: 
モンゴメリ法は除算を行うことなしに剰余乗算を演算する手法として知られており,モンゴメリ法を実行するシストリックアレーがいくつか提案されている.しかし,モンゴメリ法は出力のビット数が入力のビット数より大きくなる場合があるために,従来の手法はモンゴメリ法を実行するたびにその出力値の大きさを判定し補正する必要があり効率的ではなかった.そこで,本論文ではモンゴメリ法を行うたびの出力の補正を必要としないための条件を一般的に導き,その条件下でのモンゴメリ法を実行するシストリックアレーを提案する.このアレーは筆者らが以前に提案した剰余乗算に対するシストリックアレーよりも効率的であり,チップ化等の装置化に対しても有効であり実用的である.