(57)【特許請求の範囲】
【請求項１】
ｎより小さい整数ｘに関して法ｎの剰余Ｘ＝ｘ２ ｍｏｄ ｎの演算を実行するための剰余演算装置であって、
ｎ、ａ、ｂは正の整数であり、０＜ａ＜ｂ、ｇｃｄ（ｎ＋ａ、ｎ＋ｂ）＝１である場合、
前記ｘ２に関連する法ｎ＋ａの剰余演算を実行するとともに、この実行により得られた法ｎ＋ａに関する剰余表現を中国人剰余定理で法ｎ＋ａの２進数表現ｓｘａに変換する第１の変換手段と、
前記ｘ２に関連する法ｎ＋ｂの剰余演算を実行するとともに、この実行により得られた法ｎ＋ｂに関する剰余表現を中国人剰余定理で法ｎ＋ｂの２進数表現ｓｘｂに変換する第２の変換手段と、
前記第１の変換手段および第２の変換手段により変換された２進数表現ｓｘａ、ｓｘｂに基づいて、ｂｓｘａ-ａｓｘｂをｎで割った商ｚおよび剰余ｒを算出する第１の演算手段と、
前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｘａ、ｓｘｂに関連した条件式ｓｘａ−ｓｘｂ＋ｚ≧０が成り立つ場合には、ｓ＝ｒとして剰余を算出する第２の演算手段と
を備えることを特徴とする剰余演算装置。
【請求項２】
前記第２の演算手段は、前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｘａ、ｓｘｂに関連した条件式ｓｘａ−ｓｘｂ＋ｚ＜０かつｒ＋ｃ＜ｎ（ｃはａ・ｂをｎで除した余り）が成り立つ場合には、ｓ＝ｒ＋ｃとして剰余を算出することを特徴とする請求項１に記載の剰余演算装置。
【請求項３】
前記第２の演算手段は、前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｘａ、ｓｘｂに関連した条件式ｓｘａ−ｓｘｂ＋ｚ＜０かつｒ＋ｃ＞ｎ（ｃはａ・ｂをｎで除した余り）が成り立つ場合には、ｓ＝ｒ＋ｃ−ｎとして剰余を算出することを特徴とする請求項１または２に記載の剰余演算装置。
【請求項４】
ｎより小さい整数ｘおよびｕに関して法ｎの剰余演算Ｘ＝ｘ・ｕ ｍｏｄ ｎを実行するための剰余演算装置であって、
ｎ、ａ、ｂは正の整数であり、０＜ａ＜ｂ、ｇｃｄ（ｎ＋ａ、ｎ＋ｂ）＝１である場合、前記ｘ・ｕに関連する法ｎ＋ａの剰余演算を実行するとともに、この実行により得られた法ｎ＋ａに関する剰余表現を中国人剰余定理で法ｎ＋ａの２進数表現ｓｕａに変換する第１の変換手段と、
前記ｘ・ｕに関連する法ｎ＋ｂの剰余演算を実行するとともに、この実行により得られた法ｎ＋ｂに関する剰余表現を中国人剰余定理で法ｎ＋ｂの２進数表現ｓｕｂに変換する第２の変換手段と、
前記第１の変換手段および第２の変換手段により変換された２進数表現ｓｕａおよびｓｕｂに基づいて、ｂｓｕａ-ａｓｕｂをｎで割った商ｚおよび剰余ｒを算出する第１の演算手段と、
前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｕａ、ｓｕｂに関連した条件式ｓｕａ−ｓｕｂ＋ｚ≧０が成り立つ場合には、ｓ＝ｒとして剰余を算出する第２の演算手段と
を備えることを特徴とする剰余演算装置。
【請求項５】
前記第２の演算手段は、前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｕａ、ｓｕｂに関連した条件式ｓｕａ−ｓｕｂ＋ｚ＜０かつｒ＋ｃ＜ｎ（ｃはａ・ｂをｎで除した余り）が成り立つ場合には、ｓ＝ｒ＋ｃとして剰余を算出することを特徴とする請求項４に記載の剰余演算装置。
【請求項６】
前記第２の演算手段は、第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｕａ、ｓｕｂに関連した条件式ｓｕａ−ｓｕｂ＋ｚ＜０かつｒ＋ｃ＞ｎ（ｃはａ・ｂをｎで除した余り）が成り立つ場合には、ｓ＝ｒ＋ｃ−ｎとして剰余を算出することを特徴とする請求項４または５記載の剰余演算装置。
【請求項７】
ｎより小さい整数ｘに関して法ｎの剰余Ｘ＝ｘ２ ｍｏｄ ｎの演算を実行するための剰余演算装置であって、ｎ、ａ、ｂは正の整数であり、０＜ａ＜ｂ、ｇｃｄ（ｎ＋ａ、ｎ＋ｂ）＝１である場合、前記ｘ２に関連する法ｎ＋ａの剰余演算を実行するとともに、この実行により得られた法ｎ＋ａに関する剰余表現を中国人剰余定理で法ｎ＋ａの２進数表現ｓｘａに変換する第１の変換手段と、前記ｘ２に関連する法ｎ＋ｂの剰余演算を実行するとともに、この実行により得られた法ｎ＋ｂに関する剰余表現を中国人剰余定理で法ｎ＋ｂの２進数表現ｓｘｂに変換する第２の変換手段と、前記第１の変換手段および第２の変換手段により変換された２進数表現ｓｘａ、ｓｘｂに基づいて、ｂｓｘａ-ａｓｘｂをｎで割った商ｚおよび剰余ｒを算出する第１の演算手段と、前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｘａ、ｓｘｂに関連した条件式ｓｘａ−ｓｘｂ＋ｚ≧０が成り立つ場合には、ｓ＝ｒとして剰余を算出する第２の演算手段とを備える剰余演算装置であるコンピュータに、
前記第１の変換手段が、前記ｘ２に関連する法ｎ＋ａの剰余演算を実行するとともに、この実行により得られた法ｎ＋ａに関する剰余表現を中国人剰余定理で法ｎ＋ａの２進数表現ｓｘａに変換する機能と、
前記第２の変換手段が、前記ｘ２に関連する法ｎ＋ｂの剰余演算を実行するとともに、この実行により得られた法ｎ＋ｂに関する剰余表現を中国人剰余定理で法ｎ＋ｂの２進数表現ｓｘｂに変換する機能と、
前記第１の演算手段が、前記第１の変換機能および第２の変換機能により変換された２進数表現ｓｘａ、ｓｘｂに基づいて、ｂｓｘａ-ａｓｘｂをｎで割った商ｚおよび剰余ｒを算出する機能と、
前記第２の演算手段が、前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｘａ、ｓｘｂに関連した条件式に基づいて、条件式ｓｘａ−ｓｘｂ＋ｚ≧０が成り立つ場合には、ｓ＝ｒとして剰余を算出する機能と
を実現させることを特徴とするプログラム。
【請求項８】
ｎより小さい整数ｘおよびｕに関して法ｎの剰余演算Ｘ＝ｘ・ｕ ｍｏｄ ｎを実行するための剰余演算装置であって、ｎ、ａ、ｂは正の整数であり、０＜ａ＜ｂ、ｇｃｄ（ｎ＋ａ、ｎ＋ｂ）＝１である場合、前記ｘ２に関連する法ｎ＋ａの剰余演算を実行するとともに、この実行により得られた法ｎ＋ａに関する剰余表現を中国人剰余定理で法ｎ＋ａの２進数表現ｓｕａに変換する第１の変換手段と、前記ｘ２に関連する法ｎ＋ｂの剰余演算を実行するとともに、この実行により得られた法ｎ＋ｂに関する剰余表現を中国人剰余定理で法ｎ＋ｂの２進数表現ｓｕｂに変換する第２の変換手段と、前記第１の変換手段および第２の変換手段により変換された２進数表現ｓｕａ、ｓｕｂに基づいて、ｂｓｕａ-ａｓｕｂをｎで割った商ｚおよび剰余ｒを算出する第１の演算手段と、前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｕａ、ｓｕｂに関連した条件式ｓｕａ−ｓｕｂ＋ｚ≧０が成り立つ場合には、ｓ＝ｒとして剰余を算出する第２の演算手段とを備える剰余演算装置であるコンピュータに、
前記第１の変換手段が、前記ｘ・ｕに関連する法ｎ＋ａの剰余演算を実行するとともに、この実行により得られた法ｎ＋ａに関する剰余表現を中国人剰余定理で法ｎ＋ａの２進数表現ｓｕａに変換する機能と、
前記第２の変換手段が、前記ｘ・ｕに関連する法ｎ＋ｂの剰余演算を実行するとともに、この実行により得られた法ｎ＋ｂに関する剰余表現を中国人剰余定理で法ｎ＋ｂの２進数表現ｓｕｂに変換する機能と、
前記第１の演算手段が、前記第１の変換機能および第２の変換機能により変換された２進数表現ｓｕａおよびｓｕｂに基づいて、ｂｓｕａ-ａｓｕｂをｎで割った商ｚおよび剰余ｒを求める機能と、
前記第２の演算手段が、前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｕａ、ｓｕｂに関連した条件式ｓｕａ−ｓｕｂ＋ｚ≧０が成り立つ場合には、ｓ＝ｒとして剰余を算出する機能と
を実現させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、平方剰余算（ｓ＝ｘ２ ｍｏｄ ｎ）および剰余乗算（ｓ＝ｘ・ｕ ｍｏｄ ｎ
）を高速に処理するための剰余演算装置およびプログラムに関する。
【背景技術】
【０００２】
情報通信ネットワークや計算機システムでは、情報の盗聴や改ざんを阻止するため、通常
、公開鍵暗号方式が用いられている。ここで、公開鍵暗号方式は、ＲＳＡ暗号やエルガマ
ル（ＥｌＧａｍａｌ）暗号などのように暗号方式それ自体と、デジタル署名方式や鍵配送
方式などのように暗号方式を適用したものとが含まれる。また、ＲＳＡ暗号やエルガマル
暗号を含む著名な公開暗号方式の説明は例えば非特許文献１のｐｐ．２５３−３１２に詳
しい。
【０００３】
この種の公開鍵暗号方式では、一般に、べき乗剰余算や剰余乗算を扱うことが多い。よっ
て、暗号方式の高速化を図る観点から、べき乗剰余算や剰余乗算の高速化が古くより研究
され、数々の手法が提案されている。
【０００４】
一例として、べき乗剰余算や剰余乗算のうち、べき乗剰余算の高速化について説明する。なお、べき乗剰余算γｅ ｍｏｄ ｎに含まれる、べき乗剰余算γｅを高速に行う種々の手法は、例えば非特許文献１のｐｐ．６１３−６２７に詳しい。但し、ここでは、平方と乗算との効果的な組合せにより、べき乗算ｇｅの乗算回数を削減する一般的な手法を述べる。この乗算回路の削減手法は、固定される値に応じ、異なる手法が有効となっている。
【０００５】
例えば、ＲＳＡ暗号のように、べき乗算γｅのべき指数ｅが固定される場合には、加算
鎖（ａｄｄｉｔｉｏｎ  ｃｈａｉｎ）を用いて、べき乗算γｅに必要な乗算回数を減らす
方法が有効である。
【０００６】
また、エルガマル暗号やディフィー−へルマン（Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）鍵交
換のように、べき乗算γｅの底γが固定される場合には、乗算の一部を事前演算してテー
ブルに登録し、演算時に適宜参照することにより、乗算回数を減らす方法が有効である。
なお、ディフィー−へルマン鍵交換については、例えば非特許文献１のｐｐ．５１５−５
２４に詳しい。
【０００７】
さて、このように演算の高速化を図る研究の中で、法ｎでの平方および乗算を２つの法
ｎ＋１，ｎ＋２に関する剰余で補間する新しい手法（以下、「林法」と呼ぶ）が提案され
ている。この林法は、法ｎより大きい整数ｎ＋１，ｎ＋２がそれぞれ互いに素な整数に因
数分解できるときに、これらｎ＋１，ｎ＋２を法とする剰余算を中国人剰余定理により、
高速に算出できることを利用し、法ｎでの平方および乗算を高速化する手法である。なお
、林法は、特許文献１に詳しい。
【０００８】
さらに、林法における法ｎ＋１，ｎ＋２等のパラメータの設定を容易にする手法が非特
許文献２（以下、「清水法」ということもある）により提案されている。この非特許文献
２による手法は、林法の拡張により、２つの法ｎ＋ａ，ｎ＋ａ＋１を用いて、法ｎでの平
方および乗算を高速化するものである。
【０００９】
これら林法および清水法は、従来とは異なり、平方剰余算や剰余乗算を中国人剰余定理
により高速化するものであり、また、それぞれ他の高速化の手法との組合せが可能となっ
ている。
【００１０】
ここで、林法では、ＲＳＡ暗号の法ｎの場合、公開鍵（ｅ，ｎ）を定めた段階で、補間
する２つの法ｎ＋１，ｎ＋２の最大素因数がどれだけ小さいか、またどれだけ多くの互い
に素な整数に分解できるか、という２つの期待する条件に依存する。よって、林法では、
演算速度をより高めたい場合、これら２つの期待する条件に見合う方向で、予め法ｎの鍵
生成に何らかの制約を加える必要がある。
【００１１】
一方、清水の手法は、法ｎが定まった後でも２つの法ｎ＋ａ，ｎ＋ａ＋１を高速に設定可能な理論的な演算アルゴリズムが動作する。従って、清水の手法は、林法に比べ、補間する２つの法の設定が柔軟かつ容易になっている。
【非特許文献１】Ａ．Ｊ．Ｍｅｎｅｚｅｓ, Ｐ．Ｃ．  ｖａｎ  Ｏｏｒｓｃｈｏｔ  ａｎｄ  Ｓ．Ａ．Ｖａｎｓｔｏｎｅ, Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｈｐｙ,ＣＲＣ  Ｐｒｅｓｓ  ＬＬＣ,１９９７
【非特許文献２】清水秀夫、並列剰余乗算のための林法の拡張、１９９９年電子情報通信学会基礎・境界ソサイエティ大会、Ｐ．１１４、１９９９
【特許文献１】特開平１０−２５４６８３号公報
【特許文献２】特開２００３−２１６０３３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
林法およびその拡張である清水法では、補間する２つの法の最大素因数がどれだけ小さいか、またどれだけ多くの互いに素な整数に分解できるかに演算速度は依存する。林法では法ｎに対して一意に補間する２つの法が定まってしまうため、前記演算速度を向上させるような法ｎの生成法を別途工夫する必要がある。また清水法では、２つの法の差が１という制約条件に縛られるため、前記演算速度が期待レベルに達するような法ｎ＋ａ、ｎ＋ａ＋１を設定することが実用的に困難である。この課題を解決すべく、
【特許文献２】にて我々は、２つの法をｎ＋ａ、ｎ＋ｂという一般形に拡張し、演算速度を向上させるための２つの法選択に関して、清水法に比べて大幅な自由度を与えた。しかし、当該発明でもａおよびｂがｎ１／２未満という条件があるため、実用に十分適した方式とはいえない。
【課題を解決するための手段】
【００１３】
上述した課題を解決するために、本発明は、ｎより小さい整数ｘに関して法ｎの剰余Ｘ＝ｘ２ ｍｏｄ ｎの演算を実行するための剰余演算装置であって、ｎ、ａ、ｂは正の整数であり、０＜ａ＜ｂ、ｇｃｄ（ｎ＋ａ、ｎ＋ｂ）＝１である場合、前記ｘ２に関連する法ｎ＋ａの剰余演算を実行するとともに、この実行により得られた法ｎ＋ａに関する剰余表現を中国人剰余定理で法ｎ＋ａの２進数表現ｓｘａに変換する第１の変換手段と、前記ｘ２に関連する法ｎ＋ｂの剰余演算を実行するとともに、この実行により得られた法ｎ＋ｂに関する剰余表現を中国人剰余定理で法ｎ＋ｂの２進数表現ｓｘｂに変換する第２の変換手段と、前記第１の変換手段および第２の変換手段により変換された２進数表現ｓｘａ、ｓｘｂに基づいて、ｂｓｘａ-ａｓｘｂをｎで割った商ｚおよび剰余ｒを算出する第１の演算手段と、前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｘａ、ｓｘｂに関連した条件式ｓｘａ−ｓｘｂ＋ｚ≧０が成り立つ場合には、ｓ＝ｒとして剰余を算出する第２の演算手段とを備えることを特徴とする。また、第２の演算手段は、第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｘａ、ｓｘｂに関連した条件式ｓｘａ−ｓｘｂ＋ｚ＜０かつｒ＋ｃ＜ｎ（ｃはａ・ｂをｎで除した余り）が成り立つ場合には、ｓ＝ｒ＋ｃとして剰余を算出することも特徴とする。さらに、第２の演算手段は、前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｘａ、ｓｘｂに関連した条件式ｓｘａ−ｓｘｂ＋ｚ＜０かつｒ＋ｃ＞ｎ（ｃはａ・ｂをｎで除した余り）が成り立つ場合には、ｓ＝ｒ＋ｃ−ｎとして剰余を算出することも特徴とする。
【００１４】
さらに、本発明は、ｎより小さい整数ｘおよびｕに関して法ｎの剰余演算Ｘ＝ｘ・ｕ ｍｏｄ ｎを実行するための剰余演算装置であって、ｎ、ａ、ｂは正の整数であり、０＜ａ＜ｂ、ｇｃｄ（ｎ＋ａ、ｎ＋ｂ）＝１である場合、前記ｘ２に関連する法ｎ＋ａの剰余演算を実行するとともに、この実行により得られた法ｎ＋ａに関する剰余表現を中国人剰余定理で法ｎ＋ａの２進数表現ｓｕａに変換する第１の変換手段と、前記ｘ２に関連する法ｎ＋ｂの剰余演算を実行するとともに、この実行により得られた法ｎ＋ｂに関する剰余表現を中国人剰余定理で法ｎ＋ｂの２進数表現ｓｕｂに変換する第２の変換手段と、前記第１の変換手段および第２の変換手段により変換された２進数表現ｓｕａおよびｓｕｂに基づいて、ｂｓｕａ-ａｓｕｂをｎで割った商ｚおよび剰余ｒを算出する第１の演算手段と、前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｕａ、ｓｕｂに関連した条件式ｓｕａ−ｓｕｂ＋ｚ≧０が成り立つ場合には、ｓ＝ｒとして剰余を算出する第２の演算手段とを備えることを特徴とする。また、第２の演算手段は、前記第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｕａ、ｓｕｂに関連した条件式ｓｕａ−ｓｕｂ＋ｚ＜０かつｒ＋ｃ＜ｎ（ｃはａ・ｂをｎで除した余り）が成り立つ場合には、ｓ＝ｒ＋ｃとして剰余を算出することも特徴とする。さらに、第２の演算手段は、第１の演算手段によって得た商ｚおよび剰余ｒ、前記変換された２進数表現ｓｕａ、ｓｕｂに関連した条件式ｓｕａ−ｓｕｂ＋ｚ＜０かつｒ＋ｃ＞ｎ（ｃはａ・ｂをｎで除した余り）が成り立つ場合には、ｓ＝ｒ＋ｃ−ｎとして剰余を算出することも特徴としている。
【００１５】
なお、上記は、本発明を「装置」として記載したが、何もカテゴリーは「装置」だけに限
らず、「プログラム」、「プログラムを記憶したコンピュータ読み取り可能な記憶媒体」
又は「方法」として表現してもよい。
【発明の効果】
【００１６】
本発明によれば、従来におけるｎ＋ａ、ｎ＋ｂのパラメータａ、ｂの選択範囲をｎ１／２
倍であるまで引き上げ、実用的に問題のない演算高速化を行うことができる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の各実施形態について図面を用いて説明するが、その前に、各実施形態の
前提となる関係式について述べる。始めに、中国人剰余定理（Ｃｈｉｎｅｓｅ  ｒｅｍａ
ｉｎｄｅｒ  ｔｈｅｏｒｅｍ）について説明する。
【００１８】
中国人剰余定理とは、互いに素なｋ個の整数π１、π２、…、πｋが存在する時、以下
の各式を満たす整数α（０≦α＜π１π２…πｋ）が一意に定まるというものである。
【００１９】
α≡β１ｍｏｄ π１
α≡β２ｍｏｄ π２
…
α≡βｋｍｏｄ πｋ
以上が中国人剰余定理の内容であるが、ここでｎ＝π１π２…πｋとすると、αは図９
の式（イ）で定まることが知られている。但し、Ｎｉ＝ｎ／πｉ、Ｍｉ＝Ｎｉ−１ｍｏｄ
πｉである。
【００２０】
これは、ガウスのアルゴリズムとも呼ばれている。続いて、各実施形態の概略について
述べる。概略的に、各実施形態は、演算対象Ｘに対する法ｎの剰余演算Ｘ  ｍｏｄ  ｎの
際に、新たな２つの法ｎ＋ａおよびｎ＋ｂを用いてＸ  ｍｏｄ  （ｎ＋ａ）およびＸ  ｍ
ｏｄ  （ｎ＋ｂ）とを効率的に算出し、中国人剰余定理によりこの算出結果を用いて本来
目的である剰余演算Ｘ  ｍｏｄ  ｎを高速に処理するものである。
【００２１】
ここで、演算対象Ｘ＝ｘ２（平方剰余演算）またはＸ＝ｘ・ｕ（剰余乗算）であり、各
ｘは０≦ｘ＜ｎの範囲にある。
【００２２】
また、法ｎ＋ａおよびｎ＋ｂは、事前に演算されるが、いずれも互い素な整数の積に分
解可能な値とする。具体的には、図９の式（ロ）及び式（ハ）に示すように、法ｎ＋ａは
ｈ個の整数ｐｉ（ｉ＝０、…、ｈ）に分解可能であり、さらに、法ｎ＋ｂはｍ個の整数ｑ
ｊ（ｊ＝０、…、ｍ）に分解可能であるとする。但し、必ずしも素因数分解できなくても
よい。
【００２３】
なお、法ｎ＋ａおよびｎ＋ｂの因数分解を行う機能は、Ｘｍｏｄｎを演算する装置に必
ずしも備わっている必要はない。例えば、法ｎを決定した装置が法ｎ＋ａおよびｎ＋ｂを
各因数ｐｉおよびｑｊに分解し、得られたｐｉおよびｑｊを法ｎと同様に入手可能な公開
パラメータとして設定しておいてもよい。
【００２４】
ここで、各実施形態の前提となる各関係式を［補題］、［補題の証明］、［定理］およ
び［定理の証明］の形式を用いて説明する。なお、以下の［補題］、［補題の証明］、［
定理］および［定理の証明］は、数学上の根拠記載である。
【００２５】
［補題］
ｎ、ａ、ｂを正の整数とし、０＜ａ＜ｂ、ｇｃｄ（ｎ＋ａ、ｎ＋ｂ）＝１とする。またｘ
を０≦ｘ＜（ｎ＋ａ）（ｎ＋ｂ）なる整数とする時、整数ｘａ、ｘｂ、ｘ’を以下のよう
に定める。
【００２６】
ｘａ＝ｘ／（ｂ−ａ）ｍｏｄ （ｎ＋ａ）
ｘｂ＝ｘ／（ｂ−ａ）ｍｏｄ （ｎ＋ｂ）
ｘ’＝（ｎ＋ｂ）ｘａ−（ｎ＋ａ）ｘｂ
この時、次式が成り立つ。
【００２７】
ｘ＝ｘ’＋ｔ（ｎ＋ａ）（ｎ＋ｂ）        （１）
但し、整数ｔは次の値を取る。
【００２８】
ｔ＝０ （ｘ’≧０）または
ｔ＝１ （ｘ’＜０）
［補題の証明］
ｘ’≡（ｎ＋ｂ）ｘａ ≡ｘ（ｍｏｄ （ｎ＋ａ））
同様にして、ｘ’≡ｘ（ｍｏｄ （ｎ＋ｂ））で、ｇｃｄ（ｎ＋ａ、ｎ＋ｂ）＝１であるから、ｘ’≡ｘ（ｍｏｄ （ｎ＋ａ）（ｎ＋ｂ））と置くことができる。０≦ｘ＜（ｎ＋ａ）（ｎ＋ｂ）なる条件により、整数ｔは次の値を取る。
【００２９】
ｔ＝０ （ｘ’≧０）または
ｔ＝１ （ｘ’＜０）
［定理］
前記補題と同じ条件下で、次式が成り立つ。
【００３０】
ｘ’≡ｂｘａ−ａｘｂ＋ｔａｂ（ｍｏｄ ｎ）        （２）
ここで、ｂｘａ−ａｘｂをｎで割った商をｚ、余りをｒ（０≦ｒ＜ｎ）とおくと、次式が
成り立つ。
【００３１】
ｔ＝０ （ｘａ−ｘｂ＋ｚ≧０）
ｔ＝１ （ｘａ−ｘｂ＋ｚ＜０）
さらにａｂをｎで割った余りをｃとおくと、次の式（３）が成り立つ。
【００３２】
ｘ（ｍｏｄ  ｎ）＝ｒ、ｒ＋ｃ、またはｒ＋ｃ−ｎ        （３）
式（３）の演算結果は、次の３通りに場合分けされる。
【００３３】
ｒ  （ｘａ−ｘｂ＋ｚ≧０）
ｒ＋ｃ （ｘａ−ｘｂ＋ｚ＜０、ｒ＋ｃ＜ｎ）
ｒ＋ｃ−ｎ （ｘａ−ｘｂ＋ｚ＜０、ｒ＋ｃ＞ｎ）
［定理の証明］
定理の式（２）は、補題の式（１）の右辺をｍｏｄ ｎして得られる。ｔの値および式
（３）を証明する。
【００３４】
まず、ｘ’の定義から次の式（４）を得る。
【００３５】
ｘ’＝（ｎ＋ｂ）ｘａ−（ｎ＋ａ）ｘｂ
＝ｎ（ｘａ−ｘｂ）＋ｂｘａ−ａｘｂ        （４）
また定理で定義したｚおよびｒの関係式から次の式（５）を得る。
【００３６】
ｂｘａ−ａｘｂ＝ｚｎ＋ｒ        （５）
前記式（４）に式（５）を代入すると、次の式（６）が得られる。
【００３７】
ｘ’＝ｎ（ｘａ−ｘｂ＋ｚ）＋ｒ        （６）
前記式（６）と条件０≦ｒ＜ｎから次の関係が導かれる。
【００３８】
ｘ’≧０ （ｘａ−ｘｂ＋ｚ≧０）または
ｘ’＜０ （ｘａ−ｘｂ＋ｚ＜０）
この関係は、補題のｔの条件からそれぞれがｔ＝０、１に対応することが分かる（ｋの
値の証明）。
【００３９】
また、式（５）を式（２）に代入すると次の式（７）が得られる。
【００４０】
ｘ≡ｚｎ＋ｒ＋ｔａｂ≡ｒ＋ｔｃ（ｍｏｄ ｎ）        （７）
定理の仮定ｃ＜ｎより、ｒ＋ｃ−ｎ＜ｎであることが分かる。これと、ｔの条件を組み合
わせると、式（３）が得られる（式（３）の証明）。
【００４１】
以上により、各実施形態の前提となる関係式の説明を終える。続いて、本発明の各実施
形態について説明する。
【００４２】
（第１の実施形態）
図１は、本発明の第１の実施形態に係る剰余演算装置１０の構成を示す模式図である。この剰余演算装置１０は、平方剰余ｘ２ｍｏｄ ｎを高速に算出するものであり、平方剰余入出力管理部１０１、第１剰余演算部１０２、第２剰余演算部１０３、除算部１０４および条件判定演算部１０５を備えている。各部は、それぞれハードウェア、ソフトウェアまたはその組み合わせにより構成可能となっている。ここで、各部がソフトウェアにより構成される場合、後述する各機能を実現させるためのプログラム（剰余演算プログラム）が予め剰余演算装置１０のコンピュータにインストールされている。なお、以下の説明における各種パラメータおよび当該パラメータの意味は、図１０に示す通りである。
【００４３】
ここで、平方剰余入出力管理部１０１は、剰余演算装置１０の外部装置（不図示）から入力された入力データを管理する機能と、図２に示す本発明の第１の実施形態における平方剰余の演算処理フローに基づいて、データおよび演算命令を第１剰余演算部１０２、第２剰余演算部１０３、除算部１０４および条件判定演算部１０５に送信する機能と、第１剰余演算部１０２、第２剰余演算部１０３、除算部１０４および条件判定演算部１０５からの演算結果を受け取り管理する機能と、最終的なｘ２ｍｏｄ ｎの演算結果を出力する機能とをもっている。
【００４４】
ここで、平方剰余入出力管理部１０１は、外部装置（不図示）から入力された入力データ
を当該剰余演算装置１０内に含まれるメモリ（不図示）に一時的に記憶するものとするが
、恒久的に記憶する必要は特にない。ハードディスク装置などの記憶部（不図示）に当該
入力データや最終的な演算結果（平方剰余）を恒久的に記憶しても構わない。以下の各実
施形態においても同様である。
【００４５】
第１剰余演算部１０２は、平方剰余入出力管理部１０１からデータを受け取り、ｎ＋ａ
およびｎ＋ｂの互いに素な各因数ｐｉおよびｑｊを法とする第１剰余群を演算する機能と
、この演算結果である第１剰余群を平方剰余入出力管理部１０１へ出力する機能とをもっ
ている。
【００４６】
第２剰余演算部１０３は、平方剰余入出力管理部１０１から第１剰余演算部１０２が出
力した第１剰余群を含むデータを受け取り、中国人剰余定理を用いて第２剰余群を演算す
る機能と、この演算結果である第２剰余群を平方剰余入出力管理部１０１へ出力する機能
とをもっている。
【００４７】
除算部１０４は、平方剰余入出力管理部１０１から第２剰余演算部１０３が出力した第
２剰余群を含むデータを受け取り、法ｎで割った商と剰余を演算する機能と、この演算結
果である商および剰余を平方剰余入出力管理部１０１へ出力する機能とをもっている。
【００４８】
条件判定演算部１０５は、平方剰余入出力管理部１０１から除算部１０４が出力した剰余を含むデータを受け取り、所定の条件判定式により最終的なｘ２ｍｏｄ ｎを求める機能と、演算結果であるｘ２ ｍｏｄ ｎを平方剰余入出力管理部１０１へ出力する機能とをもっている。
【００４９】
本発明の最終結果であるｘ２ｍｏｄ ｎを出力する剰余演算装置１０における平方剰余
の演算処理手順について図２を用いて説明する。ここで、ｃ＝ａ・ｂ  ｍｏｄ ｎであり
、平方剰余の演算時の処理高速性を高めるため、ｎ＋ａやｎ＋ｂが定まった段階で事前に
演算し、パラメータとして扱う。
【００５０】
始めに、平方剰余入出力管理部１０１は、外部装置（不図示）から演算対象ｘ（０≦ｘ
＜ｎ）と、各パラメータｎ、ｎ＋ａ、ｎ＋ｂ、ａ、ｂ、ｃ、ｐｉ（ｉ＝１、…、ｈ）およ
びｑｊ（ｊ＝１、…、ｍ）を入力として受信する（ＳＴ１）。
【００５１】
ここで、例えばａおよびｂを入力すれば、各パラメータｎ＋ａ、ｎ＋ｂ、ｃ、ｐｉ（ｉ
＝１、…、ｈ）およびｑｊ（ｊ＝１、…、ｍ）が演算可能なので、この演算自体は平方剰
余入出力管理部１０１または図示していないパラメータ演算部が行っても構わない。よっ
て、平方剰余入出力管理部１０１には、必ずしも上述した全ての入力データが必要となる
わけではない。特に、演算対象ｘ以外のデータは予め当該剰余演算装置１０が保持しても
よい。これは、以下の各実施形態も同様である。また、これら以外のデータを入力しても
よい。例えば、当該平方剰余演算の事前演算値（後述）を平方剰余入出力管理部１０１で
管理し、適宜読み出して演算高速化に利用してもよい。
【００５２】
平方剰余入出力管理部１０１は、前記入力データを受信すると、第１剰余演算部１０２
へｘ、ｐｉ（ｉ＝１、…、ｈ）を送信して、第１剰余群ｓｐｉ（ｉ＝１、…、ｈ）の演算
を依頼する。第１剰余演算部１０２は、平方剰余入出力管理部１０１からｘ、ｐｉ（ｉ＝
１、…、ｈ）を受信すると、まず次式のようにｘｐｉ（i＝１、…、ｈ）を演算する（Ｓ
Ｔ２）。
【００５３】
ｘｐｉ＝ｘ ｍｏｄ ｐｉ （i＝１、…、ｈ）
次に、第１剰余演算部１０２は、ｘｐｉ（i＝１、…、ｈ）を用いて、次式のようにｙｘｐｉ を演算する（ＳＴ３）。  
【００５４】
ｙｘｐｉ＝ｘｐｉ２ ｍｏｄ ｐｉ （i＝１、…、ｈ）
さらに、第１剰余演算部１０２は、ｙｘｐｉ（i＝１、…、ｈ）を用いて、次式のように、第１剰余群ｓｘｐｉ（ｉ＝１、…、ｈ）を演算し、この演算結果である第１剰余群ｓｘｐｉ（ｉ＝１、…、ｈ）を平方剰余入出力管理部１０１へ出力する（ＳＴ４）。
【００５５】
ｓｘｐｉ＝ｙｘｐｉ／（ｂ−ａ）ｍｏｄ ｐｉ（i＝１、…、ｈ）
ここで、（ｂ−ａ）−１ｍｏｄ ｐｉ（i＝１、…、ｈ）を事前演算値として事前に演算し
ておき、当該剰余演算装置１０にパラメータとして入力する形態でもよい。これは、以下
の各実施形態も同様である。
【００５６】
平方剰余入出力管理部１０１は、第１剰余演算部１０２から受け取った第１剰余群ｓｘｐｉ（ｉ＝１、…、ｈ）及びｎ＋ａを第２剰余演算部１０３へ送信して、第２剰余ｓｘａの演算を依頼する。第２剰余演算部１０３は、平方剰余入出力管理部１０１からｓｘｐｉ（ｉ＝１、…、ｈ）及びｎ＋ａを受信すると、中国人剰余定理を用いて次式で示される第２剰余ｓｘａを計算し、平方剰余入出力管理部１０１へ出力する（ＳＴ５）。
【００５７】
ｓｘａ＝ｘ２／（ｂ−ａ）ｍｏｄ （ｎ＋ａ）
ここで、（ｂ−ａ）−１ｍｏｄ （ｎ＋ａ）を事前演算値として事前に演算しておき、当
該剰余演算装置１０にパラメータとして入力する形態でもよい。これは、以下の各実施形
態も同様である。
【００５８】
平方剰余入出力管理部１０１は、ＳＴ２からＳＴ５と同様の処理を行い、ｎ＋ｂに対す
る第２剰余ｓｘｂを演算する。すなわち、次のＳＴ６〜ＳＴ９を実行する。この実施形態
では、ＳＴ２〜ＳＴ５の後に続いてＳＴ６〜ＳＴ９の処理が行われており、ＳＴ２〜ＳＴ
５とＳＴ６〜ＳＴ９の処理は直列的に行われている。
【００５９】
平方剰余入出力管理部１０１は、第１剰余演算部１０２へｘ、ｑｊ（ｊ＝１、…、ｍ）
を送信して、第１剰余群ｓｘｑｊ（ｊ＝１、…、ｍ）の演算を依頼する。第１剰余演算部
１０２は、平方剰余入出力管理部１０１からｘ、ｑｊ（ｊ＝１、…、ｍ）を受信すると、
まず次式のようにｘｑｊ（ｊ＝１、…、ｍ）を演算する（ＳＴ６）。
【００６０】
ｘｑｊ＝ｘ ｍｏｄ ｑｊ（ｊ＝１、…、ｍ）
次に、第１剰余演算部１０２は、ｘｑｊ（ｊ＝１、…、ｍ）を用いて、次式のようにｙｑ
ｊを演算する（ＳＴ７）。
【００６１】
ｙｘｑｊ＝ｘｑｊ２ ｍｏｄ ｑｊ（ｊ＝１、…、ｍ）
さらに、第１剰余演算部１０２は、ｙｘｑｊ（ｊ＝１、…、ｍ）を用いて、次式のように
、第１剰余群ｓｘｑｊ（ｊ＝１、…、ｍ）を演算し、この演算結果である第１剰余群ｓｘ
ｑｊ（ｊ＝１、…、ｍ）を平方剰余入出力管理部１０１へ出力する（ＳＴ８）。
【００６２】
ｓｘｑｊ＝ｙｘｑｊ／（ｂ−ａ）ｍｏｄｑｊ（ｊ＝１、…、ｍ）
ここで、（ｂ−ａ）−１ｍｏｄ ｑｊ（ｊ＝１、…、ｍ）を事前演算値として事前に演算
しておき、当該平方剰余演算装置１０にパラメータとして入力する形態でもよい。これは
、以下の各実施形態も同様である。
【００６３】
平方剰余入出力管理部１０１は、第１剰余演算部１０２から受け取った第１剰余群ｓｘ
ｑｊ（ｊ＝１、…、ｍ）およびｎ＋ｂを第２剰余演算部１０３へ送信して、第２剰余ｓｘ
ｂの演算を依頼する。第２剰余演算部１０３は、平方剰余入出力管理部１０１からｓｘｑ
ｊ（ｊ＝１、…、ｍ）およびｎ＋ｂを受信すると、中国人剰余定理を用いて次式で示され
る第２剰余ｓｘｂを演算し、平方剰余入出力管理部１０１へ出力する（ＳＴ９）。
【００６４】
ｓｘｂ＝ｘ２／（ｂ−ａ）ｍｏｄ （ｎ＋ｂ）
ここで、（ｂ−ａ）−１ｍｏｄ （ｎ＋ｂ）を事前演算値として事前に演算しておき、当
該剰余演算装置１０にパラメータとして入力する形態でもよい。これは、以下の各実施形
態も同様である。
【００６５】
次に、平方剰余入出力管理部１０１は、ｎ、ａ、ｂ、ｓｘａおよびｓｘｂを除算部１０４に送信する。除算部１０４は、平方剰余入出力管理部１０１から受信したｎ、ａ、ｂ、ｓｘａ およびｓｘｂ を用いて、ｂ・ｓｘａ−ａ・ｓｘｂをｎで割った商ｚおよび剰余ｒを求め、平方剰余入出力管理部１０１に出力する（ＳＴ１０）。
【００６６】
平方剰余入出力管理部１０１は、ｎ、ａ、ｂ、ｃ、ｓｘａ、ｓｘｂ、ｚおよびｒを条件判定演算部１０５に送信し、最終演算値ｓ＝ｘ２（ｍｏｄ ｎ）の出力を要求する。条件判定演算部１０５は、平方剰余入出力管理部１０１から受信したｓｘａ、ｓｘｂ、ｚ、ｒ、ｃおよびｎの以下に示す条件判定により、ｓｘａ−ｓｘｂ＋ｚ≧０ならばｓ＝ｒとして平方剰余入出力管理部１０１に出力し（ＳＴ１１−１）、ｓｘａ−ｓｘｂ＋ｚ＜０且つｒ＋ｃ＜ｎならばｓ＝ｒ＋ｃとして平方剰余入出力管理部１０１に出力し（ＳＴ１１−２）、ｓｘａ−ｓｘｂ ＋ｚ＜０且つｒ＋ｃ＞ｎならばｓ＝ｒ＋ｃ−ｎとして平方剰余入出力管理部１０１に出力する（ＳＴ１１−３）。
【００６７】
なお、本実施形態は、例えば、ｓｘａを求める手順（ＳＴ２からＳＴ５）の前に、ｓｘ
ｂを求める手順（ＳＴ６からＳＴ９）を行う等、演算において支障をきたさない部分は、
逐次演算順序を変更してもよい。これは以下の実施形態でも同様である。
【００６８】
（第２の実施形態）
図３は、本発明の第２の実施形態に係る剰余演算装置２０の構成を示す模式図である。こ
の剰余乗算装置２０は、剰余乗算ｘ・ｕ ｍｏｄ ｎを高速に算出するものであり、剰余乗
算入出力管理部２０１、第１剰余演算部２０２、第２剰余演算部２０３、除算部２０４お
よび条件判定演算部２０５を備えている。各部は、それぞれハードウェア、ソフトウェア
またはその組み合わせにより構成可能となっている。ここで、各部がソフトウェアにより
構成される場合、後述する各機能を実現させるためのプログラム（剰余演算プログラム）
が予め剰余乗算装置２０のコンピュータにインストールされている。
【００６９】
ここで、剰余乗算入出力管理部２０１は、剰余演算装置２０の外部装置（不図示）から入力された入力データを管理する機能と、図４に示す本発明の第２の実施形態における剰余乗算の演算処理フローに基づいて、データおよび演算命令を第１剰余演算部２０２、第２剰余演算部２０３、除算部２０４および条件判定演算部２０５に送信する機能と、第１剰余演算部２０２、第２剰余演算部２０３、除算部２０４および条件判定演算部２０５からの演算結果を受け取り管理する機能と、最終的なｘ・ｕ ｍｏｄ ｎの演算結果を出力する機能とをもっている。
【００７０】
第１剰余演算部２０２は、剰余乗算入出力管理部２０１からデータを受け取り、ｎ＋ａ
およびｎ＋ｂの互いに素な各因数ｐｉおよびｑｊを法とする第１剰余群を演算する機能と
、演算結果である第１剰余群を剰余乗算入出力管理部２０１へ出力する機能とをもってい
る。
【００７１】
第２剰余演算部２０３は、剰余乗算入出力管理部２０１から第１剰余演算部２０２が出
力した第１剰余群を含むデータを受け取り、中国人剰余定理を用いて第２剰余群を演算す
る機能と、演算結果である第２剰余群を剰余乗算入出力管理部２０１へ出力する機能とを
もっている。
【００７２】
除算部２０４は、剰余乗算入出力管理部２０１から第２剰余演算部２０３が出力した第
２剰余群を含むデータを受け取り、法ｎで割った商と剰余を演算する機能と、この演算結
果である商および剰余を剰余乗算入出力管理部２０１へ出力する機能とをもっている。
【００７３】
条件判定演算部２０５は、剰余乗算入出力管理部２０１から除算部２０４が出力した剰余を含むデータを受け取り、所定の条件判定式により最終的なｘ・ｕ ｍｏｄ ｎを求める機能と、演算結果であるｘ・ｕ ｍｏｄ ｎを剰余乗算入出力管理部２０１へ出力する機能とをもっている。
【００７４】
本発明の最終結果であるｘ・ｕ ｍｏｄ ｎを出力する剰余演算装置２０における剰余乗
算の演算処理手順について図４を用いて説明する。ここで、ｃ＝ａ・ｂ ｍｏｄ ｎであり
、剰余乗算時の処理高速性を高めるため、ｎ＋ａやｎ＋ｂが定まった段階で事前に演算し
、パラメータとして扱う。
【００７５】
始めに、剰余乗算入出力管理部２０１は、外部装置（不図示）から演算対象ｘ（０≦ｘ
＜ｎ）およびｕ（０≦ｕ＜ｎ）と、各パラメータｎ、ｎ＋ａ、ｎ＋ｂ、ａ、ｂ、ｃ、ｐｉ
（ｉ＝１、…、ｈ）およびｑｊ（ｊ＝１、…、ｍ）を入力として受信する（ＳＴ２１）。
【００７６】
ここで、例えばａおよびｂを入力すれば、各パラメータｎ＋ａ、ｎ＋ｂ、ｃ、ｐｉ（ｉ
＝１、…、ｈ）およびｑｊ（ｊ＝１、…、ｍ）が演算可能なので、この演算自体は剰余乗
算入出力管理部２０１または図示していないパラメータ演算部が行っても構わない。よっ
て、剰余乗算入出力管理部２０１には、必ずしも上述した全ての入力データが必要となる
わけではない。特に、演算対象ｘおよびｕ以外のデータは予め当該剰余乗算装置２０が保
持してもよい。これは、以下の各実施形態も同様である。また、これら以外のデータを入
力してもよい。
【００７７】
剰余乗算入出力管理部２０１は、前記入力データを受信すると、第１剰余演算部２０２
へｘおよびｕ、ｐｉ（ｉ＝１、…、ｈ）を送信して、第１剰余群ｓｐｉ（ｉ＝１、…、ｈ
）の演算を依頼する。第１剰余演算部２０２は、剰余乗算入出力管理部２０１からｘおよ
びｕ、ｐｉ（ｉ＝１、…、ｈ）を受信すると、次式のようにｘｐｉ（i＝１、…、ｈ）お
よびｕｐｉ（i＝１、…、ｈ）を演算する（ＳＴ２２およびＳＴ２３）。
【００７８】
ｘｐｉ＝ｘ ｍｏｄ ｐｉ（i＝１、…、ｈ）
ｕｐｉ＝ｕ ｍｏｄ ｐｉ（i＝１、…、ｈ）
次に、第１剰余演算部２０２は、ｘｐｉ（i＝１、…、ｈ）およびｕｐｉ（i＝１、…、ｈ
）を用いて、次式のようにｙｕｐｉを演算する（ＳＴ２４）。
【００７９】
ｙｕｐｉ＝ｘｐｉｕｐｉｍｏｄ ｐｉ（i＝１、…、ｈ）
さらに、第１剰余演算部２０２は、ｙｕｐｉ（i＝１、…、ｈ）を用いて、次式のように
、第１剰余群ｓｕｐｉ（ｉ＝１、…、ｈ）を演算し、演算結果である第１剰余群ｓｕｐｉ
（ｉ＝１、…、ｈ）を剰余乗算入出力管理部２０１へ出力する（ＳＴ２５）。
【００８０】
ｓｕｐｉ＝ｙｕｐｉ／（ｂ−ａ）ｍｏｄ ｐｉ（i＝１、…、ｈ）
ここで、（ｂ−ａ）−１ｍｏｄ ｐｉ（i＝１、…、ｈ）は事前に演算しておき、当該剰余
乗算装置２０にパラメータとして入力する形態でもよい。これは、以下の各実施形態も同
様である。
【００８１】
剰余乗算入出力管理部２０１は、第１剰余演算部２０２から受け取った第１剰余群ｓｕ
ｐｉ（ｉ＝１、…、ｈ）およびｎ＋ａを第２剰余演算部２０３へ送信して、第２剰余ｓｕ
ａの演算を依頼する。第２剰余演算部２０３は、剰余乗算入出力管理部２０１からｓｕｐ
ｉ（ｉ＝１、…、ｈ）およびｎ＋ａを受信すると、中国人剰余定理を用いて次式で示され
る第２剰余ｓｕａを演算し、剰余乗算入出力管理部２０１へ出力する（ＳＴ２６）。
【００８２】
ｓｕａ＝ｘ・ｕ／（ｂ−ａ）ｍｏｄ （ｎ＋ａ）
ここで、（ｂ−ａ）−１ｍｏｄ （ｎ＋ａ）は事前に演算しておき、当該剰余乗算装置２
０にパラメータとして入力する形態でもよい。これは、以下の各実施形態も同様である。
【００８３】
剰余乗算入出力管理部２０１は、ＳＴ２２からＳＴ２６と同様の処理を行い、ｎ＋ｂに
対する第２剰余ｓｕｂを演算する。すなわち、次のＳＴ２７〜ＳＴ３１を実行する。この
実施形態では、ＳＴ２２〜ＳＴ２５の後に続いてＳＴ２６〜ＳＴ２９の処理が行われてお
り、ＳＴ２２〜ＳＴ２５とＳＴ２６〜ＳＴ２９の処理は直列的に行われている。
【００８４】
剰余乗算入出力管理部２０１は、第１剰余演算部２０２へｘおよびｕ、ｑｊ（ｊ＝１、
…、ｍ）を送信して、第１剰余群ｓｕｑｊ（ｊ＝１、…、ｍ）の演算を依頼する。第１剰
余演算部２０２は、剰余乗算入出力管理部２０１からｘおよびｕ、ｑｊ（ｊ＝１、…、ｍ
）を受信すると、まず次式のようにｘｑｊ（ｊ＝１、…、ｍ）およびｕｑｊ（ｊ＝１、…
、ｍ）を演算する（ＳＴ２７およびＳＴ２８）。
【００８５】
ｘｑｊ＝ｘ・ｕ ｍｏｄ ｑｊ（ｊ＝１、…、ｍ）
ｕｑｊ＝ｘ・ｕ ｍｏｄ ｑｊ（ｊ＝１、…、ｍ）
次に、第１剰余演算部２０２は、ｘｑｊ（ｊ＝１、…、ｍ）およびｕｑｊ（ｊ＝１、…、
ｍ）を用いて、次式のようにｙｑｊを演算する（ＳＴ２９）。
【００８６】
ｙｕｑｊ＝ｘｑｊｕｑｊｍｏｄ ｑｊ（ｊ＝１、…、ｍ）
さらに、第１剰余演算部２０２は、ｙｕｑｊ（ｊ＝１、…、ｍ）を用いて、次式のように
、第１剰余群ｓｕｑｊ（ｊ＝１、…、ｍ）を演算し、この演算結果である第１剰余群ｓｕ
ｑｊ（ｊ＝１、…、ｍ）を剰余乗算入出力管理部２０１へ出力する（ＳＴ３０）。
【００８７】
ｓｕｑｊ＝ｙｕｑｊ／（ｂ−ａ）ｍｏｄ ｑｊ（ｊ＝１、…、ｍ）
ここで、（ｂ−ａ）−１ｍｏｄ ｑｊ（ｊ＝１、…、ｍ）は事前に演算おき、当該剰余乗
算装置２０にパラメータとして入力する形態でもよい。これは、以下の各実施形態も同様
である。
【００８８】
剰余乗算入出力管理部２０１は、第１剰余演算部２０２から受け取った第１剰余群ｓｕ
ｑｊ（ｊ＝１、…、ｍ）およびｎ＋ｂを第２剰余演算部２０３へ送信して、第２剰余ｓｕ
ｂの演算を依頼する。第２剰余演算部２０３は、剰余乗算入出力管理部２０１からｓｑｊ
（ｊ＝１、…、ｍ）およびｎ＋ｂを受信すると、中国人剰余定理を用いて次式で示される
第２剰余ｓｕｂを演算し、剰余乗算入出力管理部２０１へ出力する（ＳＴ３１）。
【００８９】
ｓｕｂ＝ｘ・ｕ／（ｂ−ａ）ｍｏｄ （ｎ＋ｂ）
ここで、（ｂ−ａ）−１ｍｏｄ（ｎ＋ｂ）は事前に演算しておき、当該剰余乗算装置２０
にパラメータとして入力する形態でもよい。これは、以下の各実施形態も同様である。
【００９０】
次に、剰余乗算入出力管理部２０１は、ｎ、ａ、ｂ、ｓｕａおよびｓｕｂ を除算部２０４に送信する。除算部２０４は、剰余乗算入出力管理部２０１から受信したｎ、ａ、ｂ、ｓｕａ およびｓｕｂ を用いて、ｂ・ｓｕａ−ａ・ｓｕｂをｎで割った商ｚおよび剰余ｒを求め、剰余乗算入出力管理部２０１に出力する（ＳＴ３２）。
【００９１】
剰余乗算入出力管理部２０１は、ｎ、ａ、ｂ、ｃ、ｓｕａ、ｓｕｂ、ｚおよびｒを条件判定演算部２０５に送信し、最終演算値ｓ＝ｘ・ｕ（ｍｏｄ ｎ）の出力を要求する。条件判定演算部２０５は、剰余乗算入出力管理部２１０から受信したｓｕａ、ｓｕｂ、ｚ、ｒ、ｃおよびｎの以下に示す条件判定により、ｓｕａ−ｓｕｂ＋ｚ≧０ならばｓ＝ｒを剰余乗算入出力管理部２０１に出力し（ＳＴ３３−１）、ｓｕａ−ｓｕｂ＋ｚ＜０且つｒ＋ｃ＜ｎならばｓ＝ｒ＋ｃを演算して剰余乗算入出力管理部２０１に出力し（ＳＴ３３−２）、ｓｕａ−ｓｕｂ＋ｚ＜０且つｒ＋ｃ＞ｎならばｓ＝ｒ＋ｃ−ｎを演算して剰余乗算入出力管理部２０１に出力する（ＳＴ３３−３）。
【００９２】
なお、本実施形態は、例えば、ｘｐｉの演算（ＳＴ２２）の前に、ｕｐｉの演算（ＳＴ
２３）を行い、またはｓｕａを求める手順（ＳＴ２２からＳＴ２６）の前に、ｓｕｂを求
める手順（ＳＴ２７からＳＴ３１）を行う等、演算において支障をきたさない部分は、逐
次演算順序を変更してもよい。これは以下の実施形態でも同様である。
【００９３】
（第３の実施形態）
図５は本発明の第３の実施形態に係る剰余演算装置３０の構成を示す模式図であり、図
６は本発明の第３の実施形態における平方剰余の演算処理を説明するための処理フローで
ある。
【００９４】
すなわち、本実施形態は、第１の実施形態（直列的演算）の変形例であり、平方剰余の
演算ｘ２ｍｏｄ ｎの並列的な演算処理を図るものであって、具体的には、前述同様の平
方剰余入出力管理部３０１、除算部３０４、条件判定演算部３０５と、前記平方剰余入出
力管理部３０１に制御されるＷ個の第１剰余演算部３０２１から３０２Ｗおよび２個の第
２剰余演算部３０３１および３０３２とを備えている。
【００９５】
ここで、平方剰余入出力管理部３０１は、平方剰余入出力管理部１０１とほぼ同様の管
理機能を有するものであるが、特に、図２に代えて図６の処理フローに基づいて、各部３
０２１〜３０２Ｗ、３０３１、３０３２、３０４および３０５を制御する機能を有してい
る。
【００９６】
第１剰余演算部１３０２１ないし第１剰余演算部Ｗ３０２Ｗ、第２剰余演算部１３０３
１および第２剰余演算部２３０３２は、本発明の第１の実施形態における剰余演算装置１
０と同様に、平方剰余入出力管理部３０１から入力された入力データを受信して演算を行
う機能と、この演算結果を平方剰余入出力管理部３０１へ出力する機能とをもっている。
【００９７】
ここで、本発明の第３の実施形態の各第１剰余演算部および各第２剰余演算部と、第１
の実施形態における各第１剰余演算部および各第２剰余演算部との処理（作用）の対応関
係について図２および図６を参照して具体的に述べる。第１剰余演算部の個数Ｗが「Ｗ≧
ｈ＋ｍ」の関係がある場合を想定して説明する。
【００９８】
第１剰余演算部１３０２１の処理（ＳＴ４２ｐ１、ＳＴ４３ｐ１、ＳＴ４４ｐ１）に関
しては、「ＳＴ４２ｐ１はＳＴ２」、「ＳＴ４３ｐ１はＳＴ３」、「ＳＴ４４ｐ１はＳＴ
４」それぞれの処理に対応する。同様にして、第１剰余演算部ｈ３０２ｈの処理（ＳＴ４
２ｐｈ、ＳＴ４３ｐｈ、ＳＴ４４ｐｈ）に関しては、「ＳＴ４２ｐｈはＳＴ２」、「ＳＴ
４３ｐｈはＳＴ３」、「ＳＴ４４ｐｈはＳＴ４」それぞれの処理に対応する。
【００９９】
次に、同様にして、第１剰余演算部（ｈ＋１）３０２（ｈ＋１）の処理（ＳＴ４６ｑ１
、ＳＴ４７ｑ１、ＳＴ４８ｑ１）に関しては、「ＳＴ４６ｑ１はＳＴ６」、「ＳＴ４７ｑ
１はＳＴ７」、「ＳＴ４８ｑ１はＳＴ８」それぞれの処理に対応する。同様にして、第１
剰余演算部（ｈ＋ｍ）３０２（ｈ＋ｍ）の処理（ＳＴ４６ｑｍ、ＳＴ４７ｑｍ、ＳＴ４８
ｑｍ）に関しては、「ＳＴ４６ｑｍはＳＴ６」、「ＳＴ４７ｑｍはＳＴ７」、「ＳＴ４８
ｑｍはＳＴ８」それぞれの処理に対応する。
【０１００】
次に、第２剰余演算部１３０３１の処理（ＳＴ４５）に関しては、「ＳＴ４５はＳＴ５
」に対応し、第２剰余演算部２３０３２の処理（ＳＴ４９）に関しては、「ＳＴ４９はＳ
Ｔ９」にそれぞれ対応する。また、除算部３０４の処理（ＳＴ５０）に関しては「ＳＴ５
０はＳＴ１０」に対応し、さらに、条件判定演算部３０５の処理（ＳＴ５１、ＳＴ５１−
１、ＳＴ５１−２、ＳＴ５１−３）は、「ＳＴ５１はＳＴ１１」に対応し、「ＳＴ５１−
１はＳＴ１１−１」に対応し、「ＳＴ５１−２はＳＴ１１−２」に対応し、「ＳＴ５１−
３はＳＴ１１−３」にそれぞれ対応する。
【０１０１】
ただし、第１剰余演算部の個数Ｗが「Ｗ＜ｈ＋ｍ」である場合には、例えば、「ＳＴ４２ ｐ１ 、・・・、ＳＴ４２ｐＷ 、ＳＴ４３ｐ１、・・・、ＳＴ４３ｐＷ 、ＳＴ４４ ｐ１、・・・、ＳＴ４４ｐＷ 」それぞれの処理を単位として、Ｗ個の第１剰余演算部が並列的にそれぞれ当該単位の処理を行い、その後に、またＷ個の第１剰余演算部が当該単位の処理を繰り返し、最終的に（ｈ＋ｍ）個目の第１剰余演算部が「ＳＴ４６ｑ（ｈ＋ｍ＋１−Ｗ） 、・・・、ＳＴ４６ｑ（ｈ＋ｍ） 、ＳＴ４７ｑ（ｈ＋ｍ＋１−Ｗ）、・・・、ＳＴ４７ｑ（ｈ＋ｍ） 、ＳＴ４８ ｑ（ｈ＋ｍ＋１−Ｗ）、・・・、ＳＴ４８ ｑ（ｈ＋ｍ＋１−Ｗ）」を行う。なお、（ｈ＋ｍ）はＷで割り切れる必要は特にない。
【０１０２】
従って、以上のような構成により、第１の実施形態の効果に加え、例えば、第１剰余演
算部の個数Ｗがｈ＋ｍ以上の場合（Ｗ≧ｈ＋ｍ）には、図６に示すように、ＳＴ４２ｐ１
〜ｐｈからＳＴ４５の演算と、ＳＴ４６ｑ１〜ｑｍからＳＴ４９の演算とを並列に実行し
、第１の実施形態における直列処理に比べて演算の高速化を実現することができる。
【０１０３】
また、第１剰余演算部の個数Ｗが少ない場合（Ｗ＜ｈ＋ｍ）でも、並列演算できる部分
を第１剰余演算部ｌから第１剰余演算部Ｗで並列に実行することにより、やはり演算の高
速化を実現することができる。また他の演算でも、並列演算によって演算効率を向上可能
な部分は、適宜、複数化された演算部で並列実行してよい。
【０１０４】
さらに、本実施形態の並列平方剰余演算装置３０は、１台の装置である必要はなく、例
えばネットワークを介して複数の計算機が利用可能な環境のように、演算を並列に実行可
能な環境（装置構成）にも適用することができる。
【０１０５】
（第４の実施形態）
図７は本発明の第４の実施形態に係る剰余乗算装置４０の構成を示す模式図であり、図
８は本発明の第４の実施形態における並列剰余乗算の演算処理を説明するための処理フロ
ーである。
【０１０６】
すなわち、本実施形態は、第２および第３の実施形態の組み合わせ例であり、平方剰余
の演算に変えて、剰余乗算ｘ・ｕ ｍｏｄ ｎを並列に演算処理するものであって、具体的
には、図６に代えて図８の処理フローに基づき、前述同様の剰余乗算入出力管理部４０１
、除算部４０４、条件判定演算部４０５と、前記剰余乗算入出力管理部４０１に制御され
るＷ個の第１剰余演算部４０２１から４０２Ｗおよび２個の第２剰余演算部４０３１およ
び４０３２とを備えている。
【０１０７】
ここで、剰余乗算入出力管理部４０１は、剰余乗算入出力管理部２０１とほぼ同様の管
理機能を有するものであるが、特に、図４に代えて図８の処理フローに基づいて、各部４
０２１〜４０２Ｗ、４０３１、４０３２、４０４および４０５を制御する機能を有してい
る。
【０１０８】
第１剰余演算部１４０２１ないし第１剰余演算部Ｗ４０２Ｗ、第２剰余演算部１４０３
１および第２剰余演算部２４０３２は、本発明の第２の実施形態における剰余演算装置２
０と同様に、剰余乗算入出力管理部４０１から入力された入力データを受信して演算を行
う機能と、この演算結果を剰余乗算入出力管理部４０１へ出力する機能とをもっている。
【０１０９】
ここで、本発明の第４の実施形態の各第１剰余演算部および各第２剰余演算部と、第２
の実施形態における各第１剰余演算部および各第２剰余演算部との処理（作用）の対応関
係について図４および図８を参照して具体的に述べる。第１剰余演算部の個数Ｗが「Ｗ≧
ｈ＋ｍ」の関係がある場合を想定して説明する。
【０１１０】
第１剰余演算部１４０２１の処理（ＳＴ６２ｐ１、ＳＴ６３ｐ１、ＳＴ６４ｐ１、ＳＴ
６５ｐ１）に関しては、「ＳＴ６２ｐ１はＳＴ２２」、「ＳＴ６３ｐ１はＳＴ２３」、「
ＳＴ６４ｐ１はＳＴ２４」、「ＳＴ６５ｐ１はＳＴ２５」それぞれの処理に対応する。同
様にして、第１剰余演算部ｈ３０２ｈの処理（ＳＴ６２ｐｈ、ＳＴ６３ｐｈ、ＳＴ６４ｐ
ｈ、ＳＴ６５ｐｈ）に関しては、「ＳＴ６２ｐｈはＳＴ２２」、「ＳＴ６３ｐｈはＳＴ２
３」、「ＳＴ６３ｐｈはＳＴ２４」、「ＳＴ６４ｐｈはＳＴ２５」それぞれの処理に対応
する。
【０１１１】
次に、同様にして、第１剰余演算部（ｈ＋１）３０２（ｈ＋１）の処理（ＳＴ６７ｑ１
、ＳＴ６８ｑ１、ＳＴ６９ｑ１、ＳＴ７０ｑ１）に関しては、「ＳＴ６７ｑ１はＳＴ２７
」、「ＳＴ６８ｑ１はＳＴ２８」、「ＳＴ６９ｑ１はＳＴ２９」、「ＳＴ７０ｑ１はＳＴ
３０」それぞれの処理に対応する。同様にして、第１剰余演算部（ｈ＋ｍ）３０２（ｈ＋
ｍ）の処理（ＳＴ６７ｑｍ、ＳＴ６８ｑｍ、ＳＴ６９ｑｍ、ＳＴ７０ｑｍ）に関しては、
「ＳＴ６７ｑｍはＳＴ２７」、「ＳＴ６８ｑｍはＳＴ２８」、「ＳＴ６９ｑｍはＳＴ２９
」、「ＳＴ７０ｑｍはＳＴ３０」それぞれの処理に対応する。
【０１１２】
次に、第２剰余演算部１４０３１の処理（ＳＴ６６）に関しては、「ＳＴ６６はＳＴ２
６」に対応し、第２剰余演算部２３０３２の処理（ＳＴ７１）に関しては、「ＳＴ７１は
ＳＴ３１」にそれぞれ対応する。また、除算部４０４の処理（ＳＴ７２）に関しては「Ｓ
Ｔ７２はＳＴ３２」に対応し、さらに、条件判定演算部４０５の処理（ＳＴ７３、ＳＴ７
３−１、ＳＴ７３−２、ＳＴ７３−３）は、「ＳＴ７３はＳＴ３３」に対応し、「ＳＴ７
３−１はＳＴ３３−１」に対応し、「ＳＴ７３−２はＳＴ３３−２」に対応し、「ＳＴ７
３−３はＳＴ３３−３」にそれぞれ対応する。
【０１１３】
ただし、第１剰余演算部の個数Ｗが「Ｗ＜ｈ＋ｍ」である場合には、例えば、「ＳＴ６２ ｐ１ 、・・・、ＳＴ６２ｐＷ 、ＳＴ６３ｐ１、・・・、ＳＴ６３ｐＷ 、ＳＴ６４ｐ１、・・・、ＳＴ６４ｐＷ 」それぞれの処理を単位として、Ｗ個の第１剰余演算部が並列的にそれぞれ当該単位の処理を行い、その後に、またＷ個の第１剰余演算部が当該単位の処理を繰り返し、最終的に（ｈ＋ｍ）個目の第１剰余演算部が「ＳＴ６７ ｑ（ｈ＋ｍ＋１−Ｗ） 、・・・、ＳＴ６７ｑ（ｈ＋ｍ） 、ＳＴ６８ｑ（ｈ＋ｍ＋１−Ｗ） 、・・・、ＳＴ６８ｑ（ｈ＋ｍ） 、ＳＴ６９ ｑ（ｈ＋ｍ＋１−Ｗ）、・・・、ＳＴ６９ｑ（ｈ＋ｍ）、ＳＴ７０ ｑ（ｈ＋ｍ＋１−Ｗ） 、・・・、ＳＴ７０ｑ（ｈ＋ｍ＋１−Ｗ） 」を行う。なお、（ｈ＋ｍ）はＷで割り切れる必要は特にない。
【０１１４】
従って、以上のような構成により、第２および第３の実施形態の効果に加え、例えば、
第１剰余演算部の個数Ｗがｈ＋ｍ以上の場合（Ｗ≧ｈ＋ｍ）は、図８に示すように、ＳＴ
６２ｐ１〜ｐｈからＳＴ６６の演算と、ＳＴ６７ｑ１〜ｑｍからＳＴ７１の演算とを並列
に実行し、演算の高速化を実現することができる。
【０１１５】
また、第１剰余演算部の個数Ｗが少ない場合（Ｗ＜ｈ＋ｍ）でも、並列演算できる部分
を第１剰余演算部ｌから第１剰余演算部Ｗで並列に実行することにより、やはり演算の高
速化を実現することができる。また他の演算でも、並列演算によって演算効率を向上可能
な部分は、適宜、複数化された演算部で並列実行してよい。
【０１１６】
さらに、本実施形態の並列剰余乗算装置４０は、１台の装置である必要はなく、例えば
ネットワークを介して複数の計算機が利用可能な環境のように、演算を並列に実行可能な
環境（装置構成）にも適用することができる。
【０１１７】
（第５の実施形態）
第１から第４の実施形態において、中国人剰余定理を用いてｓｘａ、ｓｘｂ、ｓｕａまたはｓｕｂを演算する際、並列演算が可能なガウス法を用いて、以下に示すように事前演算を活用することで、処理時の演算量を削減する効果が得られる。第１の実施形態では、ＳＴ４とＳＴ５の演算を図９の式（ニ）のようにまとめることができる。ここで、Ｎｉ＝（ｎ＋ａ）／ｐｉ、Ｍｉ＝Ｎｉ−１ｍｏｄ ｐｉである。さらに、各実施形態（実施形態２、３、４）に対しても同様に対応する処理を適用することができることは言うまでもない。例えば、第２の実施形態では、上記「ＳＴ４、ＳＴ５」に対応する処理は「ＳＴ２５、ＳＴ２６」である。第３の実施形態では、上記「ＳＴ４、ＳＴ５」に対応する処理は「ＳＴ４４ｐ１ 、・・・ＳＴ４４ｐｈ 、ＳＴ４８ ｑ１ 、・・・ＳＴ４８ｑｍ、ＳＴ４５、ＳＴ４９」である。さらに、第４の実施形態では、上記「ＳＴ４、ＳＴ５」に対応する処理は「ＳＴ６５ ｐ１、・・・ＳＴ６５ｐｈ 、ＳＴ７０ ｑ１ 、・・・ＳＴ７０ｑｍ、ＳＴ６６、ＳＴ７１」である。
【０１１８】
ここで、Ｎｉ＝（ｎ＋ａ）／ｐｉ、Ｍｉ＝Ｎｉ−１ｍｏｄ ｐｉである。この演算で、ＮｉＭｉ／（ｂ−ａ）ｍｏｄ （ｎ＋ａ）を事前演算して、剰余演算装置１０へのパラメータとして入力すれば、当該演算の処理速度を向上させることができる。これは、法ｎ＋ｂに対するｓｘｂについても同様である（ＳＴ８、ＳＴ９）。上記ｓｘａまたはｓｘｂの演算は、第１演算部１０２が全てやってもよい。この場合、第２剰余演算部１０３は不要となる。また、第２剰余演算部１０３が全てを実行してもよい。さらに、第１剰余演算部１０２および第２剰余演算部１０３が処理を分割して連携して実行する形態でもよい。例えば、ｙｘｐｉＮｉＭｉ／（ｂ−ａ）ｍｏｄ （ｎ＋ａ）の剰余乗算を第１剰余演算部１０２が実行して都度出力し、各出力値の法ｎ＋ａでの剰余加算を第２剰余演算部１０３が実行する形態がある。演算において支障をきたさない部分は、適宜連携形態を変更してよい。
【０１１９】
第２の実施形態では、前記第１の実施形態での拡張と同様、ｓｕａについてはＳＴ２５お
よびＳＴ２６、ｓｕｂについてはＳＴ３０およびＳＴ３１で演算をまとめる拡張が可能で
ある。
【０１２０】
第３の実施形態では、上記第１の実施形態と同様、ｓｘａについてはＳＴ４３ ｐ１〜ｐｈ およびＳＴ４５、ｓｘｂ についてはＳＴ４８ｑ１〜ｑｍおよびＳＴ４９で演算をまとめる拡張が可能である。このとき、ｙｘｐｉＮｉＭｉ／（ｂ−ａ）ｍｏｄ （ｎ＋ａ）（１≦ｉ≦ｈ）の各剰余乗算を第１剰余演算部１から第１剰余演算部Ｗで並列処理する形態でもよい。これは、法ｎ＋ｂにおけるｙｘｑｊ（１≦ｊ≦ｍ）の演算も同様である。また、これらの演算において支障をきたさない部分は、適宜、第１剰余演算部１から、第１剰余演算部Ｗ、第２剰余演算部１および第２剰余演算部２の連携形態を変更してよい。
【０１２１】
第４の実施形態では、前記第３の実施形態での拡張と同様、ｓｕａについてはＳＴ６５
ｐ１〜ｐｈおよびＳＴ６６、ｓｕｂについてはＳＴ７０ｑ１〜ｑｍおよびＳＴ７１で演算
をまとめる拡張が可能である。
【０１２２】
（第６の実施形態）
第１から第５の実施形態において、ａまたはｂのサイズが大きいとき、例えば第１の実
施形態でｎ１／２を超える場合には、以下に示す、テーブルを用いて定数乗算を高速化す
る形態を適用してもよい。
【０１２３】
ｂ・ｓｘａ−ａ・ｓｘｂ およびｂ・ｓｕａ−ａ・ｓｕｂをｎで割った商と余りを求める演算を高速化する。ここでは、ｂ・ｓｘａ−ａ・ｓｘｂを考える。まずｂ・ｓｘａの演算は以下のとおりである。ｓｘａ は図９の式（ホ）で表現することができる。
【０１２４】
ここで、ｗはワードサイズの倍数を示し、ｎのビット長ｖは、ｖ＝ｇ・ｗとする。
【０１２５】
事前演算として、ｂ・２ｗ・ｉ（ｉ＝０、…、ｇ−１）をｎで割った商ｄｉ、余りｒｉ
を求めておく。ここで、ｂ・２ｗ・ｉ（ｉ＝０、…、ｇ−１）は次式のように表現できる
。
【０１２６】
ｂ・２ｗ・ｉ＝ｄｉ・ｎ＋ｒｉ（ｉ＝０、…、ｇ−１）
このとき、ｂ・ｓｘａは図９の式（ヘ）のように表現できる。
【０１２７】
ここで、Ａ１およびＢ１は、図９の式（ト）および式９（チ）のように、ｗビットとｖビ
ットの整数の乗算と加算で演算できる。Ａ１およびＢ１のビットサイズは、高々ｖ＋ｗ＋
ｌｏｇ ｇビットとなる。
【０１２８】
ａ・ｓｘｂ も同様に、ａ・ｓｘｂ＝Ａ２ｎ＋Ｂ２と表現することができる。よって、ｂ・ｓｘａ−ａ・ｓｘｂ は次のように表現できる。
【０１２９】
ｂ・ｓｘａ−ａ・ｓｘｂ＝（Ａ１−Ａ２）ｎ＋（Ｂ１−Ｂ２）
ここで、高々ｖ＋ｗ＋ｌｏｇ ２ｇビットの数Ｂ１−Ｂ２をｎで割る補正を行い、その結果を以下のようにおく。
【０１３０】
Ｂ１−Ｂ２ ＝Ｃｎ＋Ｄ（０≦Ｄ＜ｎ）
このとき、ｂ・ｓｘａ−ａ・ｓｘｂは次のように表現できる。
【０１３１】
ｂ・ｓｘａ−ａ・ｓｘｂ＝（Ａ１−Ａ２−Ｃ）ｎ＋Ｄ
よって、ｂ・ｓｘａ−ａ・ｓｘｂをｎで割った商および余りがそれぞれ（Ａ１−Ａ２−Ｃ）およびＤとして求まる。ｂ・ｓｕａ−ａ・ｓｕｂの場合も同様である。
【０１３２】
従来技術ではａおよびｂのサイズ制約が厳しかったため、ｎ固定の下、ａおよびｂを動
かして、ｎ＋ａおよびｎ＋ｂが多くの素数の積に分解するようなａおよびｂを探すという
パラメータ生成手法を取らざるを得なかった。しかし、以上により、本発明の各種の実施
形態によれば、ａおよびｂに関するサイズ制約が緩和されたため、従来生成手法とは逆に
、まず互いに素で演算に都合のよい整数の積であるＮａおよびＮｂを構成し、その後でｎ
を決定し、ａおよびｂを一意に定める手法が可能となる。具体的に、例えば以下の手順で
ある。ここで、ＮａおよびＮｂは、最終的にｎ＋ａおよびｎ＋ｂとなる。
【０１３３】
まず、ｌビットの素数ｐｉをｖ／ｌ個作って、次式で示されるｖビットのＮａを求める
。
【０１３４】
Ｎａ＝ｐ１＊ｐ２＊…＊ｐｈ
同様に、ｌビットの素数ｑｊをｖ／ｌ個作って、次式で示されるｖビットのＮｂを求める
。
【０１３５】
Ｎｂ＝ｑ１＊ｑ２ ＊…＊ｑｍ
ここで、一般性を失うことがないよう、Ｎａ＜Ｎｂとする。次に、ｋ／２ビットの素数ｐを生成する。図９の式（リ）で示される整数以下の最大素数ｑを生成し、ｎ＝ｐ・ｑを演算する。最後に、ａ＝Ｎａ−ｎ、ｂ＝Ｎｂ−ｎを演算して、ａおよびｂを求める。
【０１３６】
上記手順で、ｐｉおよびｑｊは自由に選択できるため、高速剰余素数などを選択し、よ
り演算を高速化することが可能である。
【０１３７】
さらに、法ｎにおける剰余演算を高速化させるために、ｎ＋ａ、ｎ＋ｂ、ｐｉ（１≦ｉ
≦ｈ）、ｑｊ（１≦ｊ≦ｍ）に関する事前演算を駆使する必要がある。そうした事前演算
値をテーブルとして、ファイル、ＤＢ等、様々な記憶媒体で記録し、剰余演算の処理時に
当該テーブルを呼び出し、演算高速化を促進させる事前演算テーブルがある。
【０１３８】
ＥｌＧａｍａｌ暗号やＤＳＡといった離散対数問題に基づく公開鍵暗号方式では、ｎを
全ユーザ共通のシステムパラメータである素数Ｐとして、ｎ＋ａ、ｎ＋ｂ、ｐｉ（１≦ｉ
≦ｈ）、ｑｊ（１≦ｊ≦ｍ）に関する事前演算テーブルを全ユーザ共通のシステムパラメ
ータとして利用できる。
【０１３９】
一方で、ＲＳＡ暗号のように法ｎが各ユーザ個別の公開鍵として、ユーザごとに異なる
場合、単純には、ｎ＋ａ、ｎ＋ｂ、ｐｉ（１≦ｉ≦ｈ）、ｑｊ（１≦ｊ≦ｍ）に関する事
前演算テーブルは、演算高速化を図りたいユーザの数分だけ必要となる。この場合でも、
以下の手法により、各ユーザでそれぞれ異なる暗号鍵について、前記ｎ＋ａ、ｎ＋ｂ、ｐ
ｉ（１≦ｉ≦ｈ）、ｑｊ（１≦ｊ≦ｍ）に関する事前演算テーブルを全ユーザ共通の一組
に統一することが可能である。
【０１４０】
今、各ユーザＵｔ（１≦ｔ≦ω）の異なる二つの素因数の合成数で成るＲＳＡ公開暗号
鍵の法をｎｉとする。各ユーザＵθ（１≦θ≦ω）は、次式を満たすａｉおよびｂｉを演
算する。
【０１４１】
ＦＮａ＝ｎ１＋ａ１＝ｎ２＋ａ２＝…＝ｎω＋ａω
ＦＮｂ＝ｎ１＋ｂ１＝ｎ２＋ｂ２＝…＝ｎω＋ｂω
ここで、あるサービスで、全ユーザのｎｔ＋ａｔおよびｎｔ＋ａｔを定数ＦＮａおよびＦ
Ｎｂに共通化することにより、ｎ＋ａ、ｎ＋ｂ、ｐｉ（１≦ｉ≦ｈ）、ｑｊ（１≦ｊ≦ｍ
）に関する事前演算テーブルを全ユーザ共通に一本化できる。これにより、ユーザごとに
異なる暗号鍵を用いた剰余演算が必要な場合でも、事前演算テーブルの管理サイズを最小
化しつつ、本発明による演算高速化の効果が得られる。
【０１４２】
以上から、本発明の各実施形態をまとめると、法ｎのビットサイズが１０２４ビットの場
合、パラメータ選択範囲は2５１２倍に向上する。このパラメータ設定の自由度向上によ
り、主目的である剰余演算の並列演算を最大限に高速化するｎ＋ａおよびｎ＋ｂを実用レ
ベルで、設定者の意図どおり、自在に設定することが可能となる。また、事前演算テーブ
ル共通化の応用により、本来ユーザごとに異なる事前演算テーブルを全ユーザで共通化す
ることで、本発明の並列演算高速化手法を当該演算装置にて、必要最小限のメモリ資源で
実行可能となる。
【０１４３】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラ
ムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光
ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの
記憶媒体に格納して頒布することもできる。
【０１４４】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能
な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１４５】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピ
ュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト
、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処
理の一部を実行しても良い。
【０１４６】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやイ
ンターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した
記憶媒体も含まれる。
【０１４７】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される
場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１４８】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実
施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の
装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１４９】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演
算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能
な機器、装置を総称している。
【０１５０】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその
要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示さ
れている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形
態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態
に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１５１】
【図１】本発明の第１の実施形態に係る剰余演算装置の構成を示す模式図である。
【図２】本発明の第１の実施形態における剰余演算の処理フローである。
【図３】本発明の第２の実施形態に係る剰余演算装置の構成を示す模式図である。
【図４】本発明の第２の実施形態における剰余演算の処理フローである。
【図５】本発明の第３の実施形態に係る剰余演算装置の構成を示す模式図である。
【図６】本発明の第３の実施形態における剰余演算の処理フローである。
【図７】本発明の第４の実施形態に係る剰余演算装置の構成を示す模式図である。
【図８】本発明の第４の実施形態における剰余乗算の処理フローである。
【図９】本発明における式の一覧である。
【図１０】本発明における記号表記と意味の一覧である。
【符号の説明】
【０１５２】
１０、２０、３０、４０・・・剰余演算装置
１０１  平方剰余入出力管理部
１０２  第１剰余演算部
１０３  第２剰余演算部
１０４  除算部
１０５  条件判定演算部
２０１  剰余乗算入出力管理部
２０２  第１剰余演算部
２０３  第２剰余演算部
２０４  除算部
２０５  条件判定演算部
３０１  平方剰余入出力管理部
３０２１〜３０２Ｗ  第１剰余演算部１〜Ｗ
３０３１  第２剰余演算部１
３０３２  第２剰余演算部２
３０４  除算部
３０５  条件判定演算部
４０１  剰余乗算入出力管理部
４０２１〜４０２Ｗ  第１剰余演算部１〜Ｗ
４０３１  第２剰余演算部１
４０３２  第２剰余演算部２
４０４  除算部
４０５  条件判定演算部
【図１】
0004679590.tif 000002
【図２】
0004679590.tif 000003
【図３】
0004679590.tif 000004
【図４】
0004679590.tif 000005
【図５】
0004679590.tif 000006
【図６】
0004679590.tif 000007
【図７】
0004679590.tif 000008
【図８】
0004679590.tif 000009
【図９】
0004679590.tif 000010
【図１０】
0004679590.tif 000011