【課題】 所定の範囲の既知の素数のみに基づき、大きな対象数についても判定可能な素数判定方法、素数判定装置および素数判定プログラムを提供する。
【解決手段】 対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定方法であって、対象数Ｎの入力を受け付ける入力受付過程と、対象数Ｎを除する除数の範囲を定める範囲規定過程と、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定過程と、対象数Ｎが素数であるか否かの結果を出力する結果出力過程と、を備え、範囲規定過程は、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数Ｍ_Ｐとして、Ｎ^1/2／Ｍ_Ｐの小数点以下を切り上げた規定数Ｒを算出するものであり、素数判定過程は、整数を１からＭ_Ｐ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭ_Ｐを構成する素数を除いた素数列の数を除数とする。 （もっと読む）

【課題】 回路規模及び消費電力を増大させることなく外部からの消費電力解析が困難なセキュリティ性の高いモンゴメリ乗算回路を提供する。
【解決手段】 モンゴメリ乗算回路１は、メモリ回路１１、算術回路１０、及び、メモリ回路１１と算術回路１０間のデータの入出力を所定のアルゴリズムに基づいて制御してモンゴメリ乗算を実現する制御回路１２を備えて構成され、制御回路１２が、アルゴリズムを２以上有し、２以上のアルゴリズムの内の１つをランダムに選択して、選択した１つのアルゴリズムに基づいてモンゴメリ乗算の実行に係る制御を行う。 （もっと読む）

【課題】有限体の逆元を演算する逆元演算装置に関し，内部変数バッファオーバフローを発生させずに有限体の逆元演算を行うことが可能となる技術を提供する。
【解決手段】逆元演算装置１０において，入力部１１は，逆元を求める値Ｘと有限体の法Ｐとを入力し，中間変数Ａ，Ｂ，α，βの設定を行う。条件付中間変数交換部１３は，条件に応じて，Ａ−Ｂ間，α−β間での値の交換，Ａ−Ｂ間，α−β間での減算処理を行う。法符号調整部１４は，αの正負に応じて中間法変数Ｐ’に−ＰまたはＰを設定する。条件付法加算・シフト部１５は，αが奇数である場合にαにＰ’を加算し，Ａおよびαの値を１／２する。変換終了判定部１６は，Ａの値が１になれば中間変数変換部１２による処理の終了を判定する。中間変数符号調整部１７は，αが負である場合にαにＰを加算する。出力部１８は，最終的なαの値を求められた逆元として出力する。 （もっと読む）

【課題】剰余乗算器の演算ビット数の２倍を超えるビット数のデータに対する剰余乗算の演算効率を向上させることができるデータ処理装置を提供する。
【解決手段】演算部（３１０）により剰余乗算の演算処理を再帰的に複数回繰り返してｗビットの剰余乗算の剰余と商から、２ｗビットの剰余乗算の商と剰余を計算するとき、先の剰余乗算の演算処理で求めたｗビットの剰余乗算の剰余と商を、次の剰余乗算の演算処理に振り分ける制御を制御部（３２０）が行う。これにより、先の剰余乗算の演算処理がｗビットの剰余乗算の剰余だけを求める演算アルゴリズムに比べ、再帰的に行われる後の演算に必要な前の演算処理の商を新たに演算することを要しない。剰余乗算ユニットの演算ビット数の２の倍数のビット数のデータに対する剰余乗算の演算効率を向上させることができる。 （もっと読む）

【課題】楕円曲線暗号等に必要な種々の多倍長演算を高速に実行することが可能な多倍長演算装置を提供する。
【解決手段】演算対象となるｎワード長の整数や演算結果等を一時的に記憶するための２個のデュアルポートメモリ４１、４２からなるメモリ部４０と、ワード単位で加算及び乗算を含む２以上の種類の演算を実行し、１ワード長の演算結果を出力する演算部２０と、メモリ部４０から演算部２０に最大３つの１ワードデータを供給すると同時に、演算部２０からの１ワード長の演算結果をメモリ部４０に格納するメモリ入出力部３０と、演算部２０及びメモリ入出力部３０を制御することにより、演算部２０にｎワード長の加算剰余及びモンゴメリリダクションのいずれかの演算を実行させる制御を行う制御部１０とを備える。 （もっと読む）

