(57)【要約】【課題】モジュラス掛け算を実行するためのモンゴメリモジュラス掛け算モジュールの電力消耗の減少と計算速度の向上のための方法が提供される。【解決手段】コーディングスキームは部分積及びマルチプルモジュラス選択信号の間のハミング距離を減少させ、マルチプレックス動作と電力消耗を減少させる。同期化レジスタは累算器に入力される部分積及びマルチプルモジュラス値を同期化してグリッチを減少させ、そして／または計算速度を向上させる。レジスタは以前値を貯蔵し、マルチプレクサからの値を得るための要求、マルチプレックス動作を減少させ、そして／または電力消費を減少させる。【選択図】図１
2004334212.tif 000002
【特許請求の範囲】
【請求項１】
ブースレコーダと
前記ブースレコーダからの少なくとも一つの出力を入力とするブースレジスタとを含むことを特徴とするブースプロセッサ。
【請求項２】
前記ブースレジスタは前記ブースプロセッサにフィードバックされる前記ブースプロセッサの少なくとも一つの出力値を貯蔵するフィードバックレジスタであることを特徴とする請求項１に記載のブースプロセッサ。
【請求項３】
前記出力値は部分積の値を選択するために使われる部分積選択信号であることを特徴とする請求項２に記載のブースプロセッサ。
【請求項４】
前記ブースレジスタは前記ブースレコーダの出力値を貯蔵するためのパイプラインレジスタであることを特徴とする請求項１に記載のブースプロセッサ。
【請求項５】
モジュラスレコーダと、
前記モジュラスレコーダからの少なくとも一つの出力を入力とするフィードバックレジスタとを含むことを特徴とするモジュラスプロセッサ。
【請求項６】
前記モジュラスフィードバックレジスタは前記モジュラスレコーダにフィードバックされる前記モジュラスレコーダの少なくとも一つの出力値を貯蔵することを特徴とする請求項５に記載のモジュラスプロセッサ。
【請求項７】
前記出力値はマルチプルモジュラス値を選択するために使われるマルチプルモジュラス選択信号であることを特徴とする請求項５に記載のモジュラスプロセッサ。
【請求項８】
ブースレコーダと、
前記ブースレコーダからの少なくとも一つの出力を入力とする部分積同期レジスタと、
モジュラスレコーダと、
前記モジュラスレコーダからの少なくとも一つの出力を入力とするマルチプルモジュラス同期レジスタとを含み、
前記部分積同期レジスタ及び前記マルチプルモジュラス同期レジスタは前記ブースレコーダ及び前記モジュラスレコーダの出力から導出された信号を同期させるために使われることを特徴とする掛け算器。
【請求項９】
前記部分積同期レジスタからの少なくとも一つの値を入力とするブースＡＮＤゲートをさらに含むことを特徴とする請求項８に記載の掛け算器。
【請求項１０】
前記マルチプルモジュラス同期レジスタからの少なくとも一つの値を入力とするモジュラスＡＮＤゲートをさらに含むことを特徴とする請求項８に記載の掛け算器。
【請求項１１】
掛け算器において、
モジュラスレコーダと、
前記モジュラスレコーダからの少なくとも一つの出力を入力とするモジュラスフィードバックレジスタと、
ブースレコーダと、
前記ブースレコーダからの少なくとも一つの出力を入力とするブースレジスタとを含み、
前記モジュラスフィードバックレジスタ及び前記ブースレジスタは前記掛け算器で減少した計算電力使用を可能にする値を貯蔵することを特徴とする掛け算器。
【請求項１２】
前記ブースレジスタは前記ブースレコーダにフィードバックされるように、前記ブースレコーダの少なくとも一つの出力値を貯蔵するフィードバックレジスタであることを特徴とする請求項１１に記載の掛け算器。
【請求項１３】
前記出力値は部分積値を選択するために使われる部分積選択信号であることを特徴とする請求項１２に記載の掛け算器。
【請求項１４】
前記ブースレジスタは前記ブースレコーダの出力値を貯蔵するパイプラインレジスタであることを特徴とする請求項１１に記載の掛け算器。
【請求項１５】
前記モジュラスフィードバックレジスタは前記モジュラスレコーダにフィードバックされるように、前記モジュラスレコーダの少なくとも一つの出力値を貯蔵するフィードバックレジスタであることを特徴とする請求項１１に記載の掛け算器。
【請求項１６】
前記出力値はマルチプルモジュラス値を選択するために使われるマルチプルモジュラス選択信号であることを特徴とする請求項１５に記載の掛け算器。
【請求項１７】
前記ブースレコーダからの少なくとも一つの値を入力とするブースＡＮＤゲートをさらに含むことを特徴とする請求項１１に記載の掛け算器。
【請求項１８】
前記モジュラスフィードバックレジスタからの少なくとも一つの値を入力とするモジュラスＡＮＤゲートをさらに含むことを特徴とする請求項１１に記載の掛け算器。
【請求項１９】
ブースレコーダと、
前記ブースレコーダからの少なくとも一つの出力を入力とするマルチプレクサとを含み、
前記ブースレコーダ及び前記マルチプレクサは部分積を求めるために使われることを特徴とする部分積発生器。
【請求項２０】
前記マルチプレクサからの少なくとも一つの値を入力とするブースＡＮＤゲートをさらに含むことを特徴とする請求項１９に記載の部分積発生器。
【請求項２１】
前記ブースレコーダは部分積選択信号、及び前記部分積選択信号の以前値に基づいて禁止される前記部分積選択信号の特定値に割り当てられるビットパターンを発生することを特徴とする請求項１９に記載の部分積発生器。
【請求項２２】
前記ビットパターンは前記部分積選択信号と前記部分積選択信号の以前値との間のハーミング距離が減少するように選択されることを特徴とする請求項２１に記載の部分積発生器。
【請求項２３】
前記ビットパターンは前記部分積選択信号と対応する以前値の間の平均臨時ハミング距離が減少するように選択されることを特徴とする請求項２１に記載の部分積発生器。
【請求項２４】
前記ブースレコーダは、
前記部分積選択信号の以前値の第１部分を入力とし、前記部分積選択信号の第１部分を出力とする第１マルチプレクサと、
前記部分積選択信号の以前値の第２部分を入力とし、前記部分積選択信号の第２部分を出力とする第２マルチプレクサとを含むことを請求項２１に記載の部分積発生器。
【請求項２５】
前記第１マルチプレクサと前記第２マルチプレクサは８：１マルチプレクサであることを特徴とする請求項２４に記載の部分積発生器。
【請求項２６】
モジュラスレコーダと、
マルチプレクサとを含み、
前記モジュラスレコーダはあらかじめ設定された値を有するイネーブル信号を除いた現在マルチプルモジュラス選択信号を発生し、もし前記イネーブル信号があらかじめ設定された値を有したら、前記選択信号の以前値はマルチプルモジュラス選択信号の発生なしに使われ、前記選択信号はマルチプルモジュラス値を選択するために使われることを特徴とするマルチプルモジュラス発生器。
【請求項２７】
モジュラスの一部から導出された値を入力とするモジュラスＡＮＤゲートをさらに含むことを特徴とする請求項２６に記載のマルチプルモジュラス発生器。
【請求項２８】
前記選択信号の以前値の第１部分を入力とし、前記現在マルチプルモジュラス選択信号の第１部分を出力とする第１マルチプレクサと、
前記選択信号の以前値の第２部分を入力とし、前記現在マルチプルモジュラス選択信号の第２部分を出力とする第２マルチプレクサとを含むことを特徴とする請求項２６に記載のマルチプルモジュラス発生器。
【請求項２９】
前記第１マルチプレクサと前記第２マルチプレクサは８：１マルチプレクサであることを特徴とする請求項２８に記載のマルチプルモジュラス発生器。
【請求項３０】
被乗数の一部が入力されるモジュラスレコーダと、
前記モジュラスレコーダからの値を貯蔵するマルチプルモジュラス同期レジスタと、
掛け算値を貯蔵する直列同期レジスタとを含むことを特徴とする掛け算器。
【請求項３１】
マルチプルモジュラス値と部分積値は前記マルチプルモジュラス同期レジスタからの値及び直列同期レジスタからの値を使って同期されることを特徴とする請求項３０に記載の掛け算器。
【請求項３２】
グリッチを減少させるために前記マルチプルモジュラス値と前記部分積値は同時に同期されることを特徴とする請求項３１に記載の掛け算器。
【請求項３３】
掛け算器において、
モジュラスレコーダと、
前記モジュラスレコーダからの少なくとも一つの出力を入力とするモジュラスフィードバックレジスタと、
前記モジュラスレコーダからの少なくとも一つの出力を入力とするモジュラス同期レジスタと、
ブースレコーダと、
前記ブースレコーダからの少なくとも一つの出力を入力とするブース同期レジスタと、
前記ブースレコーダからの少なくとも一つの出力を入力とするブースレジスタとを含み、前記モジュラスフィードバックレジスタ及び前記ブースレジスタは前記掛け算器で減少した計算電力使用を可能にする値を貯蔵し、グリッチを減少させるため前記ブース同期レジスタ及び前記モジュラス同期レジスタは前記ブースレコーダ及び前記モジュラスレコーダの出力から導出された信号を同期させるために使われることを特徴とする掛け算器。
【請求項３４】
前記ブースレジスタは前記ブースレコーダにフィードバックされるように、前記ブースレコーダの少なくとも一つの出力値を貯蔵するフィードバックレジスタであることを特徴とする請求項３３に記載の掛け算器。
【請求項３５】
前記出力値は部分積値を選択するために使われる部分積選択信号であることを特徴とする請求項３４に記載の掛け算器。
【請求項３６】
前記ブースレジスタは前記ブースレコーダの出力値を貯蔵するパイプラインレジスタであることを特徴とする請求項３３に記載の掛け算器。
【請求項３７】
前記モジュラスフィードバックレジスタは前記モジュラスレコーダにフィードバックされるように、前記モジュラスレコーダの少なくとも一つの出力値を貯蔵するモジュラスフィードバックレジスタであることを特徴とする請求項３３に記載の掛け算器。
【請求項３８】
前記出力値はマルチプルモジュラス値を選択するために使われるマルチプルモジュラス選択信号であることを特徴とする請求項３７に記載の掛け算器。
【請求項３９】
前記ブースレジスタからの少なくとも一つの値を入力とするブースＡＮＤゲートをさらに含むことを特徴とする請求項３３に記載の掛け算器。
【請求項４０】
前記モジュラスフィードバックレジスタからの少なくとも一つの値を入力とするモジュラスＡＮＤゲートをさらに含むことを特徴とする請求項３３に記載の掛け算器。
【請求項４１】
マルチプルモジュラス値及び部分積値は前記モジュラス同期レジスタからの値及び前記ブース同期レジスタからの値を使って同期されることを特徴とする請求項３３に記載の掛け算器。
【請求項４２】
レディックス２Ｎ(Ｎ>1)モンゴメリ掛け算の速度を向上させるための方法において、
ブースレコーダに入力を提供する段階と、
前記ブースレコーダの出力を貯蔵する段階と、
前記モンゴメリ掛け算の結果を累算する段階とを含み、
前記貯蔵及び累算段階は同時にオーバラップされて実行されることを特徴とするモンゴメリ掛け算方法。
【請求項４３】
前記ブースレコーダの出力はパイプラインレジスタに貯蔵されることを特徴とする請求項４２に記載のモンゴメリ掛け算方法。
【請求項４４】
レディックス２Ｎ(Ｎ>１)モンゴメリ掛け算の電力消耗を減少させるための方法において、
モジュラス、乗数及び被乗数が入力される段階と、
前記モジュラス、乗数及び被乗数を同期させる段階と、
モンゴメリ掛け算の結果を生成するため値を累算する段階とを含むことを特徴とするモンゴメリ掛け算方法。
【請求項４５】
前記モジュラス、前記乗数及び前記被乗数のうちの少なくとも一つを用いてマルチプルモジュラスを計算する段階と、
前記モジュラス、前記乗数及び前記被乗数のうちの少なくとも一つを用いて部分積を計算する段階とをさらに含み、
前記マルチプルモジュラス及び前記部分積は同期された値であることを特徴とする請求項４４に記載のモンゴメリ掛け算方法。
【請求項４６】
前記モジュラス、前記乗数及び前記被乗数と関連のある少なくとも二つの入力を同期レジスタに貯蔵する段階をさらに含むことを特徴とする請求項４４に記載のモンゴメリー掛け算方法。
【請求項４７】
モンゴメリ掛け算の全体の電力消耗を減少させるため前記部分積及び前記マルチプルモジュラスが累算器に到着する時間を一致させる段階をさらに含むことを特徴とする請求項４５に記載のモンゴメリ掛け算方法。
【請求項４８】
レディックス２Ｎ(Ｎ>１)モンゴメリ掛け算の電力消耗を減少させるための方法において、
ブースレコーダに入力を提供する段階と、
前記ブースレコーダを用いて選択信号を生成する段階と、
反転されたビットパターンを前記選択信号の以前値に基づいて禁止される前記選択信号の特定値で割り当てる段階と、
前記ブースレコーダの出力を貯蔵する段階とを含むことを特徴とするモンゴメリ掛け算方法。
【請求項４９】
前記選択信号と前記選択信号の以前値との間のハミング距離が縮小されるように、前記反転されたビットパターンを選択する段階をさらに含むことを特徴とする請求項４８に記載のモンゴメリ掛け算方法。
【請求項５０】
前記選択信号及びそれらに対応する以前値の間の平均臨時ハミング距離が縮小されるように、前記ビットパターンは選択されることを特徴とする請求項４８に記載のモンゴメリ掛け算方法。
【請求項５１】
レディックス２Ｎ(Ｎ>１)モンゴメリ掛け算の電力消耗を減少させるための方法において、
内部結果信号のｎ番目の値を決める段階と、
イネーブル信号と前記繰り返し結果信号のｎ番目の値を回路に提供する段階と、
もし前記イネーブル信号が前記繰り返し結果信号のｎ＋１番目の値を無価値にする場合、前記繰り返し結果信号のｎ＋１番目の値を計算しない段階と、
前記繰り返し結果信号のｎ番目の値をフィードバックする段階と、
前記繰り返し結果信号のｎ＋１番目の値に代えて前記繰り返し結果信号のｎ番目の値を用いる段階とを含むことを特徴とするモンゴメリ掛け算方法。
【請求項５２】
前記繰り返し結果信号の前記ｎ番目及びｎ＋１番目の値は組み合わせロジックによって決められることを特徴とする請求項５１に記載のモンゴメリ掛け算方法。
【請求項５３】
前記組み合わせロジックはマルチプレクサによって実行されることを特徴とする請求項５２に記載のモンゴメリ掛け算方法。
【請求項５４】
モジュラスレコーダの電力消費を減少させるための方法において、
マルチプルモジュラス選択信号のｎ番目の値を決める段階と、
レジスタに前記マルチプルモジュラス選択信号のｎ番目の値を貯蔵する段階と、
ｎ＋１番目のイネーブル信号を発生する段階と、
前記マルチプルモジュラス値を０に選択するように前記イネーブル信号はあらかじめ設定され、前記ｎ＋１番目のイネーブル信号が前記あらかじめ設定された値である時に、前記ｎ＋１番目のマルチプルモジュラス選択信号を決めず、前記マルチプルモジュラス選択信号の前記ｎ番目の値を用いる段階とを含むことを特徴とするモジュラスレコーダの電力消費減少方法。
【請求項５５】
前記マルチプルモジュラス選択信号を用いて前記マルチプルモジュラス値を選択する段階をさらに含み、
前記イネーブル信号値があらかじめ設定された値である時に、前記選択段階は実行されないことを特徴とする請求項５４に記載のモジュラスレコーダの電力消費減少方法。
【請求項５６】
モンゴメリ掛け算器において、
モジュラス、被乗数及び乗数の値を入力する入力手段と、
ブースレコーダからの少なくとも一つの出力値を貯蔵するためのブース貯蔵手段と、
モジュラスレコーダからの少なくとも一つの出力値を貯蔵するためのモジュラス貯蔵手段と、
前記入力手段からの入力を用いて部分積値を発生するための部分積発生手段と、
前記入力手段からの入力を用いてマルチプルモジュラスを発生するマルチプルモジュラス発生手段と、
前記部分積値と前記マルチプルモジュラス値を同期させる同期化手段と、
前記同期化された部分積値と前記マルチプルモジュラス値とを入力とし、モンゴメリ掛け算結果を発生する累算手段とを含むことを特徴とするモンゴメリ掛け算器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号化システムに関するものであり、さらに具体的には、モンゴメリモジュラ掛け算器に関するものである。
【背景技術】
【０００２】
ネットワークシステムの使用が頻繁になるにつれ、ネットワーク通信の機密性が非常に重要になった。データの無欠性(ｉｎｔｅｇｒｉｔｙ)の保護と機密性(ｓｅｃｒｅｃｙ)は重要視されている。
【０００３】
コード送信の基本過程とメッセージデコーディングはプレーンテキスト(ｐｌａｉｎｔｅｘｔ)を得て、メッセージを暗号文(ｃｉｐｈｅｒｔｅｘｔ)に変更し、(ｅｎｃｒｙｐｔｉｎｇ)、暗号文を受信機に伝送し、暗号文を復元(ｄｅｃｒｙｐｔｉｎｇ)して元々のメッセージに復元するものである。
【０００４】
暗号化システムで、暗号化キー(ｅｎｃｒｙｐｔｉｏｎ  ｋｅｙ)はプレーンテキストを暗号化(ｅｎｃｒｙｐｔ)するために使われる。暗号文は受信機に伝送され、受信機は復号化キー(ｄｅｃｒｙｐｔｉｏｎ  ｋｅｙ)を利用して暗号文を復号化してプレーンテキストに戻す。暗号化キー及び復号化キーは一対で使われる。
【０００５】
例えば、公開及び秘密キー対は２またはそれ以上の大きい素数(ｐｒｉｍｅ  ｎｕｍｂｅｓ)の関数である。暗号及び復号で、各関数は大きい素数であり、各々は一対で使われる。二つのキー対（Ｐ、Ｑ）は完全なシステム(暗号化そして復号化)のために提供される。機密性を向上させるため、ワード長さのＰ及びＱは互いに類似であるので、ビット長さに基づいて区別し難しい。Ｎは次の通りである。
【０００６】
【数１】
2004334212.tif 000003
【０００７】
暗号化キーＫＥは任意の数であり、ＫＥ、及び（Ｐ−１）（Ｑ−１）は素数である。したがって、復号化キーＫＤは拡張されたユークリットアルゴリズム(ｅｘｔｅｎｄｅｄ  Ｅｕｃｌｉｄｅａｎ  ａｌｏｇｏｒｉｔｈｍ)で計算することができる。
【０００８】
【数２】
2004334212.tif 000004
【０００９】
ＫＤ及びＮは素数である。ＫＥ、Ｎはデータの暗号化のために使われる暗号化キー（または公開キー）であり、ＫＤ及びＮは復号化のために使われる復号化キーである。キーが発生された後、元々のメッセージは次のような計算によって暗号化される。
【００１０】
【数３】
2004334212.tif 000005
【００１１】
Ｍは元々のメッセージ(プレーンテキスト)であり、Ｃは暗号化されたメッセージ(暗号文、ｃｉｐｈｅｒｔｅｘｔ)である。暗号化されたデータを復号化するため、次のような計算が実行される。
【００１２】
【数４】
2004334212.tif 000006
【００１３】
Ｍ'は復号化されたメッセージである。Ｍ'は元々のメッセージＭと同一である。例示的ないくつかのモジュラ掛け算が以下実行される。
【００１４】
いくつかの暗号化システムで、長いワード長さ(例えば、５１２ビット)に対する機密性が求められる。しかし、長いワード長さによって速度の性能が制限され、計算速度の向上が求められる。計算速度の向上のために速い指数計算の重要性が増大している。指数計算を速くするための方法としては、Ｈ−アルゴリズム、Ｌ−アルゴリズムなどがある。このような方法のうちの一つであるモンゴメリモジュラ掛け算アルゴリズムは、高性能指数計算アルゴリズムの核心動作で使うことができる。モンゴメリモジュラ掛け算アルゴリズムは暗号化及び復号化動作の効率を向上させる。
【００１５】
ｎビット計算のためのモンゴメリモジュラ掛け算アルゴリズムは次の通りである。
【００１６】
【数５】
2004334212.tif 000007
【００１７】
モジュラ指数アルゴリズム内で使われるＡ、Ｂ及びＮは乗数、被乗数及びモジュラ数(Ｍｏｄｕｌａｒ  ｎｕｍｂｅｒ)であり、各々はｎビットである。
【００１８】
例示的に、レディックス２(ｒａｄｉｘ２)モンゴメリ繰り返しモジュラ掛け算アルゴリズムは次の通りである。
【００１９】
Ｓ０＝０
ｆｏｒ（Ｉ＝０；１<Ｎ；Ｉ＋＋）｛
ｑＩ＝（ＳＩ＋ｂＩＡ）ｍｏｄ２；
ＳＩ＋１＝（ＳＩ＋ｂＩＡ＋ｑＩＭ）／２；
ｉｆ（ＳＮ＞＝Ｍ）ＳＮ＝ＳＮ−Ｍ；
【００２０】
ｂＩＡ(＝ＰＰＩ)は部分積であり、ｑＩＭ(＝ＭＭＩ)は(ＳＩ＋ＰＰＩ)の最下位ビットを０に作るためのマルチプルモジュラスである。ｎはモジュラスＭのビット長さである。Ｎ＝ｎ／２であり、ＳＩは以前サイクルの部分累積結果であり、ＳＩ＋１はｎビットを有する現在サイクルの部分累積結果であり、ＳＮは最終計算結果である。例えば、レディックス４モンゴメリ繰り返しモジュラ掛け算アルゴリズムは次の通りである。
【００２１】
ＳＯ＝０；
ｆｏｒ(Ｉ＝０；１＜Ｎ；Ｉ＋＋)｛
ｑＩ＝（（（ＳＩ＋ｂＩＡ）ｍｏｄ４＊Ｍ'）ｍｏｄ４；
ＳＩ＋１＝（ＳＩ＋ｂＩＡ＋ｑＩＭ）／４；｝
ｉｆ（ＳＮ＞＝Ｍ）ＳＮ＝ＳＮ−Ｍ；
【００２２】
レディックス２及びレディックス４プロセスは繰り返しのデータを生成するプロセスであり、Ｉ＝０；Ｉ<ｎ；Ｉ＋＋のループ内の繰り返しによってデータの値が変更される。モジュラ動作速度はシステム性能に影響を及ぼす。したがって、もしビット長さが非常に長ければ、システムの性能も低くなる。ＭＭＩ(ｑＩＭ)を計算するため、一番目のＰＰＩ(＝ｂＩＡ)が計算され、計算されたＰＰI及びＳIは足される。累算器が論理的計算を二度実行するので、電力消耗が増加する。
【００２３】
モンゴメリモジュラ掛け算での時間消費は暗号化計算装置を含むデジタル応用装置内の動作に影響を及ぼす。高性能デジタル装置を製造するためモジュラ演算の速度を向上させることが必要である。
【００２４】
速度とともに電力消費が考慮されなければならない。例えば、スマートカード及びモバイル製品では低電力消耗がさらに重要になっている。データの保護及び装置の効率を向上させるため、暗号化計算装置を使うスマートカード及びモバイル製品の電力消耗特性は向上しなければならない。さらに、多い電力を消費する計算装置(ｃｏｍｐｕｔａｔｉｏｎａｌ  ｄｅｖｉｃｅｓ)は多い電力を消耗し、大部分の電力がモジュラ掛け算で消耗される。特に、ビット長さが増加すれば増加するほどモジュラ動作でさらに多い電力が求められる。
【発明の開示】
【発明が解決しようとする課題】
【００２５】
本発明の目的は、低電力消耗のモジュラ掛け算演算装置を提供することにある。
【００２６】
本発明の他の目的は、低電力消耗で、かつ動作速度を向上させることができるモジュラ掛け算演算装置を提供することにある。
【課題を解決するための手段】
【００２７】
本発明によれば、レジスタパイプライン及び／または累算器へのデータ到着時間を操作して、モンゴメリモジュラ掛け算の速度向上及び／または電力消費減少のための方法が提供される。
【００２８】
本発明によれば、モンゴメリモジュラ掛け算の速度を加速するためにモンゴメリ掛け算器のブースレコーダで使われるパイプライン方法が提供される。
【００２９】
本発明によれば、モンゴメリ掛け算器の電力消費を減少させ、累算器の計算動作が減少するように、Ｉ番目の繰り返しの部分積ＰＰＩとＩ番目の繰り返しのマルチプルモジュラスＭＭＩが累算器にほぼ同時に到着するようにする。
【００３０】
本発明によれば、フィードバックレジスタの使用でマルチプレックス動作の数は減少する。もし現在の繰り返しの部分積ＰＰＩまたはマルチプルモジュラスＭＭＩ値が“０”で選択されれば、“０”は加算動作が不要であることを示し、以前繰り返しの値がマルチプレックスサ動作で使用されない。
本発明によれば、平均ハミング距離(ａｖｒａｇｅ  ｈａｍｍｉｎｇｄｉｓｔａｎｃｅ)が減少する。ハミング距離は同一のビット位置の差値の数である。したがって、いくつかのビット変化はファン−アウトローディング変化を減少させる。
【発明の効果】
【００３１】
本発明はモジュラ掛け算演算装置で電力消耗を減らす効果がある。特に、モジュラス積と部分積の印加時点を同期化させることによって、不要な信号の遷移、またはグリッチを抑制することによって、動作上の電力消耗を減らす利点がある。
【発明を実施するための最良の形態】
【００３２】
以下、本発明の望ましい実施の形態を添付の図面を参照して詳細に説明する。
【００３３】
図１は本発明の望ましい実施の形態によるモジュラ掛け算器１０００を示している。モジュラ掛け算器１０００はレジスタ１に貯蔵されたモジュラスＡ、レジスタ３に貯蔵された被乗数Ａ、レジスタ７に貯蔵された乗数Ｂ、ブースプロセッサ３０１、モジュラスプロセッサ３００、マルチプルモジュラスＭＭＩの計算を助けるマルチプレクサ１０、部分積ＰＰIの計算を助けるマルチプレクサ２０、及びモジュラ掛け算演算を助ける累算器１００を含む。累算器１００は部分積ＰＰIとマルチプルモジュラスＭＭＩが入力され、モンゴメリ掛け算結果を出力する。本発明の実施の形態で、モジュラスＭは正数であり、ｎビットＭ[ｎ−１：０]である。被乗数Ａは正数、または負数であり、ｎ＋１ビットＡ[ｎ：０]であり、１ビットの符号ビットを有し、乗数Ｂは偶数ビットを有する。ｎが偶数であれば、Ｂはｎ＋２ビットであり、符号ビットは２ビットである。またはｎが奇数であれば、Ｂはｎ＋１ビットであり、符号ビットは１ビットである。
【００３４】
本発明の望ましい実施の形態によるレジスタ１はモジュラスＭとモジュラスＭの１の補数値Ｍを提供する。同様に、レジスタ３は被乗数Ａと被乗数Ａの１の補数値Ａを提供する。
【００３５】
掛け算器１０００は数５の繰り返しのプロセスでモジュラ掛け算の解答を捜す。モジュラスプロセッサ３００及びマルチプレクサ１０はモジュラスＭＭＩを選択するために使われる。モジュラスＭＭＩを選択するため、モジュラスプロセッサ３００は累算器１００から繰り返しのデータを受け入れる。本発明の実施の形態で、繰り返しのデータＳＰＰＩ[１：０]は、累算器１００に貯蔵された和の最下位二つのビットＳＩ[１：０]と部分積の最下位二つのビットＰＰＩ[１：０]の組み合わせである。和ＳＩ[１：０]と部分積ＰＰＩ[１：０]は２ビット加算器４０で結合して、ＳＰＰＩ[１：０]を形成する。部分積反転信号ＮＥＧ＿ＰＰ及びＰＰＩは累算器１００で結合する。−ＰのＰＰＩを得るように、ビット反転を表示するため部分積反転信号ＮＥＧ＿ＰＰが使われる。モジュラスプロセッサ３００はモジュラスの二番目のビットＭ[１]をさらに受け入れる。モジュラスプロセッサ３００はＳＰＰＩ[１：０] 及びモジュラスＭ[１]を用いて、複数のモジュラスＭＭＩの選択を決めるための出力信号を発生する。本発明の実施の形態による上述の説明で、ビットの大きさは限定されない。ＳＰＰＩは２ビット以上であり得る。これによって、本発明の他の構成は変更される。
【００３６】
モジュラスプロセッサ３００は複数の信号例えば、マルチプルモジュラス選択信号ＳＥＬ＿ＭＭ[１：０]、マルチプルモジュラスイネーブル信号ＥＮ＿ＭＭ、マルチプルモジュラス反転信号ＮＥＧ＿ＭＭ、…を出力する。この実施の形態で、モジュラスプロセッサ３００は２Ｍ、Ｍ、０、Ｍのうちの一つを選択するためマルチプレクサ１０にマルチプルモジュラス選択信号ＳＥＬ＿ＭＭ[１：０]を出力する。マルチプレクサ１０はモジュラスＭとマルチプルモジュラス選択信号ＳＥＬ＿ＭＭ[１：０]が入力され、ＭＭＩを出力する。マルチプルモジュラス反転信号ＮＥＧ＿ＭＭ及びＭＭＩは累算器１００で結合する。−ＭのＭＭＩを得るように、ビット反転を表示するためモジュラス反転信号ＮＥＧ＿ＭＭが使われる。
【００３７】
各マルチプレックス動作は電力及びエネルギを消耗するので、新しい信号ＳＥＬ＿ＭＭ[１：０]が使われる時に、マルチプレックス動作がＭＭＩ設定及び選択を変更するため実行される。ＳＥＬ＿ＭＭ[１：０]の以前値の使用は設定を変更せず、マルチプレックス動作が実行されない。ＭＭＩ選択でマルチプレックス動作の必要な数の減少は掛け算器１０００全体の電力消費を減少させる。
【００３８】
本発明の望ましい実施の形態で、モジュラスプロセッサ３００はマルチプルモジュラスフィードバックレジスタ６１及びモジュラスレコーダ７０を含む。フィードバックレジスタ６１は以前の繰り返しのＳＥＬ＿ＭＭ[１：０]の値をＳＥＬ＿ＭＭ＿Ｄ[１：０]として貯蔵する。ＭＭＩ＝０であることを所望する時、モジュラスプロセッサ３００はマルチプルモジュラスイネーブル信号ＥＮ＿ＭＭを０で出力する。ＥＮ＿ＭＭはＡＮＤゲート３１に入力される。ＡＮＤゲート３１はマルチプレクサ１０の出力が入力され、これはマルチプルモジュラス選択信号ＳＥＬ＿ＭＭ＿Ｄ[１：０]の以前値で使われるので、マルチプレックス動作が実行されない。ＡＮＤゲート３１はＭＭＩ＝０を出力する。ＭＭＩ＝０はマルチプレックス動作なしに割り当てられて、掛け算器１００の電力消耗を減少させる。 このようなコーディングスキームが図２に示されている。
【００３９】
図２は本発明の望ましい実施の形態によるコーディングスキームを示している図である。図２ではモジュラスレコーダ７０に入力される三つの入力を示しているが、本発明はこれに限定されず、図１に示したＳＥＬ＿ＭＭ＿Ｄ[１：０]の付加的な入力などのように多様に変更され得る。図２のコーディングスキームはＥＮ＿ＭＭの値が０であり、選択されたＭＭＩが０である時に、ＳＥＬ＿ＭＭ[１：０]＝ＳＥＬ＿ＭＭ＿Ｄ[１：０]を示している。
【００４０】
本発明の実施の形態で、電力消耗を減少させるための類似の方法がブースプロセッサ３０１にも使われる。掛け算器１０００は繰り返しのプロセスで、ＭＭＩと部分積ＰＰＩを累算器１００に提供することによって、モジュラ掛け算の結果を得る。ブースプロセッサ３０１及びマルチプレクサ２０は累算器１００に提供するための部分積ＰＰＩ値(例えば、０、Ａ、２Ａ、−２Ａ、−Ａ、…)を選択するために使われる。ブースプロセッサ３０１は被乗数の最下位二つのビットＡ[１：０]、乗数の最下位二つのビットＢ[１]、Ｂ[０]、及びＢ[１]の以前の繰り返し値であるＢ[ｒ]が入力される。
【００４１】
部分積ＰＰＩを選択するためブースプロセッサ３０１は部分積選択信号ＳＥＬ＿ＰＰ[１：０]をマルチプレクサ２０に出力する。マルチプレクサ２０は被乗数Ａ０及びＳＥＬ＿ＰＰ[１：０]を受け入れ、値をＡＮＤゲート３２に出力する。ＡＮＤゲート３２はマルチプレクサ２０からの入力とブースプロセッサ３０１からの部分積イネーブル信号ＥＮ＿ＰＰを受け入れる。ＡＮＤゲート３２は部分積ＰＰＩの選択された値を出力し、選択された部分積ＰＰＩは累算器１００に提供される。上述のような類似の過程で、ブースプロセッサ３０１はブースレコーダ８０及び部分積フィードバックレジスタ６４を含む。ＰＰＩの０はＳＥＬ＿ＰＰ＿Ｄ[１：０]及びＳＥＬ＿ＰＰ[１：０]の以前値を部分積フィードバックレジスタ６４に貯蔵することにより選択される。ＰＰＩ＝０であれば、ブースプロセッサ３０１は部分積イネーブル信号ＥＮ＿ＰＰを０で出力する。信号ＥＮ＿ＰＰはＡＮＤゲート３２に入力される。ＡＮＤゲート３２には部分積選択信号ＳＥＬ＿ＰＰ＿Ｄ[１：０]の以前値で使われたマルチプレクサ２０の出力が入力される。マルチプレックス動作なしに、ＰＰＩ＝０に設定することは掛け算器１０００の電力消耗を減少させる。これと類似なコーディングスキームが図３に示されている。
【００４２】
図３は本発明の望ましい実施の形態によるコーディングスキームを示している。図３では、ブースレコーダ８０への入力として三つの入力を示しているが、本発明はこれに限定されず、図１に示したような付加的な入力ＳＥＬ＿ＰＰ＿Ｄ[１：０]及びＡ[１：０]のような多様な入力及び出力を有することができる。図３のコーディングスキームはＥＮ＿ＰＰ＝０であり、選択されたＰＰＩが０である時に、ＳＥＬ＿ＰＰ[１：０]＝ＳＥＬ＿ＰＰ＿Ｄ[１：０]を示している。
【００４３】
付加的に、図３に示したコーディングスキームは本発明の望ましい実施の形態による平均ハミング距離(ｈａｍｍｉｎｇ  ｄｉｓｔａｎｃｅ)を示している。ハミング距離は同一のビット位置の差値の数である。例えば、もしｉ−１番目の繰り返しで、ＳＥＬ＿ＰＰ[１：０]が“００”の値であり、対応するＰＰＩの値が“Ａ”であれば、Ｉ番目の繰り返しのＳＥＬ＿ＰＰ［１：０］は“１１”であり、対応するＰＰＩの値は“２Ａ”であるので、結果的にハミング距離は２である。これは二つの値の間のハミング距離を減少させて、ビット反転の数と計算電力使用を減少させる。コーディングスキームの選択によって以前繰り返しＰＰＩ値がＡ（−Ａ）または、２Ａ（−２Ａ）であれば、続く繰り返しＰＰＩ値は制限されて、各々Ａ（−Ａ）、２Ａ（−２Ａ）になることができない。図３はコーディングスキームに対する多様なビット値を示しているが、本発明の例示的なコーディングスキームは図３に示したビットパターンに限定されない。例えば、ＰＰＩの値“Ａ”に対応するＳＥＬ＿ＰＰ［１：０］は００に代えて１０であり得る。
【００４４】
先に述べたＰＰＩ値を選択するために使われる類似なハミング距離コーディングスキームはＭＭＩの値を選択するのにも適用することができる。
【００４５】
図１は４：１マルチプレクサを例示的に使ったが、本発明はマルチプレクサの特定比の値に限定されない。
【００４６】
一般的な繰り返しで、モジュラスプロセッサ３００及びブースプロセッサ３０１は順次に動作する。しかし、ブースプロセッサ３０１は掛け算器１０００の解答を捜すための繰り返しの性質と隔たる。本発明の望ましい実施の形態によるブースプロセッサ３０１は部分積の最下位２ビットＰＰＩ[１：０]を提供し、これは累算器１００によって提供された以前繰り返しの累算の結果ＳＩ[１：０]と足されて、ＳＰＰＩ[１：０]が発生される。本発明の実施の形態で、ＳＰＰＩを発生するために使われるビットの数は多様に変更することができる。レジスタ７が右側に３ビットシフトされる間、ＳＰＰＩ[１：０]はモジュラスプロセッサ３００によって使われる。レジスタ７がシフトされた後、モジュラスプロセッサ３００の活性化と独立的に、新しい値Ｂ[０]、Ｂ[１]及びＢ[ｒ]がブースプロセッサ３０１に入力される。したがって、モジュラスプロセッサ３００が動作される間ブースプロセッサ３０１は動作される。パイプラインレジスタ２２０はブースプロセッサ３０１の出力ＳＥＬ＿ＰＰ[１：０]、ＥＮ＿ＰＰ、ＮＥＧ＿ＰＰ及びＰＰＩ[１：０]をサブレジスタ６４〜６７に各々貯蔵する。パイプラインレジスタはグラッチ減少によって掛け算器のハードウェア性能を向上させる。グラッチは信号が調整される間、計算での遅延による信号の一時的ミスマッチングの結果である。上述の段階はＢ[１]が乗数Ｂの最上位ビットであるまで繰り返される。ブースプロセッサ３０１とモジュラスプロセッサ３００の同時的動作は掛け算器１０００全体の計算速度を向上させる。
【００４７】
上述のように、掛け算器１０００はマルチプルモジュラスＭＭＩ及び部分積ＰＰＩを入力にする。先ず、ＰＰＩ及びＭＭＩが累算器１００に入力される。ＭＭＩを計算するため、先ず、第１論理演算でＰＰＩが計算され、第２論理演算でＰＰＩ及びＳＩが結合する。 電力消耗が増加することは累算器１００が論理演算を二度実行するためである。二つの値が同時に入力されないことは、各々の回路経路が異なるためである。もしＰＰＩ及びＭＭＩの値が同時に、または十分に近接するように累算器１００に入力されれば電力消耗は減少する。
【００４８】
本発明の実施の形態で、同期化レジスタ２２０、２１０はＰＰＩ及びＭＭＩが累算器１００で動作する時間を同期化する。ブースプロセッサ３０１は上述のように、部分積ＰＰＩを選択するためＳＥＬ＿ＰＰ[１：０]及びＥＮ＿ＰＰをマルチプレクサ２０とＡＮＤゲート３２に各々提供する。また、モジュラスプロセッサ３００はマルチプルモジュラス値ＭＭＩを選択するためＳＥＬ＿ＭＭ[１：０]及びＥＮ＿ＭＭをマルチプレクサ１０及びＡＮＤゲート３１に各々提供する。もし部分積同期化レジスタ２２０が使われれば、ＳＥＬ＿ＰＰ[１：０]及びＥＮ＿ＰＰはサブレジスタ６４、６５に貯蔵される。本発明の実施の形態では、モジュラスプロセッサ３００およびブースプロセッサ３０１の両方に同期化レジスタ２１０、２２０を使用したが、これに限定されず、一つの同期化レジスタとすることができる。両方に同期化レジスタが使われる実施の形態で、ＳＥＬ＿ＰＰ[１：０]及びＳＥＬ＿ＭＭ[１：０]はサブレジスタ６８、６２に各々貯蔵され、ＥＮ＿ＰＰ[１：０]及びＥＮ＿ＭＭ[１：０]はサブレジスタ６９、６３に各々貯蔵される。 クロック信号ＣＫに応答してＳＥＬ＿ＰＰ[１：０]及びＳＥＬ＿ＭＭ[１：０]は十分に同時にマルチプレクサ２０とマルチプレクサ１０に各々入力され、ＥＮ＿ＰＰ及びＥＮ＿ＭＭは十分に同時にＡＮＤゲート３２、３１に各々入力される。マルチプレクサ２０、１０及びＡＮＤゲート３１、３２の出力は同時に出力される。したがって、ＭＭＩ及びＰＰＩは同期化されて累算器１００に供給される。したがって、データセットＭＭＩ及びＰＰＩ当り一つの論理演算を実行することができ (従来では二度の論理演算が実行される)、掛け算器１０００の電力消耗が減少する。
【００４９】
本発明の望ましい実施の形態はレディックスモンゴメリ掛け算に限定されない。例えば、図４は乗数値Ｂを貯蔵するためのマルチプルモジュラス同期化レジスタ３６、および／または他の同期化レジスタ３７を有するレディックス−２システムを示している。上述のように、同期化レジスタ３６、３７はＰＰＩ及びＭＭＩ値を十分に同時に累算器２００に提供するために使われ、掛け算器２０００の電力消耗を減少させ、計算速度を向上させる。さらに、本発明の望ましい実施の形態で、同期化レジスタは一つまたは二つを使う。
【００５０】
例示的な望ましい実施の形態を利用して本発明を説明したが、本発明の範囲は開示された実施の形態に限定されない。したがって、特許請求の範囲はそのような変形例及び類似の構成全部を含むように、可能な限り幅広く解釈されなければならない。例えば、マルチプレクサ１０、２０は多様な形態に変更することができる。マルチプルモジュラス同期化サブレジスタ６２は付加的に分離されたマルチプルモジュラスフィードバックレジスタ６１を具備せず、マルチプルモジュラスフィードバックレジスタとして使うことができる。さらに、サブレジスタ６８及びフィードバックレジスタ６４に対する必要性をなくすために部分積フィードバックレジスタ６４は部分積同期化レジスタ２２０のサブレジスタとして使うことができる。同期化レジスタ２１０、２２０はパイプラインレジスタ、および／またはフィードバックレジスタのような他のレジスタを備えることなく使うことができる。
【図面の簡単な説明】
【００５１】
【図１】本発明の望ましい実施の形態によるモジュラ掛け算器を示す図である。
【図２】本発明の望ましい実施の形態によるマルチプルモジュラスＭＭＩの選択基準を説明するテーブルを示す図である。
【図３】本発明の望ましい実施の形態による部分積ＰＰＩの選択基準を説明するテーブルを示す図である。
【図４】本発明の望ましい実施の形態によるレディックス−２モジュラ掛け算器を示す図である。
【符号の説明】
【００５２】
１，３，７    レジスタ
１０，２０    マルチプレクサ
３１，３２    ＡＮＤゲート
４０    ２ビット加算器
６１    フィードバックレジスタ
６２，６３    サブレジスタ
６４    フィードバックレジスタ（サブレジスタ）
６５，６６，６７    サブレジスタ
６８，６９    サブレジスタ
７０    モジュラスレコーダ
８０    ブースレコーダ
１００    累算器
２１０    同期化レジスタ
２２０    同期化レジスタ
３００    モジュラスプロセッサ
３０１    ブースプロセッサ
１０００    モジュラ掛け算器
３６，３７    同期化レジスタ
２０００    掛け算器
【図１】
2004334212.tif 000008
【図２】
2004334212.tif 000009
【図３】
2004334212.tif 000010
【図４】
2004334212.tif 000011