【課題】処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行する。
【解決手段】乗算装置１０では、入出力部１２が各入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）を入力し、乗算装置制御部１３が入力値Ｂ（ｘ）（＝ｘ^(s-1)gＢ_s-1（ｘ）＋ｘ^(s-2)gＢ_s-2（ｘ）＋…＋ｘ^igＢ_i（ｘ）＋…＋ｘ^gＢ₁（ｘ）＋Ｂ₀（ｘ））を処理単位g毎に区切ってｓ個の値Ｂ_s-1（ｘ），…，Ｂ₀（ｘ）を作成し、Ｍテーブル作成部１４が、値Ｂ_ｉ（ｘ）の順番ｉ毎のＭ［ｉ］＝Ａ（ｘ）ｘ^ig ｍｏｄ Ｆ（ｘ）の計算結果からなるＭテーブルを作成する。Ｔテーブル作成部１５は、Ｍテーブルを参照し、順番ｉ毎のＴ［ｉ］＝Ｍ［ｉ］Ｂ_i（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるＴテーブルを作成する。乗算実行部１６は、Ｔテーブルの計算結果Ｔ［ｓ−１］，…，Ｔ［０］の総和を計算し、乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として出力する。 （もっと読む）

【課題】モントゴメリー・モジュラ乗算を実行する、改良された小型電子論理演算装置を提供する。
【解決手段】ρ(A・B)Nのモントゴメリー・モジュラ乗算を実行するものであって、ここでρ(A・B)Nは A・B・I mod N にモジュラ演算上の合同であり、I・2ⁿ≡1 mod N であり、A、B及びNはnビット長オペランドであり、Nは奇数であり、該装置は、第一及び第二の主メモリ・レジスタであって、各レジスタはnビット長オペランドを保持し、それぞれ、乗数B、法Nを格納するように適合せしめられたものと、第一の値を第二の値によって、及び第三の値を第四の値によって、同時に乗算し、両方の結果を合計するデバイスであって、該デバイスへの入来ビットとしての予想Y₀ビットを出力するための一つの桁上げ保存加算器を有するものと、該桁上げ保存加算器から出力される最下位kビットがゼロとなるようにY₀を決定するY₀センスユニットと、を具備する。 （もっと読む）

【課題】多項式間の乗算結果を利用して他の多項式間の乗算を行う多項式乗算を、少ないロード回数で実現する。
【解決手段】まず、多項式Ａ（α）の係数系列をレジスタに格納する。次に、或る整数ｉ≧２に対してＷ（α）＝ｔ_０＋ｔ_１・α＋…＋ｔ_ｉ−１・α^ｉ−１で表現可能な０及び１を除くすべての多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列を生成する。次に、多項式α^ｉ−１・Ａ（α）の係数系列の各係数を１次数分だけ高次数側へシフトさせ、そのシフト結果である係数系列を、多項式α^ｉ・Ａ（α）の係数系列としてレジスタに格納する。そして、多項式α^ｉ・Ａ（α）の係数系列を継続的にレジスタに保持した状態で、Ｗ（α）＝ｔ_０＋ｔ_１・α＋…＋ｔ_ｉ・α^ｉで表現可能なα^ｉを除くすべての多項式Ｗ（α）について、多項式Ｗ（α）・Ａ（α）の係数系列が算出されるまで二倍算過程と加算過程と、を交互に実行する。 （もっと読む）

【課題】改善されたモジュラー減少演算子を提供する。
【解決手段】本発明は改善されたモジュラー減少装置に関する。該モジュラー減少装置は、４以上の高い記数法の底ｒを用いたモンゴメリー乗算プロセスの変形を使用する、乗算器（１２）を含む。それはとりわけ非対称の暗号法に用いられる計算要素に適用される。 （もっと読む）

【課題】剰余演算を行って暗号アルゴリズムを処理する暗号処理回路において、ＦＰＧＡの機能拡張に適応した回路構成及び処理方式を採ることで、より少ない回路リソースでの高速動作を可能とし、さらに、回路の汎用性を高めることを目的とする。
【解決手段】被乗数をＡ、乗数をＢ、法をＭ、中間値をＱとし、Ａ及びＢの乗算結果とＭ及びＱの乗算結果と中間結果Ｓとの加算結果に基づいて、モンゴメリ乗算による剰余演算を行うモンゴメリ乗算回路２０１において、演算回路Ａ３０１及び演算回路Ｄ６０１は、所定の動作周波数ｃｌｋ１ｘの２倍の動作周波数ｃｌｋ２ｘにて、Ａ及びＢの乗算処理とＭ及びＱの乗算処理とを行う。演算回路Ｂ４０１及び演算回路Ｃ５０１は、ｃｌｋ１ｘにて、上記２つの乗算処理の結果とＳとの加算処理を行う。演算回路Ｃ５０１は、その加算処理の結果に基づいて、モンゴメリ乗算による剰余演算を行う。 （もっと読む）