(57)【要約】  整数の積を計算するように設けられた電子計算装置１００、２００であって、多層剰余数系（ＲＮＳ）表現で整数２１０、２２０を保存する保存装置１１０であって、前記多層ＲＮＳ表現は、少なくとも上側の層のＲＮＳ及び下側の層のＲＮＳを有し、前記上側の層のＲＮＳは、複数の上側の法の系列（Ｍｉ）についての剰余数系であり、前記下側の層のＲＮＳは、複数の下側の法の系列（ｍｉ）についての剰余数系であり、整数（ｘ）が、前記上側の法の系列（Ｍｉ）を法とする複数の上側の剰余の系列（ｘｉ＝（ｘ）Ｍｉ）２１１、２２１によって前記保存装置内に表現されており、少なくとも１つの特定の上側の法（Ｍｊ）についての上側の剰余（ｘｊ）２１０．２、２２０．２は、前記下側の法の系列（ｍｉ）を法とする前記上側の剰余（ｘｊ）の複数の下側の剰余の系列（（ｘｊ）ｍｊｉ）２１２、２２２によって前記保存装置内に更に表現されており、前記複数の下側の法（ｍｉ）のうちの少なくとも１つは、前記複数の上側の法（Ｍｊ）を分割しない、保存装置１１０を含む。
2020515928.tif 000002
【特許請求の範囲】
【請求項１】
整数の積を計算するように設けられた電子計算装置であって、前記電子計算装置は、
多層剰余数系（ＲＮＳ）表現で整数を保存する保存装置であって、前記多層ＲＮＳ表現は、少なくとも上側の層のＲＮＳ及び下側の層のＲＮＳを有し、前記上側の層のＲＮＳは、複数の上側の法の系列（Ｍｉ）についての剰余数系であり、前記下側の層のＲＮＳは、複数の下側の法の系列（ｍｉ）についての剰余数系であり、整数（ｘ）が、前記上側の法の系列（Ｍｉ）を法とする複数の上側の剰余の系列（
【数１４６】
2020515928.tif 000148
）によって前記保存装置内に表現されており、少なくとも１つの特定の上側の法（Ｍｊ）についての上側の剰余（ｘｊ）は、前記下側の法の系列（ｍｉ）を法とする前記上側の剰余（ｘｊ）の複数の下側の剰余の系列（
【数１４７】
2020515928.tif 000149
）によって前記保存装置内に更に表現されており、前記複数の下側の法（ｍｉ）のうちの少なくとも１つは、前記複数の上側の法（Ｍｊ）の法を分割しない、保存装置と、
第１の整数（ｘ）と第２の整数（ｙ）との積を計算するプロセッサ回路であって、前記第１の整数と前記第２の整数とは、前記多層ＲＮＳ表現に従って前記保存装置内に保存されており、前記プロセッサ回路は、少なくとも下側乗算ルーチンと上側乗算ルーチンとで構成されており、
前記下側乗算ルーチンは、前記上側の法（Ｍｊ）を法とする同一の上側の法（Ｍｊ）に対応する２つの更に表現された上側の剰余（ｘｊ、ｙｊ）の積を計算し、
前記上側乗算ルーチンは、前記第１の整数（ｘｉ）の上側の剰余と前記対応する法（Ｍｉ）を法とする前記第２の整数（ｙｉ）の対応する上側の剰余との成分ごとの乗算によって前記第１の整数と前記第２の整数との積を計算し、前記上側乗算ルーチンは、更に表現された前記上側の剰余を掛け合わせるよう前記下側乗算ルーチンに求め、前記上側乗算ルーチンは、前記対応する法の予め定義された拡張係数倍よりも小さい上側の剰余（ｘｉ、ｙｉ）を受け、前記対応する法の前記予め定義された拡張係数倍よりも小さい受けられた前記上側の剰余（ｚ）の積の上側の剰余（ｚｉ）を生成する、プロセッサ回路とを含む、電子計算装置。
【請求項２】
前記上側乗算ルーチンは、さらに、更なる法（Ｎ）を法とする前記第１の整数（ｘ）と前記第２の整数（ｙ）との積を計算する、請求項１に記載の電子計算装置。
【請求項３】
前記拡張係数は２以上である、請求項１又は２に記載の電子計算装置。
【請求項４】
前記下側乗算ルーチンは、前記対応する法（Ｍｊ）を法とするモジュラ簡約が次に続く、前記第１の上側の剰余の下側の剰余と前記第２の上側の剰余の対応する下側の剰余との成分ごとの乗算によって、上側の法（Ｍｊ）を法とする前記２つの更に表現された上側の剰余の演算積（ｈ）を計算する、請求項１乃至３のいずれか一項に記載の電子計算装置。
【請求項５】
前記モジュラ簡約は、前記演算積（ｈ）と前記対応する法（Ｍｊ）との切り捨て除算［ｈ／Ｍｊ］を計算することを含む、請求項４に記載の電子計算装置。
【請求項６】
前記電子計算装置は、テーブル保存装置を含み、前記下側乗算ルーチンは、前記テーブル保存装置に保存されたモジュラ乗算結果ルックアップテーブル内の前記下側の剰余の積をルックアップすることを含み、前記下側の法のための前記ルックアップテーブルが、少なくとも最大の下側の法程度に大きい、請求項１乃至５のいずれか一項に記載の電子計算装置。
【請求項７】
更に表現された上側の剰余（Ｘ）が、Ｍｏｎｔｇｏｍｅｒｙ表現（ｘ）で表現され、前記Ｍｏｎｔｇｏｍｅｒｙ表現（ｘ）は、前記対応する法を法とする予め定義されたＭｏｎｔｇｏｍｅｒｙ定数（ｍ）と掛け合わせられた前記上側の剰余（Ｘ）であり、前記下側乗算ルーチンは前記Ｍｏｎｔｇｏｍｅｒｙ表現で更に表現された２つの上側の剰余を下側の剰余の２つの系列として受け、Ｍｏｎｔｇｏｍｅｒｙ表現で積を生成する、請求項１乃至６のいずれか一項に記載の電子計算装置。
【請求項８】
前記下側乗算ルーチンは、あるｚについて、ｈ＋ｕＭｊ＝ｚｍを満たす整数ｕを計算し、ここでｈ＝ｘｙであり、前記下側乗算ルーチンは、ｚ＝（ｈ＋ｕＭｊ）／ｍを計算する、請求項７に記載の電子計算装置。
【請求項９】
前記下側の層のＲＮＳは、拡張された剰余数系であり、前記複数の下側の法の系列（ｍ１、・・・、ｍＫ）は、基底の系列であり、前記拡張されたＲＮＳは、更なる複数の下側の法の拡張系列（ｍＫ＋１、・・・、ｍＬ）を有し、Ｍｏｎｔｇｏｍｅｒｙ定数（ｍ）は、前記複数の下側の法の基底の系列の積であり、前記ｚ＝（ｈ＋ｕ）／ｍを計算することが、前記拡張系列について行われ、次に前記基底の系列に対する基底拡張が続く、請求項８に記載の電子計算装置。
【請求項１０】
先ず前記ｚ＝（ｈ＋ｕ）／ｍについての剰余が、前記更なる複数の下側の法（ｍＫ＋１、・・・、ｍＬ）について計算され、続いて下側の法の基底の系列（ｍ１、・・・、ｍＫ）についての前記ｚに対する剰余が基底拡張によって計算される、請求項９に記載の電子計算装置。
【請求項１１】
前記下側乗算ルーチンは、前記上側の剰余（ｘｉ）及び（ｄｉ）を表す下側の剰余の成分ごとの乗算及び加算によって先ず積の和（ｄｊ＝ｍｃｊで、
【数１４８】
2020515928.tif 000150
）を計算し、次に前記対応する法（Ｍｊ）を法とする最後のモジュラ簡約が続くことによって上側の法（Ｍｊ）を法とするモジュラ積和（
【数１４９】
2020515928.tif 000151
）を計算する、請求項１乃至１０のいずれか一項に記載の電子計算装置。
【請求項１２】
前記上側の法の系列は、基底拡張について冗長な法を含み、前記冗長な法は、前記複数の下側の法の系列のうちの１つ以上の下側の法の積である、請求項１乃至１１のいずれか一項に記載の電子計算装置。
【請求項１３】
定数Ｈｓ＿の系列が、少なくとも前記上側の層について法Ｍｍについて定義され、よって、剰余ｘｓが、ｘｓ＝Ｈｓｙｓ  ｍｏｄ  Ｍｓである疑似剰余ｙｓとして表現され、ここで少なくとも１つのＨｓはｍ−１  ｍｏｄ  Ｍｓとは異なる、請求項１乃至１２のいずれか一項に記載の電子計算装置。
【請求項１４】
整数の積を計算する電子計算方法であって、前記電子計算方法は、
多層の剰余数系（ＲＮＳ）表現で整数を保存することであって、前記多層ＲＮＳ表現は、少なくとも上側の層のＲＮＳと下側の層のＲＮＳを有し、前記上側の層のＲＮＳは複数の上側の法の系列（Ｍｉ）についての剰余数系であり、前記下側の層のＲＮＳは、複数の下側の法の系列（ｍｉ）についての剰余数系であり、整数（ｘ）が、前記上側の法（Ｍｉ）の系列を法とする複数の上側の剰余（
【数１５０】
2020515928.tif 000152
）の系列によって保存装置に表現されており、少なくとも１つの特定の上側の法（Ｍｊ）についての上側の剰余（ｘｊ）は、前記下側の法の系列（ｍｉ）を法とする前記上側の剰余（ｘｊ）の複数の下側の剰余の系列（
【数１５１】
2020515928.tif 000153
）によって前記保存装置に更に表現されており、前記複数の下側の法（ｍｉ）のうちの少なくとも１つは、前記複数の上側の法（Ｍｊ）の法を分割しない、保存することと、
第１の整数（ｘ）と第２の整数（ｙ）との積を計算することであって、前記第１の整数（ｘ）と第２の整数（ｙ）とは前記多層ＲＮＳ表現に従って前記保存装置に保存され、前記計算することは少なくとも下側乗算部分と上側乗算部分とを含み、
前記下側乗算部分は、前記上側の法（Ｍｊ）を法とする同一の上側の法（Ｍｊ）に対応する２つの更に表現された上側の剰余（ｘｊ、ｙｊ）の積を計算し、
前記上側乗算部分は、前記第１の整数（ｘｉ）の上側の剰余と前記対応する法（Ｍｉ）を法とする前記第２の整数（ｙｉ）の対応する上側の剰余との積の成分ごとの乗算によって前記第１の整数（ｘ）と第２の整数（ｙ）との積を計算し、前記上側乗算ルーチンは、更に表現されている前記上側の剰余を掛け合わせるように前記下側乗算ルーチンに求め、前記上側乗算部分は、前記対応する法の予め定義された拡張係数倍よりも小さい上側の剰余（ｘｉ、ｙｉ）を受け、前記対応する法の前記予め定義された拡張係数倍よりも小さい受けられた前記上側の剰余（ｚ）の積の上側の剰余（ｚｉ）を生成する、計算することとを含む、電子計算方法。
【請求項１５】
プロセッサシステムに請求項１４に記載の電子計算方法を実行させる命令を表す一時的な又は非一時的なデータを含む、コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子計算装置、計算方法及びコンピュータ可読保存装置に関する。
【背景技術】
【０００２】
計算において、整数は、剰余数系（Ｒｅｓｉｄｕｅ  Ｎｕｍｂｅｒ  Ｓｙｓｔｅｍ、ＲＮＳ）表現に符号化されることもある。剰余数系（ＲＮＳ）では、法ｍは、互いに素であるより小さい法ｍｉの積ｍ＝ｍ１・・・ｍｋであり、整数ｙ∈［０，ｍ）は、これらの剰余の一覧（ｙ１、・・・、ｙｋ）によって一意的に表され、ここで、全てのｉについてｙｉ＝｜ｙ｜ｍｉである。後者の表記は、ｙ≡ｙｉ  ｍｏｄ  ｍｉを満たす一意的な整数ｙｉ＝∈［０，ｍｉ）を表す。整数についての中国剰余定理（ＣＲＴ）の結果として、ＲＮＳ表現は、法の積よりも小さい非負整数について一意的であり、またＲＮＳのダイナミックレンジと呼ばれる。
【０００３】
ＲＮＳの優位性は、計算が、成分に関して、すなわち、剰余に関して、行われることができることである。ＲＮＳを用いることによって、大きな整数の計算が、独立に及び並列に行われることができる成分のそれぞれについて多くの小さな計算によって実行されることができる。ＲＮＳは、例えば、フィルタリングやフーリエ変換などについてのデジタル信号処理（ＤＳＰ）に、及び暗号化に、広く用いられている。
【０００４】
特にホワイトボックス暗号法において、ＲＮＳ表現は有利である。ホワイトボックスでは、計算は、計算の結果を表すテーブルを用いて、符号化されたデータに行われる。ＲＮＳ表現された整数の演算は、しばしばＲＮＳの桁に独立に行われることができる。例えば、ＲＮＳ表現において２つの整数を加える又は掛け合わせるためには、対応する法を法とする対応する成分を加える又は掛け合わせることで十分である。ＲＮＳの法を法とする演算は、テーブルルックアップによって行われることができる。ホワイトボックス暗号法において、テーブルルックアップは、符号化されることもできる。ＲＮＳを大幅に用いることは、キャリーの問題を除去する。ホワイトボックスにおいてでもキャリーを正しく考慮に入れることは可能であるけれども、ＲＮＳを用いることは、計算を相当に平易にすることができる。さらに、キャリーの存在又は非存在は、隠すことが難しく、それを通してホワイトボックスの実装が攻撃される可能性があるサイドチャンネルとなり得る。例えば、暗号のアルゴリズムのホワイトボックスの実装は、ブロック暗号などの秘密鍵に依存する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ＲＮＳのダイナミックレンジは法の積であるから、大きなダイナミックレンジは、法の数を増すことによって及び／又は法の大きさを増すことによってのみ実現されることができる。これは、特に演算がテーブルルックアップによって実行される場合に、好ましくないことがある。この場合、テーブルがとても大きくなるか又はとても多くのテーブルが要求される（又は両方）。それなので、ＲＮＳとても大きなダイナミックレンジは、とても大きなテーブルか又はとても多くの数のテーブルを必要とする。
【課題を解決するための手段】
【０００６】
整数の積を計算するように設けられた電子計算装置は、特許請求の範囲に規定されるように提供される。上記装置は、多層化された剰余数系表現で整数を保存する保存装置を含み、上記多層ＲＮＳ表現は、少なくとも上側の層のＲＮＳと下側の層のＲＮＳを有し、上記上側の層のＲＮＳは、複数の上側の法の系列についての剰余数系であり、上記下側の層のＲＮＳは、複数の下側の法の系列についての剰余数系であり、整数が上側の法の系列を法とする複数の上側の剰余の系列によって上記保存装置に表現されており、少なくとも１つの特定の上側の法についての上側の剰余は下側の法の系列を法とする上記上側の剰余の複数の下側の剰余の系列によって上記保存装置に更に表現されている。
【０００７】
計算装置は、ＲＮＳの法の固定された、小さい組を用いつつ、所望の大きさのダイナミックレンジを実現することを可能にするので、とても大きい整数を用いた、例えば加算、減算、乗算などの計算、又はとても大きい法を法とする計算が、ＲＮＳの法についてモジュラ演算のための小さなテーブルの小さな組を用いて行われることができる。
【０００８】
一実施形態では、上記上側乗算ルーチンは、更なる法（Ｎ）を法とする上記第１の整数（ｘ）と第２の整数（ｙ）との積を計算するように更に構成されている。例えば、一実施形態では、上記計算装置は、Ｍｏｎｔｇｏｍｅｒｙ積ｘｙＭ−１  ｍｏｄ  Ｎを計算する。
【０００９】
上記計算装置は、電子装置であり、移動式装置、例えば携帯電話機であってもよい。他の例は、セットトップボックス、スマートカード、コンピュータその他を含む。本明細書に記載された計算装置及び方法は、幅広い実際的な応用に適用されることもできる。そのような実際的な応用は、暗号法、例えば、特に大きな数を用いる演算を要求する暗号法、例えば、ＲＳＡ、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ法、楕円曲線暗号を含む。
【００１０】
本発明に従う方法は、コンピュータ上にコンピュータに実装された方法として、又は専用ハードウェアに、又は両方の組合せに実装されてもよい。本発明に従う方法のための実行可能なコードは、コンピュータプログラム製品に保存されてもよい。コンピュータプログラム製品の例は、メモリ装置、光学保存装置、集積回路、サーバ、オンラインソフトウェアなどを含む。好ましくは、上記コンピュータプログラム製品は、上記プログラム製品がコンピュータ上で実行されたときに本発明に従う方法を実行するための、コンピュータ可読媒体に保存された非一時的なプログラムコードを含む。
【００１１】
好ましい実施形態では、上記コンピュータプログラムは、コンピュータ上で走らせられたときに本発明に従う方法の全てのステップを実行するように適用されたコンピュータプログラムコードを含む。好ましくは、上記コンピュータプログラムは、コンピュータ可読媒体に組み込まれる。
【００１２】
本発明の他の態様は、ダウンロードすることが利用可能な上記コンピュータプログラムをつくる方法を提供する。この態様は、上記コンピュータプログラムが、例えば、ＡｐｐｌｅのＡｐｐ  Ｓｔｏｒｅ、ＧｏｏｇｌｅのＰｌａｙ  Ｓｔｏｒｅ、又はＭｉｃｒｏｓｏｆｔのＷｉｎｄｏｗｓ  Ｓｔｏｒｅへアップロードされるときに、及び上記コンピュータプログラムがそのようなストアからダウンロードすることが利用可能であるときに、用いられる。
本発明の更なる詳細、態様及び実施形態が、図面を参照して、ほんの例として、説明される。図における要素は、簡明性及び明瞭性のために表されており、必ずしも正確は比率ではない。図において、既に説明された要素に対応する要素は、同一の参照番号を有することがある。図面は次のようである。
【図面の簡単な説明】
【００１３】
【図１】電子計算装置の実施形態の一例を概略的に示す。
【図２ａ】電子計算装置の実施形態の一例を概略的に示す。
【図２ｂ】多層ＲＮＳで整数を表現することの実施形態の一例を概略的に示す。
【図３】多層ＲＮＳで整数を表現することの実施形態の一例を概略的に示す。
【図４】計算方法の実施形態の一例を概略的に示す。
【図５ａ】一実施形態に従う、コンピュータプログラムを含む、書き込み可能な部分を有する、コンピュータ可読媒体を概略的に示す。
【図５ｂ】一実施形態に従う、プロセッサシステムの表現を概略的に示す。
【発明を実施するための形態】
【００１４】
本発明は、多くの異なる形態における実施形態が可能であるが、本開示は、本発明の原理の典型として考えられるべきであり、示された及び説明された特定の実施形態に本発明を限定することを意図するものではないという理解をもって、１つ以上の特定の実施形態が、図面に示され及び本明細書に詳細に説明される。
【００１５】
以下において、理解のために、実施形態の要素は、動作中で説明される。しかし、それぞれの要素は、それらによって実行されるように説明されている機能を実行するように設けられることは明らかであろう。
【００１６】
さらに、本発明は、実施形態に限定されないし、本発明は、本明細書に又は互いに異なる従属する請求項に記載された新規な特徴又は特徴の組合せの全部又はそれぞれに広がっている。
【００１７】
本発明の実施形態は、固定された、小さい法を法とする演算を用いた、特に、固定された、少数のルックアップテーブルを用いた、任意に大きな法についてのモジュラ演算を可能にする。モジュラ乗算は、難しい操作であるが、さまざまな方法、例えば、Ｍｏｎｔｇｏｍｅｒｙ、Ｂａｒｒｅｔｔ、Ｑｉｕｓｑｕａｔｅｒなどが、次の意味において、すなわち、０≦ｒ＜Ｎでｒ＝ｘｙ  ｍｏｄ  Ｎが、Ｎを法とする乗算の正確な結果であるなら、これらの方法は、小さい非負整数ｑについてｚ＝ｒ＋ｑＮの形の結果ｚを与える、という意味において、この操作を近似するように考え出された。そのような結果を疑似剰余と呼ぶことにする。例えば、Ｊｅａｎ−Ｆｒａｎｃｏｉｓ  Ｄｅｈｍを参照されたい。ＲＩＳＣベースのスマートカード用の効率的なパブリックキー暗号化ライブラリの設計を参照されたい。多くのモジュラ演算アルゴリズムの考察についての、詳細にはモジュラ乗算、より詳細にはＭｏｎｔｇｏｍｅｒｙ乗算についての、博士論文、Ｕｎｉｖｅｒｓｉｔｅ  Ｃａｔｈｏｌｉｑｕｅ  ｄｅ  Ｌｏｕｖａｉｎ、１９９８を参照されたい。
【００１８】
疑似剰余が、０≦ｑ＜φの場合を満たし、よって、法Ｎの固定された倍数φＮによって制限されたままである場合の、拡張限界φを有する疑似剰余ｒ＋ｑＮを述べる。整数ｐは、ある所定の整数φについて、ｐ＝ｘ  ｍｏｄ  ｍ且つ０≦ｐ＜φｍの場合の整数ｘのｍを法とする疑似剰余である。整数φは、拡張限界と呼ばれ、疑似剰余の増大を制限する。φ＝１の場合、疑似剰余は、通常の剰余である。例えば、単に−φｍ＜ｐ＜φｍであることを要求することによって、疑似剰余についての制限を更に緩めることが可能である。表現の利便性のために、この緩められた仮定を設けないが、以下の考察はより制限的ではない限界を考慮に入れることに容易に適応させられることができると理解される。この種の疑似剰余は、対称疑似剰余と称される。
【００１９】
より更なる一般化では、上側及び下側の拡張限界は、例えば、下側の拡張係数φＬ及び上側の拡張係数φＵについてφＬｍ＜ｐ＜φＵｍであることを要求することによって、用いられることができる。下側及び上側の拡張係数は、φＬ＜φＵであるが、正又は負であってもよい。例えば、疑似剰余は、φ＝φＵ−φＬでφＬ≦ｑ＜φＵを満たすこともある。他方、例えば、法の追加の減算を行うことによって、追加の乗算又は簡約を行うことによって、又は、正確な除算を行うことによって、正確な剰余ｒを計算する、より複雑な方法が存在する。興味深いことに、モジュラ演算の方法は、典型的には結果を疑似剰余として与える。正確な剰余を得るには余分な労力が要求される。例えば、Ｄｅｈｍ（２．２．６章）におけるＭｏｎｔｇｏｍｅｒｙアルゴリズムは、この余分な簡約ステップを省く“Ｕｎ＞ＮならＵ＝Ｕｎ−ＮでありそうでなければＵ＝Ｕｎである”は、出力が拡張係数２を有する疑似剰余であるモジュラ簡約アルゴリズムを与えることになることを、最終の２つのステップとしてもつ。数百ほどに大きくても、より大きい拡張係数を有するモジュラ乗算アルゴリズムが、そのアルゴリズムで用いられてもよい。例えば、変換として長いことがシステム内で長い系列の操作の後に要求されるだけならば、これは、問題ではない。一般的に、剰余というとき、それは、疑似剰余又は正確な剰余であることがある。
【００２０】
計算装置の一実施形態では、上側乗算ルーチンは、対応する法の予め定義された拡張係数倍よりも小さい（ｘｉ、ｙｉ＜φＵＭｉ）上側の剰余（ｘｉ、ｙｉ）を受けるように構成され、且つ、対応する法の予め定義された拡張係数倍よりも小さい（ｚｉ＜φＵＭｉ）受けられた上側の剰余（ｚ）の積の上側の剰余（ｚｉ）を生成するように構成される。また、上側乗算ルーチンは、対応する法の更に予め定義された拡張係数倍より大きいか又は等しい（ｘｉ、ｙｉ≧φＬＭｉ）上側の剰余（ｘｉ、ｙｉ）を受けるように構成されることができ、且つ、対応する法の予め定義された拡張係数倍よりも大きいか又は等しい（ｚｉ≧φＬＭｉ）受けられた上側の剰余（ｚ）の積の上側の剰余（ｚｉ）を生成するように構成される。もし、φＬ＞０なら、φ＝φＵ−φＬを拡張係数と呼ぶことにする。
【００２１】
本発明の実施形態の基礎をなす重要な所見は、次のようなものである。ＲＮＳを用いたモジュラ演算を行う方法が与えられたなら、法ｍｉをもつ小さいＲＮＳを用いたその方法、言うなれば、大きな法Ｎについてのモジュラ演算を実行する、大きなＲＮＳの法Ｍｉのそれぞれについてモジュラ演算を実行することを、用いることができる。換言すれば、ＲＮＳを用いたモジュラ演算用の方法を用いて、互いの上に築かれたＲＮＳの２つ以上の層をもつ“階層的な”ＲＮＳを構築することができる。かかる階層的なＲＮＳ系を多層剰余数系（Ｍｕｌｔｉ−Ｌａｙｅｒ  Ｎｕｍｂｅｒ  Ｓｙｓｔｅｍｓ、ｍｕｌｔｉ−ｌａｙｅｒ  ＲＮＳ）と呼ぶことにする。このようにして、小さいダイナミックレンジをもつ、小さいＲＮＳを用いて、より大きなダイナミックレンジをもつ、より大きなＲＮＳを実行することができる。
【００２２】
最大のダイナミックレンジをもつＲＮＳを第１層又は最上層と呼び、最小のダイナミックレンジをもつＲＮＳを最下層又は底層と呼ぶことにする。一実施形態では、２つの層を有し、底層は、第２層となる。
【００２３】
一実施形態では、そのような階層的な系は、正確な剰余に代わる疑似剰余で動作するＲＮＳを用いてモジュラ演算を行う方法を実装することによって構築される。疑似剰余が有界であるならば、すなわち、疑似剰余が保証された拡張限界を持つならば、これは、効率的なシステムを構築することを可能にする。そのような階層的ＲＮＳ系において、底層におけるものを除く異なる層における全てのＲＮＳは、底のＲＮＳのみが実際に演算を行い、より高い層における全て（又はほとんど全て）の演算は底のＲＮＳに権限を委ねているという意味において、“仮想”である。
【００２４】
多層ＲＮＳの典型的な応用では、底のＲＮＳにおけるモジュラ演算は、ルックアップテーブルによって行われ、その場合、多層ＲＮＳ系は、更なる演算が底のレベルの演算を超えて必要とされないような仕方に、工夫されることができる。これは、かかる多層ＲＮＳ系がホワイトボックスの応用に用いられることを特に魅力的にする。また、これらの多層ＲＮＳ系のハードウェア実装は、相当に並列化可能であり、したがって速度の観点において大きな有望性を提供する。
【００２５】
例えば、ＲＳＡやＤｉｆｆｉｅ−Ｈｅｌｌｍａｎにおいて要求されるような、モジュラべき乗を、２０４８ビット程度の大きさの法を用いて行うように、方法を実行した。本方法の好ましい実施形態において、２層の多層ＲＮＳを用い、底のＲＮＳにおいて８ビットの法と第１層において６６ビットの法を用いた。結果として生じる系は、約１４００００のテーブルルックアップを行って２０４８ビットのモジュラ乗算を行った。結果として、２０４８ビットの法と５００ビットべき指数とを用いたモジュラべき乗が、通常のラップトップ上で、２分の１秒よりも短い時間に、達成されることができる。
【００２６】
図１は、電子計算装置１００の一実施形態の例を模式的に示す。
【００２７】
計算装置１００は、保存装置１１０を含む。保存装置１１０は、整数を多層化されたＲＮＳで保存する。多層化されたＲＮＳは、少なくとも２つの層を有する。第１（最上の、最も高い）層は、複数の上側の法Ｍｉの系列によって定義される。第２（下側の）層は、複数の下側の法ｍｉの系列によって定義される。保存装置１１０における整数は、複数の上側の法Ｍｉの系列を法とする上側の疑似剰余の系列として表現されることができる。上側の剰余のうちの少なくとも１つは、今度は、複数の下側の法ｍｉを法とする下側の剰余の系列として表現され、例えば、それは‘更に表現されて’いる。上側の剰余のそれぞれがこのように表現されることは要求されないが、これは、可能な実施形態である。下側のＲＮＳは上側の剰余の１つよりも多くについて上側の剰余を表現するように用いられることができることに注意されたい。実際、一実施形態では、同一の下側のＲＮＳが、上側の剰余のそれぞれについて用いられる。上側の剰余が下側のＲＮＳで表現される場合、整数は、ｍ１を法とする複数の剰余、ｍ２を法とする複数の剰余、などのように、上側の層にある剰余の数だけ、結局表現される。この場合、上側の剰余は、保存装置１１０に保存されるが、下側の剰余の系列の形式にのみ保存される。計算装置１００は、保存装置１１０に保存するために整数を受ける、及び、それらに計算を施すための、入力インタフェースを含んでいてもよい。乗算の結果は、保存装置１１０に保存されることができて、更なる計算のための入力として用いられることもできる。単層ＲＮＳで保存された整数のように、多層ＲＮＳで保存された整数は、加えられることもでき、これは、更に下に拡張されない。
【００２８】
計算装置１００は、プロセッサ回路１２０と更なる保存装置１３０とを含む。更なる保存装置１３０は、プロセッサ回路１２０によって実行可能なコンピュータ命令を含む。プロセッサ回路は、分散された形態で、例えば複数のサブプロセッサのように、実装されてもよい。更なる保存装置１３０は、下側乗算ルーチン１３１と上側乗算ルーチン１３２とを含む。多層ＲＮＳに２層よりも多くの層がある場合には、複数の乗算ルーチン、例えば、第１層乗算ルーチン、第２層乗算ルーチン、第３層乗算ルーチンなどが、あってもよい。乗算ルーチンは、追加の機能、例えば、例えばモジュラ加算などの他のモジュラ操作を実行することができることに注意されたい。
【００２９】
下側乗算ルーチン１３１は、下側ＲＮＳに表現された２つの整数の積を計算するように構成される。特に、下側乗算ルーチン１３１は、上記上側の剰余（Ｍｊ）を法とする同一の上側の法（Ｍｊ）に対応する２つの更に表現された上側の疑似剰余（ｘｊ、ｙ）を乗算するように用いられることができる。下側乗算ルーチン１３１は、適切である、上側の剰余演算（Ｍｊ）を法とする結果を生成する。さらに、法の操作の結果は、拡張限界を満たす疑似剰余である。拡張限界は、小さくてもよく、例えば２、又は１でさえもよく、又はより大きくてもよく、例えば数百でもよいが、それは系がＲＮＳ表現にとどまることを許容する。
【００３０】
上側乗算ルーチン１３２は、第１の整数（ｘｉ）の上側の剰余と対応する法（Ｍｉ）を法とする第２の整数（ｙｉ）の対応する上側の剰余との成分に関する乗算によって、上側の層に表現された第１の整数ｘと第２の整数ｙとの積を計算するように構成される。ここで、上側乗算ルーチンは、下側乗算ルーチンに、更に表現されている上側の剰余を乗算するように求める。上側の層のＲＮＳのダイナミックレンジは上側の法Ｍｉによって決定され、これに対して、下側の層のＲＮＳのダイナミックレンジは下側の法ｍｉによって決定されることに注意されたい。このようにして、下側の法は、複数回用いられてより大きなダイナミックレンジを作り上げることができる。通常、単層ＲＮＳではこれはうまくいかないことになることに注意されたい。剰余演算を繰り返すことは、ダイナミックレンジをまったく増大させることにはならない。
【００３１】
典型的には、上側と下側の法は、互いに素に選択される。しかし、発明者は、この条件は、便利であるけれども、厳格に必要であることはないことを理解している。多層ＲＮＳは、法が全ては互いに素に選択されない場合も動作することになり、この場合には、下側の層のダイナミックレンジを法ｍ１、・・・、ｍｋの最小公倍数としてとり、上側の層のダイナミックレンジを法Ｍ１、・・・、Ｍｋの最小公倍数としてとることができるものもある。一実施形態では、上側の法の少なくとも２つ又は下側の法の少なくとも２つは、１よりも大きい最大公約数をもつ。これは、難読化の追加のソースとして有用となり得る。例えば、Ｏｙｓｔｅｉｎ  Ｏｒｅによる“Ｔｈｅ  Ｇｅｎｅｒａｌ  Ｃｈｉｎｅｓｅ  Ｒｅｍａｉｎｄｅｒ  Ｔｈｅｏｒｅｍ”（本明細書に参照により含まれる）を参照されたい。
【００３２】
典型的には、計算装置１００は、独立型の装置ではなく、計算装置１００を用いてモジュラ演算を実行する、より大きな計算装置１５０の部分として用いられることになるであろう。例えば、より大きな装置１５０は、計算装置１００を含んでいてもよい。例えば、より大きな装置１５０は、例えば、暗号の目的のために、モジュラべき指数を計算することができる。
【００３３】
プロセッサ回路１２０がどのように構成されて２つの整数又は保存装置におけるそれらの表現に乗算を施すのかのさまざまな実施形態における更なる詳細を、以下に説明する。
【００３４】
図２ａは、電子計算装置２００の一実施形態の例を模式的に示す。図２ｂに従う実施形態は、図１を用いて表された種類のハードウェアを含む、多くの仕方で実装されることができる。
【００３５】
計算装置２００は、保存装置２３０を含む。保存装置２３０は、多層ＲＮＳ系の形式で整数を保存する。整数２１０と２２０が示されているが、より多くの整数が可能である。図２ｂは、整数２１０と２２０がもつことができる形態を表す。
【００３６】
図２ｂに示されているように、整数２１０は、複数の上側の法の系列を法とする複数の上側の剰余の系列２１１で表現される。整数がｘであるなら、上側の法は、Ｍｉであり、剰余の系列は、
【数１】
2020515928.tif 000003
であり得る。表記
【数２】
2020515928.tif 000004
は、法は、法Ｍｉを法とする疑似剰余を表す。疑似剰余は、Ｍｉよりも大きいこともあるが、拡張限界を満たし、例えば、ある拡張係数φについてφＭｉよりも小さい。一実施形態では、層ごとに単一の固定された係数がある。しかし、層ごとに、法ごとに異なる拡張係数をもつことが可能である。
【００３７】
図２ｂには３つの上側の法に対応する３つの上側の剰余が示されている。２つ以上の法が可能である。例えば、上側の剰余２１０．１は
【数３】
2020515928.tif 000005
であり、上側の剰余２１０．２は
【数４】
2020515928.tif 000006
であり、その他であり得る。上側の剰余のうちの少なくとも１つは、下側の法の系列（ｍｉ）を法とする上側の剰余（ｘｊ）の複数の下側の剰余の系列（
【数５】
2020515928.tif 000007
；２１２、２２２）を表すデータによって保存装置に更に表現される。
【００３８】
図２ｂには、３つの下側の法に対応する３つの下側の剰余が示されている。２つ以上の下側の法が可能であり、多くの上側と下側との法が等しいという必要はない。例えば、上側の剰余２１０．２、例えば
【数６】
2020515928.tif 000008
は、指数ｊを用いた剰余演算は更に表現されると仮定して、複数の下側の剰余の系列
【数７】
2020515928.tif 000009
によって保存装置に更に表現されてもよい。
【００３９】
例えば、下側の剰余２１０．２．１は、
【数８】
2020515928.tif 000010
であってもよく、下側の剰余２１０．２．２は、
【数９】
2020515928.tif 000011
などであってもよい。
【００４０】
上側の法Ｍｉの何れも下側の法ｍｉの積である必要はないということに注意することが重要である。特に、一実施形態では、更に表現された剰余演算Ｍｊは、下側の法の何れよりも大きいとともに、それらの何れの積でもない。また更なる一実施形態では、上側の法の何れも、冗長な法又は複数の法（これらが用いられる場合）の可能性のある例外はあるものの、下側の法の積ではない。
【００４１】
上側の剰余２１０．２が、更に表現されているただ１つの上側の剰余であるなら、保存装置２３０は、上側の剰余２１０．１、２１０．３と下側の剰余２１０．２．１、２１０．２．２及び２１０．２．３とを保存することがある。上側の剰余２１０．２はまさに下側の剰余の系列の形式で保存されることに注意されたい。一実施形態では、上側の剰余の全てが、下側の剰余の系列として保存される。換言すれば、数２１０は、法Ｍｉの第１の組をもつ第１のＲＮＳの形式２１１で表現され、これらの剰余のそれぞれは、法ｍｉの第２の組をもつ第２のＲＮＳの形式２１２で表現される。第２のＲＮＳの法は、上側の剰余のそれぞれについてと同一であってもよい。これは、必須ではないけれども、系の複雑さと表の数とをかなり減少させる。これらの剰余のそれぞれは疑似剰余であってもよいことに注意されたい。さらに、剰余は、例えば、Ｍｏｎｔｇｏｍｅｒｙ定数を用いて乗算されるというような、Ｍｏｎｔｇｏｍｅｒｙ乗算について適切な形式に、表現されることができる。剰余はまた符号化されてもよい。
【００４２】
第２の整数２２０は、第１の整数２１０と同一の形式で表現されることができる。複数の上側の剰余の系列２２１が示され、それらのうち上側の剰余２２０．１−２２０．３が示されている。上側の剰余のうちの少なくとも１つは、この場合上側の剰余２２０．２が、複数の下側の剰余の系列２２２として更に表現され、それらのうち下側の剰余２２０．２．１−２２０．２．３が示されている。
【００４３】
図２ａに戻って、計算装置２００は、上側乗算ルーチン２４４と下側乗算ルーチン２４２を更に含む。下側乗算ルーチン２４２は、下側の、例えば、第２のＲＮＳ系において、２つの上側の剰余を掛け合わせるように構成される。乗算に加えて、下側乗算ルーチン２４２は、追加のモジュラ演算、例えば、加算を有するように構成されてもよい。上側乗算ルーチン２４４は、上側のＲＮＳ系で表現された第１の整数２１０と第２の整数２２０を掛け合わせるように構成される。しかし、上側の法は、それ自体ＲＮＳ系の形式で表現されるが、これらの演算は、下側乗算ルーチン２４２と呼ばれる。上側乗算ルーチン２４４はまた、追加の演算、例えば、加算を有するように構成されてもよい。
【００４４】
底のＲＮＳにおける演算は、ルックアップテーブルを用いてモジュラ演算を実行してもよい。したがって、計算装置２００は、テーブルを保存するテーブル保存装置２４５を含んでいてもよい。これは、方法をホワイトボックスの応用に用いられるのに適する（ｗｅｌｌ−ｓｕｉｔｅｄ）ようにする。それは、小さいデータ要素のみを用いて動作するからである。よって、全ての演算が、テーブルルックアップによって行われることができる。一実施形態では、テーブル保存装置２４５は、下側の法のそれぞれについて、又は、２つの層よりも多い場合に、最も低い（底の）法、又は層が２つよりも多い場合、最も下側（底）の法について加算する及び乗算するためのテーブルを含む。
【００４５】
最も低い層の計算は、また、テーブルルックアップに替えて、他の手段、例えば、プロセッサの演算命令を用いて、又は演算コプロセッサを用いて実行されるようにも、実行されてもよい。一実施形態では、小さいｃで２ｍ−ｃ形式の法が、用いられることができる。例えば、ｍ＝１６、且つｃ＜８である。
【００４６】
ホワイトボックスの情報については、Ｃｈｏｗ他による論文、“Ａ  Ｗｈｉｔｅ−Ｂｏｘ  ＤＥＳ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎｆｏｒ  ＤＲＭ  Ａｐｐｌｉｃａｔｉｏｎｓ”を参照されたい。ホワイトボックスの更なる情報、特にステート（ｓｔａｔｅ）を用いる符号化については、国際公開ＷＯ２０１４０９６１１７の“Ｃｏｍｐｕｔｉｎｇ  ｄｅｖｉｃｅ  ｃｏｎｆｉｇｕｒｅｄ  ｗｉｔｈ  ａ  ｔａｂｌｅ  ｎｅｔｗｏｒｋ”を参照されたい。また、コンピュータプログラムをホワイトボックスの形態でどのように表現するかについては、国際公開ＷＯ２０１４０９５７７２の “Ｃｏｍｐｕｔｉｎｇ  ｄｅｖｉｃｅ  ｃｏｍｐｒｉｓｉｎｇ  ａ  ｔａｂｌｅ  ｎｅｔｗｏｒｋ”も参照されたい。ここに３つの文献が参照によって本明細書に含まれる。
【００４７】
一実施形態では、システムは、ホワイトボックス暗号化を用いて実行される。データは、ことによるとステートとともに、符号化された形式で表現される。ステートは冗長な変数であるので、符号化することは一意ではない。例えば、ある（ことによるとたいへん大きな）整数ｙは、その疑似剰余のリストによって、符号化された形式に（特に下側の剰余）、表現されることもある。すなわち、全ての剰余ｙｉが、形式
【数１０】
2020515928.tif 000012
で与えられ、ここで、ｓｉはステート変数であり、Ｅはある符号化の機能である（典型的には、データ−ステート空間における置換）。符号化された変数に対する操作は、典型的には、ルックアップテーブルを用いて実行される。より大きな操作は、必要であればより小さい操作に分けられる。結果として、計算は、テーブルネットワークの形式をとることができ、複数のルックアップテーブルを含む。あるテーブルは、入力としてアルゴリズムへの入力の部分をとり、例えば、数が逆数にされる。あるテーブルは、１つ以上の他のテーブルの出力を入力としてとる。あるテーブルは、出力の部分を生成する。例えば、ｍｉを法とする要求される演算は、ｍｉが相対的に小さい場合には少なくとも、テーブルルックアップのある形式によって典型的には実行される。
【００４８】
ホワイトボックスには、相対的に小さい（符号化された）データを用いて計算を行う方法が都合がよい。本発明では、これは、特にうまく動作する。何故ならば、多層のおかげで、それに対して計算が行われる剰余が小さく保たれることができるからである。例えば、符号化されたデータは、概ねバイトサイズであり得る。
【００４９】
発明者は、下側のレベルにおいて計算するための、例えば加算及び乗算するためのテーブルが、ほんの異なる下側の法についてであっても、同一の大きさであるなら、系が改善されることを、見出した。これは、変換テーブルの使用を回避する。例えば、まさに固有の剰余についての代わりに、それぞれの小さい法（例えば、たかだか８ビット）について、加算及び乗算のテーブルをバイトサイズの数に実装する。さらに、テーブルが同一の大きさを有するなら、テーブルの大きさは下側の法の大きさを漏らさない。
【００５０】
さらに、ｍ＝ｍａｘ  ｍｉが法ｍｉの最大の大きさであると仮定すると、ｍｉについてのルックアップテーブルは、例えば、ｍｉよりも小さい大きさの出力で、大きさＴｉのエントリをもつ。テーブルの何れかから出てくる剰余の最大の大きさは、１つのテーブルからの出力を他のテーブルについてのエントリとして用いることができる全てのＩについてＴｉ＞＝ｍである限り、ｍ−１である。最も効率的なのは、全てのｉについてＴｉ＝ｍである。一実施形態では、モジュラ演算操作のためのルックアップテーブルの大きさは、最大の下側の法の大きさのエントリを少なくとも受け入れるように拡張される。
【００５１】
テーブル保存装置２４５のためのテーブルを作成することは、演算操作、例えば、２つの入力の場合のｆ（ｘ１、ｘ２）を選択すること、及び、実施例では、ｘ１とｘ２の全ての値にわたって、全ての可能性のあるオペランドについて関数を計算し、結果をテーブルにリストすることによって行われることができる。テーブルが符号化されることになっている場合、
【数１１】
2020515928.tif 000013
の計算であり、この式において、関数Ｅ１、Ｅ２、Ｅｆは、それぞれ、２つの入力の及び出力の符号化である。
【００５２】
第１及び第２の乗算ルーチンのさまざまな可能な実施形態の更なる詳細を、以下に述べる。
【００５３】
多層ＲＮＳ表現は、３つ以上の層に拡張されることができ、これは、図３に示されている。図３は、例えば保存装置２３０に保存された、整数３１０を示す。整数は、法の第１の系列を法とする整数３１０の複数の第１の層の剰余の系列３１１によって表現される。第１の系列３１１のうち、３つの剰余が示されている。すなわち、第１の層の剰余３１０．１、３１０．２及び３１０．３である。
【００５４】
第１の層の剰余のうち、少なくとも１つ、図において剰余３１０．２は、第１の層の剰余のうち、第２の層の剰余の系列３１２として表現されている。この場合剰余３１０．２である。第２の系列３１２は、法の第２の系列を法とする第１の層の剰余を含む。第２の系列３１２の、３つの剰余が示されている。すなわち、第２の層の剰余３１０．２．１、３１０．２．２及び３１０．２．３である。
【００５５】
第２の層の剰余のうち、少なくとも１つ、図において剰余３１０．２．２は、第２の層の剰余の、この場合剰余３１０．２．２の、複数の第３の層の剰余の系列３１２として表現される。第３の層の系列３１３は、法の第３の系列を法とする第２の層の剰余を含む。第３の系列３１３の、３つの剰余が示されている。すなわち、第３の層の剰余３１０．２．２．１、３１０．２．２．２及び３１０．２．２．３である。
【００５６】
要点は、整数３１０が第３の剰余の系列を法とする剰余によって少なくとも部分的に表現されることである。第３の系列における法の大きさは、第２の系列における法の大きさよりもたいへん小さくなり、第１の系列における法の大きさよりもさらにたいへん小さくなり得る。
【００５７】
第１の層の剰余の全てが第３の層の剰余として表現される場合、この表現は、小さな法を用いた計算のみをしながら、整数３１０のように表現された整数について計算することを可能にする。
【００５８】
図３の多層ＲＮＳに示された、３つの階層的な層は、もっと多くの層に拡張されることができる。例えば、第２の層と第３の層とを、例えば図２に示されているように、多層ＲＮＳとみなすことが可能であり、これに階層のより高い層３１１が加えられる。
【００５９】
一実施形態では、モジュラ演算は、上側のレベルにおいて実行され、結果として、オーバフローの問題に見舞われない。モジュラ演算がほとんどの法について実行されない場合、表現の系は、オーバフローの問題に見舞われることがある。本明細書に記載された多層化されたＲＮＳ系は、いわゆる２レベル系と混同されるべきではない。２レベル系は、実際には２レベルのＲＮＳをもたないが、典型的には２ｎ±１の、又は小さいａで２ｎ±ａでさえの形式の、一対の関連する法を用いる。これらの場合では、より大きい法が、下側レベルにおける法の積として形成され、結果として、実際はただ１つのＲＮＳがある。
【００６０】
私たちが以下に提案する、ＲＮＳにおけるＭｏｎｔｇｏｍｅｒｙ乗算アルゴリズムの利点は、疑似剰余と後置されたＭｏｎｔｇｏｍｅｒｙ簡約を用いて計算の効率を上げることである。
【００６１】
剰余数系は、たいへん広く、例えばさまざまなデジタル信号処理アルゴリズムや暗号化に、用いられている。問題点は、ＲＮＳのとても大きなダイナミックレンジを実現するために、たいへん多くの又はたいへん大きな法の何れかが要求されることである。大きな法についてのモジュラ演算は、直接的に実行することが急激に難しくなる。一方、とても大きなダイナミックレンジを実現するために十分に小さい法が実にない。例えば、たかだか２５６の大きさの法に与えられるダイナミックレンジは、たかだか（２８）５４、２５６より小さいの５４の別個の素数の５４の素数の累乗をとることによって得られる、４３２ビットの数である。実際、大きさはたかだか２３６３である。任意のより大きいダイナミックレンジも全く可能ではない。また、モジュラ演算がルックアップテーブルによって実行される場合、最大の大きさのダイナミックレンジは、実に多数のテーブルを必要とすることになる。対照的に、実施形態は、例えば、たかだか２５６の大きさの１８の法のみを用いながら２０４８ビットよりも少し大きな値までの任意のダイナミックレンジも達成することを可能にする。本方法は、また、大規模な並列化を可能にする。本方法は、うまく設計されるとき、オーバフローの問題に見舞われことがなく、必要な都度、例えばモジュラべき乗について、応用されることができる。
【００６２】
さまざまな実施形態の興味深い側面は、次のようなものである。
−  ＲＮＳを用いてモジュラ演算を行って互いの上に２つ以上のＲＮＳを構築しこれによって底のＲＮＳのダイナミックレンジを最上のＲＮＳのダイナミックレンジに拡張する一般的な方法を用いることができるというアイデアである。一実施形態では、層化されたＲＮＳの系が提供され、そこでは、剰余又は疑似剰余の値それぞれが、下のＲＮＳのダイナミックレンジ内に含まれ、下のＲＮＳによって表現される。またさらに、これらの疑似剰余についてのモジュラ演算が、下のレベルにおける表現ＲＮＳのダイナミックレンジが常に考慮されるように、実行される。２つよりも多くの層、例えば、３以上の層が、可能である。一実施形態では、各層が、少なくとも２つの法についての剰余を含む。一実施形態では、第１の層の少なくとも１つの法が、第２の層における法に対して互いに素である。例えば、底ではない各層における少なくとも１つの法が、下のレベルのＲＮＳの法に対して互いに素である。一実施形態では、連続する層におけるＲＮＳは、漸次増大するダイナミックレンジをもつ。例えば、第１の層は、第２の層などよりも大きいダイナミックレンジをもつ。
−  疑似剰余が有界ならば（すなわち、既知の拡張限界がある）、ＲＮＳを用い、及びＲＮＳの法において加算と乗算のみを行い、結果を正確な剰余の代わりに疑似剰余の形式で提供する、モジュラ演算用の方法を有することで十分であるというアイデアである。これのさまざまな拡張限界について正確な表現の導出及び組合せである。ＲＮＳを用いる多くのモジュラアルゴリズムが、疑似剰余で動作するように適合させられることができる。
−  疑似剰余を用いる冗長な法を有する基底拡張の使用、及びある拡張限界についての正確な表現と組み合わせた、より高いレベルのＲＮＳにおける後置のモジュラ簡約と組み合わせられたＭｏｎｔｇｏｍｅｒｙ簡約を用いることの使用である。
−  もっぱらＲＮＳ内において適切な除数について“近似的な”除算−切り捨て操作を行い疑似剰余を取り扱うアイデアである。
−  底のレベルにおけるモジュラ演算について固定された大きさのルックアップテーブルの使用（すなわち、全ての小さい法がたかがか２８の大きさであるときの２８×２８のテーブルの使用）である。これによって、より高いレベルの基底拡張をより効率的にする。
−  それぞれ底のレベルにおける１つ以上の法の積であるより高いレベルにおける冗長な法の使用。これによって、正確なモジュラ演算がこれらの法について可能である。
−  アルゴリズムを平易化するために、疑似剰余
【数１２】
2020515928.tif 000014
について、法のみに依存する固定された定数Ｈｊを有する形式＜ｘｊ＞Ｍ＿ｊの、整数ｘの特別な表現の使用である。この改善は、Ｍｏｎｔｇｏｍｅｒｙ表現上で一般化する。例えば、
【数１３】
2020515928.tif 000015
は、Ｍｏｎｔｇｏｍｅｒｙ表現を与える。それで操作の約２０％の得をする。この改善なしに有効な実施形態を、例えば、全ての剰余がＭｏｎｔｇｏｍｅｒｙ表現である実施形態をつくることは可能である。
【００６３】
以下に、異なる基礎をなすモジュラ乗算法を用いたものを含む、本発明のいくつかの実施形態が開示される。現在、好ましい実施形態は、Ｍｏｎｔｇｏｍｅｒｙ乗算に基づいている。ＲＮＳにおいて難しい操作である（加算と減算は別個に考察されることになる）、モジュラ乗算を実行する方法を示される。系は多層を可能にするので、既にあるＲＮＳ層の上に新しいＲＮＳ層をどのようにして追加するのかを説明する。ここで、底の層は、例えば、テーブルルックアップによって、ある直接的な方法によって、又は何れかの他の方法によって、それについて要求されるモジュラ演算が実行される法ｍｉをもつＲＮＳとして、簡単にとられることができる。
【００６４】
その上に新しいＲＮＳを構築するための最上の層は、（互いに素な）法ＭｉをもつＲＮＳからなり、この最上の層は、次の拡張された限界の要求を満たすことになる。すなわち、次の特性をもつ正の整数ｍとφｉがある。整数が０≦ｘ、ｙ＜φｉＭｉとすれば、モジュラ積
【数１４】
2020515928.tif 000016
を表す、すなわちそれに対してｍｚ≡ｘｙ  ｍｏｄ  Ｍｉである、拡張限界φｉをもつ疑似剰余ｚ（従って、ｚ＜φｉＭｉで）を計算することができる。
【数１５】
2020515928.tif 000017
と記述してそのような整数を表すことになる。したがって、両方のオペランドが同一の拡張限界を満たす疑似剰余であるという条件で、全てのＭｉについて、モジュラ積を表し且つ所与の拡張限界を満たす疑似剰余を計算するいくつかの手段があることになる。
【００６５】
上記の要求を、整数ｘ、ｙが
【数１６】
2020515928.tif 000018
とすれば、ｍｚ≡ｘｙ  ｍｏｄ  Ｍｉ且つ
【数１７】
2020515928.tif 000019
で疑似剰余
【数１８】
2020515928.tif 000020
を計算することができるという要求に、弱めることができることになることに注意されたい。ここでの要点は、ある制約が、ｘ、ｙによって満たされて、モジュラ乗算
【数１９】
2020515928.tif 000021
の結果を表す疑似剰余ｚによってもまた満たされるように、ある制約をもつ必要があることである。
【００６６】
多層ＲＮＳを実行するために、第１の層を、例えばテーブルルックアップによって、要求されるモジュラ演算をそれについて直接的に実行することができる、多数の法ｍｉによって形成されたＲＮＳとしてとる。そのような小さい系では、全ての拡張限界φｉは、１に等しい。一実施形態では、ＲＮＳの最も低い層についての拡張限界は１であるが、より高い層についての拡張限界は１よりも大きい。本方法は、今度は、どのようにして、新しい法Ｎを、付加されることになる新しいＲＮＳ層の法のうちの１つとして加えるのかを、説明する。したがって、多層系は、最も低い層からより高い層へ築き上げられる。
【００６７】
上側の層におけるモジュラ乗算は、さまざまな方法を用いて行われることができる。例えば、第１の方法において、モジュラ乗算は、例えばＨｉｔｓ−Ｋａｌｔｏｆｅｎにおけるように、ＲＮＳの法についてのモジュラ加算／減算及びモジュラ乗算のみを用いて、ＲＮＳ内で切り捨てを用いた整数除算に基づくことができる。そして、この方法は、モジュラ簡約
【数２０】
2020515928.tif 000022
を行う、したがってまたもっぱらＲＮＳ内のモジュラ乗算を行うために用いられることができる。このアイデアを簡潔に述べる。この方法は、基底ＲＮＳ  Ｍｉ，・・・，Ｍｋ及び拡張ＭＫ＋１，・・・，ＭＫ＋Ｌにグループ化された、Ｍｉを法とするＫ＋Ｌからなる拡張されたＲＮＳを用いる。Ｍ＝Ｍ１・・・ＭＫ及び
【数２１】
2020515928.tif 000023
と記述して基底ＲＮＳ及び拡張のダイナミックレンジをそれぞれ表す。
【数２２】
2020515928.tif 000024
を用いることにする。整数ｈと法Ｎが０≦ｈ、Ｎ＜Ｍとすると、先ず反復ニュートンアルゴリズムを用いて
【数２３】
2020515928.tif 000025
を計算し、次にＲが与えられたなら、
【数２４】
2020515928.tif 000026
を計算し、次にＱ又はＱ＋１のうちの１つは
【数２５】
2020515928.tif 000027
に等しい。反復ニュートンアルゴリズムは、ｚ０＝０、ｚ１＝２をとり、そして、ｚｉ＝ｚｉ−１まで、
【数２６】
2020515928.tif 000028
である。このアルゴリズムは、ｚｉ又はｚｉ＋１の何れかが
【数２７】
2020515928.tif 000029
に等しければ、常に停止することが示されることができる。基本的なステップは、ｕ＝ｚｉ（２Ｍ−ｚｉＮ）又はｕ＝ｈＲで、
【数２８】
2020515928.tif 000030
を計算することである。例えば、
【数２９】
2020515928.tif 000031
がＭ１，・・・，ＭＫ＋Ｌを法とするＲＮＳの全てについて維持されることが用いられてもよい。数ｒ＝｜ｕ｜Ｍ＜Ｍは、１≦ｉ＜Ｋについて基底の剰余ｕｉによって表現される。そして、０≦ｒｉ−１≦Ｍｉで１≦ｉ≦Ｋについての混合基数表現
ｒ＝ｒ０＋ｒ１Ｍ１＋ｒｋ−１Ｍ１・・・ＭＫ−１
が、Ｍｉを法とするモジュラ計算から得られることができる。この表現が一旦得られたなら、基底拡張を行うことができる。すなわち、ｊ＝１，・・・，Ｌについて、
【数３０】
2020515928.tif 000032
とすることによって拡張されたＲＮＳにおいて欠けている剰余を得ることができる。今度は
【数３１】
2020515928.tif 000033
を計算するために、基底拡張がその後に続くＭＲ表現を計算することによって１≦ｉ≦Ｋで基底の剰余ｕｉからｒ＝｜ｕ｜Ｍの完全な表現を、先ず計算する。次に、拡張された法ＭＫ＋１，・・・，ｍＫ＋Ｌにおいて除算Ｑ＝（ｕ−ｒ）Ｍ−１の表現を計算する。これは、ＭがＭＫ＋ｊと
【数３２】
2020515928.tif 000034
とを法とする逆元（ｉｎｖｅｒｓｅ）をもつので可能である。最後に、第２の基底拡張によって、今度は拡張された剰余から、Ｑの完全な表現を計算する。例えば、実際に
【数３３】
2020515928.tif 000035
を、したがって、モジュラ加算、予め計算された定数によるモジュラ乗算、及びＲＮＳの法Ｍｉを法とするとするモジュラ乗算のみを用いて、法Ｍ１，・・・，ＭＫ＋ＬをもつＲＮＳにおいて、モジュラ簡約
【数３４】
2020515928.tif 000036
を、計算する。それで、Ｎ２＜Ｍという条件で、もっぱらＲＮＳ内において、ｈ＜Ｎ２から剰余｜ｘｙ｜Ｎを計算することができる。
【００６８】
上に概要を述べたようにモジュラ演算を行うこの第１の方法は、層化されたＲＮＳ系を構築するために用いられることができる。実際に、上述のように最上層に法ｍ１，・・・，ｍｋ＋ｌをもつ拡張されたＲＮＳをもつ、層化されたＲＮＳ系の上に新しいＲＮＳ層を構築するために、それぞれが
【数３５】
2020515928.tif 000037
を満たす法Ｍ１，・・・，Ｍｋ，ＭＫ＋１，・・・，ＭＫ＋Ｌをもつ新しいＲＮＳを構築する。いまや、ｍｉを法とするモジュラ加算及び乗算の意味において、Ｍｉ，・・・，ＭＫ＋Ｌによって形成されたＲＮＳにおいて必要に応じてＭｉのそれぞれについてモジュラ演算を実行することができる。すなわち、Ｍｉのそれぞれを法とするモジュラ演算を下の層に割り当てることができる。代わりに疑似剰余で動作するより効率的な体系を構築することが可能であることを見出したが、上に開示されたように結果としてできる系は、全く正確な剰余で動作する。本明細書に記載されたこの方法は、正確な剰余で動作するので、拡張限界φ＝１をもつ。
【００６９】
例えば、第２の方法において、モジュラ乗算は、Ｍｏｎｔｇｏｍｅｒｙ乗算に基づいてもよく、法ＮとＭｏｎｔｇｏｍｅｒｙ定数Ｍ（ｇｃｄ（Ｎ，Ｍ）＝１であると仮定する）とを伴う。オペランドＸ，Ｙ及びモジュラ乗算の結果Ｚ≡ＸＹ  ｍｏｄ  Ｎは、Ｍｏｎｔｇｏｍｅｒｙ表現であり、すなわち、数ｘ≡ＸＭ、ｙ≡ＹＭ、ｚ≡ＺＭ  ｍｏｄ  Ｎによって表現されるので、ｘｙ≡ｚＭ  ｍｏｄ  Ｎである。Ｍｏｎｔｇｏｍｅｒｙ表現に関して、式
ｈ＋ｕＮ＝Ｍｚ、
（ここでｈ＝ｘｙはｘとｙの通常の（整数の）積である）の整数の解ｚ、ｕを見つけたい。一桁のＭｏｎｔｇｏｍｅｒｙ乗算法の従来の形式は、次のようなものである。定数
【数３６】
2020515928.tif 000038
を予め計算し、次に、
【数３７】
2020515928.tif 000039
を行う。
【００７０】
ｈ＋ｕＮ≡０  ｍｏｄ  Ｎであるから、ステップ３における除算は正確であり、さらに、結果ｚについて、Ｍｚ≡ｈ≡ｘｙ  ｍｏｄ  Ｎであり、さらに、ｘ、ｙが実際に拡張限界φをもつ疑似剰余であるなら、０≦ｘｙ＜φＮであり、よって、
【数３８】
2020515928.tif 000040
。
もし、
【数３９】
2020515928.tif 000041
なら、結果ｚは、拡張限界０≦ｚ＜φＮを再び満たす。例えば、φ＝２とするように、Ｍ≧４Ｎを要求することで十分である。より一般的には、０＜ε＜１でφ＝１／εとすると、最終の結果は、法が
Ｎ≦ε（１−ε）Ｍ
を満たすという条件で、拡張限界φを再び満たす。
【００７１】
ＲＮＳにおける実行についてこのアルゴリズムを適応させるさまざまな可能な方法がある。ＲＮＳにおける
【数４０】
2020515928.tif 000042
の計算は、単純であり、例えば、予め計算されるか又は別な方法でなされてもよい。興味深いことに、右のＲＮＳにおけるｕの表現も得られる。例えば、
【数４１】
2020515928.tif 000043
は、ｕを決定するが、左のＲＮＳにおけるｕの剰余を与えるだけである。ステップ３におけるｚは、Ｍによる除算を用いることもできるので、右のＲＮＳにおいてのみ直接的に計算されることができる。しかし、基底拡張を用いることによって、ｕについてか、又はｚについて、残りも計算されることができる。後者の選択がわずかによりよく動作することを見出された。
【００７２】
より良い方法は、ダイナミックレンジＭ＝Ｍ１・・・Ｍｋをもつ、基底又は左のＲＮＳ  Ｍ１，・・・，ＭＫ、及びダイナミックレンジＭ’＝ＭＫ＋１・・・ＭＫ＋Ｌをもつ、拡張又は右のＲＮＳ  ＭＫ＋１，・・・，ＭＫ＋Ｌにグループ化された、Ｍｉを法とするＫ＋Ｌからなる拡張ＲＮＳを用いると思われる。これらの左と右のＲＮＳは、多層ＲＮＳの層と混同されるべきではないが、同一の層の２つの部分である。例えば、以下の方法は、Ｊｅａｎ−Ｃｌａｕｄｅ  Ｂａｊａｒｄ  Ｓｙｌｖａｉｎ  Ｄｕｑｕｅｓｎｅ、Ｍｉｌｏｓ  Ｅｒｃｅｇｏｖａｃ、Ｎｉｃｏｌａｓ  Ｍｅｌｏｎｉや、モジュラ積和についての剰余体系の効率：Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ  Ｃｒｙｐｔｏｇｒａｐｈｙに対する応用や、ＳＰＩＥの予稿集：Ａｄｖａｎｃｅｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ａｌｇｏｌｉｔｈｍｓ，  Ａｒｃｈｉｔｅｃｔｕｒｅｓ，  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎｓ．  ＸＶＩ，２００６年秋、６３１３、２００６から用いられることができる。
【００７３】
Ｍｏｎｔｇｏｍｅｒｙ定数Ｍは、左の法の積としてとられることができる。さらに、基底拡張を行うために、追加の、冗長な法Ｍ０を用いることにする。正確な剰余を用いる代わりに疑似剰余を用いるこれらの方法を用いることに注意されたい。ｕについての代わりにｚについての基底拡張、及び、以下の方法における新規な後置の加算／乗算ステップ２及び５に、特に注意されたい。
【００７４】
私たちの方法は、ｈ＝ｘｙで、方程式
ｈ＋ｕＮ＝ｚＭ  （２）
の適切な解（ｕ、ｚ）を見つけることからなる。ｚ＝Ｒ（Ｎ，Ｍ）（ｈ）を記述して私たちのアルゴリズムによって見つけられた解を表し、この解をｈのＭｏｎｔｇｏｍｅｒｙ簡約（Ｍｏｎｔｇｏｍｅｒｙ  ｒｅｄｕｃｔｉｏｎ）と呼ぶことにする。Ｍｏｎｔｇｏｍｅｒｙ簡約は、Ｍｏｎｔｇｏｍｅｒｙ定数Ｍによる整数除算に対する近似を提供し、よって、数の大きさを減ずる手段を提供することに、注意されたい。アルゴリズムのアイデアは、次のようなものである。左の法Ｍｉについて、式（２）を用いてｕ≡ｈ（−Ｎ）−１  ｍｏｄ  Ｍｉである適切なｕを計算することができる。可能な解は、全てのｉ≦Ｋについて
【数４２】
2020515928.tif 000044
で
【数４３】
2020515928.tif 000045
をとることである。これは、必ずしも最小の可能なｕではないが、ｈ＋ｕＮ≡０  ｍｏｄ  Ｍを確実に満たす。次に、右及び冗長な法Ｍｊについて疑似剰余
【数４４】
2020515928.tif 000046
を計算することができる。最後に、基底拡張を行って左の法Ｍｉを法とするｚの剰余を計算することができる。すなわち、
【数４５】
2020515928.tif 000047
で
【数４６】
2020515928.tif 000048
を記述し、先ず冗長な剰余を用いてｑを正確に計算し、次に、ｚについてこの表現を用いて基底の法Ｍｉを法とするｚの疑似剰余を決定することができる。
【００７５】
今度は、この方法の一実施形態の詳細に戻る。方法についての、設定、入力及び結果を一覧にすることによって始める。以下を用いる。
【００７６】
１．法Ｎ、ダイナミックレンジＭ＝Ｍ１・・・ＭＫ及びＭ’＝ＭＫ＋１・・・ＭＫ＋Ｌをもつ、基底の法Ｍ１，・・・，ＭＫによって形成された基底（左の）ＲＮＳ及びＭＫ＋１，・・・，ＭＫ＋Ｌによって形成された拡張（右の）ＲＮＳ、並びに冗長な法Ｍ０が与えられる。好ましくは、全ての法は、（Ｍ０，Ｎ）について起こりうるものを除いて一対について互いに素である。上に注記したように、全ての法が互いに素であることは厳格に必要な考えでないが、これは、より小さいダイナミックレンジに導くことがある。
【００７７】
２．次のように、拡張されたＲＮＳの法についてのＭｏｎｔｇｏｍｅｒｙ乗算及びＭｏｎｔｇｏｍｅｒｙ簡約の実行
−０≦ａｉ，ｂｉ＜φ１Ｍｉで
【数４７】
2020515928.tif 000049
であるなら、ｅｉは、全てのｉについて、ｍｅｉ≡ａｉｂｉ  ｍｏｄ  Ｍｉ及び０≦ｅｉ＜φ１Ｍｉである疑似剰余Ｍｉである。
−０≦ａｉ＜φ１Ｍｉ且つ０≦Ｃｉ＜Ｍｊで
【数４８】
2020515928.tif 000050
であるなら、全てのｉについて、０≦ｅｉ＜φ１Ｍｉである（可能なより厳格な拡張限界が、真の剰余、例えば定数によって、Ｍｉを法とする乗算について、当てはまる）。
−
【数４９】
2020515928.tif 000051
がｈｉの計算されたＭｏｎｔｇｏｍｅｒｙ簡約であるなら、ｚｉは、
【数５０】
2020515928.tif 000052
という条件で、ｍｚｉ≡ｈｉ  ｍｏｄ  Ｍｉ及び０≦ｚｉ＜φ１Ｍｉである疑似剰余である。
−冗長な法についてのモジュラ演算が正確である、すなわち、全ての疑似剰余の法Ｍ０が実際に真の剰余である。
【００７８】
それで、定数による乗算について、拡張限界φ１、及び拡張限界φ１をもつＭｉを法とするモジュラ演算を実行する。冗長な法について、拡張限界１が等しいことが要求される。実際に、これらの拡張限界が、法Ｍｉに依存することさえもある。簡単のために、以下の説明においてその場合を含めないことにした。ここで、ｍは、下のＲＮＳレベルについてのＭｏｎｔｇｏｍｅｒｙ定数である。
【００７９】
３．Ｍｏｎｔｇｏｍｅｒｙ乗算アルゴリズムのための入力は、冗長な法を除いて、拡張係数φ１をもつＭｏｎｔｇｏｍｅｒｙ表現において、全体の法の組Ｍ０，・・・，ＭＫ＋Ｌについて表現された、ｘ、ｙ＜φＮである、Ｎを法とする疑似剰余ｘ、ｙである。すなわち、ｘは、ｍｘ≡ａｉ  ｍｏｄ  Ｍｉ、及び０≦ｉ≦Ｋ＋Ｌについて０≦ａｉ＜φ１Ｍｉ及びａ０≡ｘ  ｍｏｄ  Ｍ０でａ＝（ａ０，ａ１，・・・，ａＫ＋Ｌ）によって表現され、同様に、ｙは、ｍｙ≡ｂｉ  ｍｏｄ  Ｍｉ、及び０≦ｉ≦Ｋ＋Ｌについて０≦ｂｉ＜φ１Ｍｉ及びｂ０≡ｙ  ｍｏｄ  Ｍ０で、ｂ＝（ｂ０，・・・，ｂＫ＋Ｌ）によって表現される。そのような表現を剰余Ｍｏｎｔｇｏｍｅｒｙ表現と呼ぶことにする。
【００８０】
４．Ｍｏｎｔｇｏｍｅｒｙ乗算又は簡約の計算された出力は、
０≦ｃｉ＜φ１Ｍｉ及びに１≦ｉ＜Ｋ＋Ｌついてｍｃｉ≡ｚ  ｍｏｄ  Ｍｉでｃ＝（ｃ０，ｃ１，・・・，ｃＫ＋Ｌ）によってＭｏｎｔｇｏｍｅｒｙ表現に全体の法の組について表現された、０≦ｚ＜φＮである疑似剰余であることになり、Ｎよりも小さい定数によるＭｏｎｔｇｏｍｅｒｙ乗算の結果について、多分φよりも小さいφで、ｚ＜φＮとなるであろう。ここで、ｚは、ｘとｙのＭｏｎｔｇｏｍｅｒｙ乗算の場合Ｈ＝ｘｙで、（２）を満たす。
【００８１】
実行されるモジュラ演算操作は次のようなものである。
【００８２】
１．ＲＮＳにおける整数の乗算
上記ポイント３におけるように入力ｘ、ｙが与えられると、０≦ｉ＜Ｋ＋Ｌ及び
【数５１】
2020515928.tif 000053
について、
【数５２】
2020515928.tif 000054
を計算することによって、剰余Ｍｏｎｔｇｏｍｅｒｙ表現ｅ＝（ｅ０，ｅ１，・・・，ｅＫ＋Ｌ）における全体の法の組について表現された、整数の積ｈ＝ｘｙを計算することができる。上記を鑑み、特にポイント２において、これは実際ｈについて剰余Ｍｏｎｔｇｏｍｅｒｙ表現を生成する。
【００８３】
２．Ｍｏｎｔｇｏｍｅｒｙ簡約
ｈがｅ＝（ｅ０，ｅ１，・・・，ｅＫ＋Ｌ）のように剰余Ｍｏｎｔｇｏｍｅｒｙ表現に表現されると仮定すると、Ｍｏｎｔｇｏｍｅｒｙ簡約ｚ＝Ｒ（Ｍ，Ｎ）（ｈ）は、次のステップによって計算される。
【００８４】
１．下側の法について（すなわち、ｉ＝１，・・・，Ｋについて）
【数５３】
2020515928.tif 000055
を計算する。結果として、整数
【数５４】
2020515928.tif 000056
は、ある整数ｚについてｖ＝ｈ＋ｕＭ＝ｚＮを満たす。
【００８５】
２．次に、（積及び和を計算する成分に関する整数加算及び整数乗算を用いて）
【数５５】
2020515928.tif 000057
を計算し、次に、拡張の法について（すなわち、Ｊ＝Ｋ＋１，…，Ｋ＋Ｌについて）Ｍｏｎｔｇｏｍｅｒｙ簡約
【数５６】
2020515928.tif 000058
が続く。冗長な法について、単に
【数５７】
2020515928.tif 000059
を計算する。
【００８６】
したがって、ｃｊは、ｚ＝（ｈ＋ｕＭ）／Ｎの拡張及び冗長剰余についてＭｏｎｔｇｏｍｅｒｙ表現を形成する。
【００８７】
底のレベルのＲＮＳについて、全てのモジュラ演算は、Ｍｏｎｔｇｏｍｅｒｙ定数１を用いて、直接であり、それで、底のレベルにおける、γｊについての加算及び乗算は、モジュラ操作として実行されることになり、簡約は要求されないことになる。
【００８８】
３．今度は、拡張の法について（すなわち、Ｋ＋１≦ｊ≦Ｋ＋Ｌについて）
【数５８】
2020515928.tif 000060
を計算する。
【００８９】
４．次に、正確なモジュラ演算を用いて、
【数５９】
2020515928.tif 000061
（拡張の法にわたっての和）を計算する。今、ｚ＝Σηｊ（Ｍ’／Ｍｊ）−ｑＭ’である。
【００９０】
５．最後に、（積と和を計算する成分に関する整数加算と整数乗算を用いて）
【数６０】
2020515928.tif 000062
を計算し、下側の法について（すなわち、ｉ＝１，・・・，Ｋについて）Ｍｏｎｔｇｏｍｅｒｙ簡約
【数６１】
2020515928.tif 000063
が続く。
【００９１】
後置の簡約を用いたモジュラドット積とモジュラ和
ｔ項ドット積和σ＝＜ｘ（１）ｃ（１）＋・・・＋ｘ（ｔ）ｃ（ｔ）＞Ｎ、ここでｃ（ｉ）は定数、を計算するために、ＲＮＳにおいて、
ｈ＝ｘ（１）｜ｃ（１）Ｍ｜Ｎ＋・・・＋ｘ（ｔ）｜ｃ（ｔ）Ｍ｜Ｎ’
を計算し、それで、成分に関する整数の乗算及び加算による、
σ＝Ｒ（Ｎ，Ｍ）（ｈ）  （３）
が続く。
【００９２】
同様に、余分な係数｜Ｍ−１｜Ｎを次の計算へ組み込みながら、定数ｃ（ｉ）＝１をとる上記方法か、又は代わりに疑似剰余σ’＝Ｒ（Ｎ，Ｍ）（Ｓ））、ここでＭσ’≡σ  ｍｏｄ  Ｎである、を計算することの何れかによって、ｔ項の和Ｓ＝＜ｘ（１）＋・・・＋ｘ（ｔ）＞Ｎ、ここで計算することができる。
【００９３】
可能な限界
上記のアルゴリズムにおける全ての要求される定数は予め計算されることができることに注意されたい。上記方法は、直ちに実行されることができるが、多数の条件（限界）がオーバフローを回避すること及び最後の結果が特定された拡張限界を再び満たすことを維持することを条件に、全ての可能な入力について正しく動作するだけであろう。
【００９４】
最初に、法についての可能な要求をリストする。先ず、法Ｍ０及びＭ１，・・・，ＭＫ＋Ｌは、ＲＮＳを形成するべきであるので、好ましくは対で互いに素であるべきである。さらに、多分Ｍ０を除いて、全ての法は、法Ｎと互いに素であるべきである。ＭとＭ’が互いに素であるなら、左と右の法は互いに素であること、及び、Ｍ０がＭ’と互いに素であるなら、Ｍ０は右の法と互いに素であることに注意されたい。これらのことは望ましい。
【００９５】
今度は、０≦ｘ，ｙ＜φＮという条件で、Ｍｏｎｔｇｏｍｅｒｙ簡約ｚ＝Ｒ（Ｎ，Ｍ）（ｈ）についてｈ＝ｘｙに対して作業するために、すなわち、０≦ｘ，ｙ＜φＮで数ｚを再び生成するために、
【数６２】
2020515928.tif 000064
（ここで、ＵＭは
【数６３】
2020515928.tif 000065
の最大の大きさである）が求められる。（４）が成り立つなら、Ｍｏｎｔｇｏｍｅｒｙ簡約ｚ＝Ｒ（Ｎ，Ｍ）（ｈ）は、０≦ｈ＜φ２Ｎ２であるときはいつでも０≦ｚ＜φＮでｚを生成するであろう。μｉが拡張限界μｉ＜φ１Ｍｉを満たすなら、Ｕ＝Ｋφ１である。同様の状態が、他の乗算アルゴリズムにおいて再び生じ、次のように解決されることができる。不等式から、φ＞Ｕ＞０であるとわかる。０＜ε＜１で
φ＝Ｕ／ε
と記述して、
Ｎ≦ε（１−ε）Ｍ／Ｕ、  Ｕ＝Ｋφ１
を有していることになると結論する。
【００９６】
依然として扱うことができる法Ｎの大きさを最大化するために、ε＝１／２を選ぶべきであることに注意されたい。
【００９７】
ある定数Ｃ＜Ｎについてｈ＝ｘＣを減少させる場合、結果ｚ＜（φＮ／Ｍ＋Ｕ）Ｎであることを得る。すなわち、定数によるＭｏｎｔｇｏｍｅｒｙ乗算は、拡張限界φ＝φＮ／Ｍ＋Ｕをもつ。φ＝Ｕ／ε及びＮ≦ε（１−ε）Ｍ／Ｕから、
φ≦Ｕ＋１＜Ｕ＋１＝εφ＋１
であることを保証することができることがわかる。
【００９８】
法ｈは、基底、拡張及び冗長の法によって形成されたＲＮＳにおいてオーバフローなしにいつでも表現可能であるべきである。したがって、
φ２Ｎ２≦Ｍ０ＭＭ’  （５）
であり、さらに、ｚが、拡張の法によって形成されたＲＮＳにおいてオーバフローなしに表現されるために、
φＮ≦Ｍ’
であることが要求される。
【００９９】
Ｎ≦ε（１−ε）Ｍ／Ｕ且つφ＝Ｕ／εであるから、φＮ≦（Ｕ／ε）ε（１−ε）Ｍ／Ｕ＝（１−ε）Ｍであると結論する。すなわち、それをφＮ≦Ｍ’と組み合わせる場合、φ２Ｎ２≦（１−ε）ＭＭ’＜Ｍ０ＭＭ’であることを見出すので、この条件は、他の条件によって暗示される。φＮ＜（Ｕ／ε）ε（１−ε）Ｍ／Ｕ＝（１−ε）Ｍであるから、限界φＮ＜Ｍ’は、
（１−ε）Ｍ≦Ｍ’
である場合、確かに満たされる。
【０１００】
ステップ４において、
【数６４】
2020515928.tif 000066
となる。すなわち、０≦ｚ＜φＮ且つ０≦ηｊ＜φ１Ｍｊであるから、
【数６５】
2020515928.tif 000067
であり、０≦ｑ＜φ１Ｌであると結論する。それで、ｑは、
Ｍ０≧φ１Ｌ
であるという条件で、その剰余の法と冗長な法Ｍ０とから決定される。
【０１０１】
最後に、アルゴリズムのステップ２とステップ５における２つの後置の簡約が動作する（すなわち、十分小さいｚを生成する）ために、γｉ，γｊ＜φ２Ｎ２であることが必要である。ｉ＝１，・・・，Ｋ及びｊ＝Ｋ＝１，・・・，Ｋ＋ＬについてＮの限界μｉ＜φ１Ｍｉ及びηｊ＜φ１Ｍｊを用いて、
【数６６】
2020515928.tif 000068
を要求することもできることがわかる。
【０１０２】
これらの限界を理解するために、以下を提供する。底のレベルを上回るレベルにおいて、全ての通常の法は、たいへん大きく且つ概ね等しく、冗長な法よりもたいへん大きい。次に、φ≒Ｕ１及びε１≒１／２、所望の値を記述して、限界がＫ、Ｌ≦４Ｕ１であることを概ね表すことを見出す。例えば、２レベル系について、Ｕ１＝Ｋ、底のＲＮＳにおける基底の法の数であるので、第１のレベルにおける基底と拡張の法の数ＫとＬが、それぞれ、Ｋ、Ｌ≦４ｋを満たすことをほぼ必要である。私たちの２レベルの好ましい実施形態では、これらの限界は自動的に出てくることがわかる。
【０１０３】
計算された疑似剰余σが拡張限界０≦σ＜φＮを満たすことを保証するために、（３）における数ｈがφ２Ｎ２よりも小さいことが保証されるべきであり、これは、全てのｉについてｘ（ｉ）が０≦ｘ（ｉ）＜Ｎを満たす場合、限界
ｔ≦φ２／θ
に至る。ここで、一般にθ＝φである。
【０１０４】
アルゴリズムのステップ２と５における後置の簡約は、法Ｍｉについての（Ｋ＋１）項及び（Ｌ＋１）項のドット積であり、μｉとηｊについてより良い限界があるので、これらは、わずかに厳しくない条件のもとで動作する。
【０１０５】
多くの実際の問題が以下で扱われる。
【０１０６】
１．テーブルの大きさ
法ｍ０，ｍ１，・・・，ｍＫ＋Ｌをもつ底のＲＮＳにおいて今や実行された、上記のアルゴリズムを考える。アルゴリズムのステップ２と５において、数μｉ（剰余の法ｍｉを表す）とηｊ（剰余の法ｍｊを表す）が、異なる法ｍｓを法とする剰余である定数と掛け合わされる。より高いレベルにおいて、これは、問題はない。なぜならば、両方の数は、ＲＮＳにおいて１つ下側のレベルの法について表現されるが、しかし、最も低いレベルにおいて、かかる数は、それぞれ、範囲［０，ｍｉ）又は［０，ｍｊ）からであり、法ｍｓについての加算又は乗算のテーブルにおけるエントリとして用いられることが想定されるからである。結果として起こる問題は、２つの異なる仕方で解決されることができる。
【０１０７】
１．先ず、それぞれの法ｍｓについて、ｍｓを法とするそれの剰余
【数６７】
2020515928.tif 000069
に数０≦ａ＜ｍａｘｔｍｔを変換する単項簡約テーブルＲｓを用いることができる。これは、異なる演算テーブルをもつことを可能にするが、このために、平均のより小さい大きさにおいて、最も低いレベルにおける演算操作のための余分なテーブルアクセスを要求し、このために、プログラムをより低速にさせることになる。
【０１０８】
２．第２の解決は、全ての演算テーブルを固定された大きさＳ＝ｍａｘｓｍｓに拡張することである。これは、わずかにより大きなテーブルの負担で、増加した速度及び平易さのために、最も低いレベルにおける楽な演算操作及びモジュラ変換が不要になることを可能にする。
【０１０９】
速度を重要視する、好ましい実施形態において、私たちは、第２の解決を選択した。
【０１１０】
２．冗長な法
底のレベルにおいて、冗長な法ｍ０がたいへん小さいことを許容する、ｍ０≧ｋを要求することができる。次のレベルにおいて、冗長な法Ｍ０が、典型的には最大の小さい法よりもわずかに大きい、少なくとも概ねＬ（ｋ＋１）の大きさであることを要求する、Ｍ０≧Ｋφ１を要求することができる。また、前の節におけるアルゴリズムのステップ２において、Ｍｏｎｔｇｏｍｅｒｙ簡約を用いてではなくテーブルルックアップによって、より簡単な仕方で冗長な法についてこのステップを行いたい。これは、私たちが“大きな”μｉ（それなので小さい法についてのＲＮＳ表記において）から容易な仕方で大きく冗長な剰余を得ることができることを要求する。繰り返すと、結果として起こる問題は、２つの仕方で解決されることができる。
【０１１１】
１．Ｍ０＝ｍ０≧Ｌ（ｋ＋１）をとる。次に、全てのテーブルが、わずかにより大きな大きさである必要があるが、簡明である。そして、他の小さな法の全てについての余分な簡約テーブルをもつことは、速度を犠牲にして、テーブルの大きさを減少させることを助けることになる。
【０１１２】
２．ある適切な除数及び適切なｔについて、Ｍ０を、１≦ｉ≦ｔについて
【数６８】
2020515928.tif 000070
で積
【数６９】
2020515928.tif 000071
であるようにとる（典型的には
【数７０】
2020515928.tif 000072
）。ここで、全てのｉについてｒｉ∈｛１，・・・，ｋ＋ｌ｝である。次に、適切な剰余の法
【数７１】
2020515928.tif 000073
は、対応する剰余の法
【数７２】
2020515928.tif 000074
からいつでも利用可能であり、全ての操作は、１か所においてを除いて、平易である。私たちは、大きな法のそれぞれについて小さな法についてのＭｏｎｔｇｏｍｅｒｙ  ＲＮＳ表現における大きな剰余の一覧、及び剰余の法
【数７３】
2020515928.tif 000075
（又は単に法
【数７４】
2020515928.tif 000076
）のリストの形式における最後の大きき冗長な剰余によって、大きな数を表現することができる。次に、アルゴリズムのステップ４において、単なる２ｌにかえて２ｌｒ操作をして、
【数７５】
2020515928.tif 000077
のそれぞれを法とする剰余のリストとしてｑを得る。“大きな”法についてのアルゴリズムのステップ４において、数μｉの剰余の法Ｍ０を法とする剰余を必要とし、これらの剰余は、“大きな”剰余の法が底のレベルにおいて法ｍｉの（除数の）積である場合に直ちに利用可能である。今度はステップ５において、
【数７６】
2020515928.tif 000078
を利用でき、ｑｈｉ  ｍｏｄ  Ｍｉを（疑似）剰余として計算するために、全てのｊについて、ｑｈｉ，ｊ  ｍｏｄ  ｍｊを必要とし、これは、最後のｒの小さい法に直接関連するが、他の小さい法について、基底拡張のある形式、又は追加のテーブルを、用いることもできる。
【０１１３】
以下に、この乗算の方法に基づいて有利な実施形態が示される。その実施形態では、私たちは、ｋ＝ｌ＝９、Ｋ＝Ｌ＝３２をとしたので、ｍ０≧１０とすることもできる。大きく冗長な法について、アルゴリズムのステップ４において、Ｍ０の大きさが少なくともｑの値の最大の大きさ３２０であることを確実にするためにＭ０≧３２０であることが必要である。ゆえに、ｒ＝２をとり、したがってＭ０＝ｍｋ＋ｌｍｋ＋ｌ−１＝２５３・２３３であり、そして、ｑ０＝ｑ１又はｑ０＝ｑ１＋２３３である場合ｑ＝ｑ０であり、ｑ１＝ｑ０＋２０の場合ｑ＝ｑ０＋２５３である。ｑ０は、乗算のテーブルについて最大のエントリの大きさに当たるので、アルゴリズムのステップ４におけるｑによる乗算を、多分２５３による乗算及び加算が後に続く、ｑ０による乗算として実行することができる。このようにして、全体のアルゴリズムについての総ての余分なコストが、今や、ｉｆ文及び２Ｋテーブルルックアップのコストに限定されることになる。
【０１１４】
事前及び事後処理、例えば、Ｍｏｎｔｇｏｍｅｒｙ形式への／からの、又はＲＮＳ表現への／からの変換が、要求されることもある。これらは一般的な操作であり、さらには考察されない。例えば、Ｍｏｎｔｇｏｍｅｒｙ表現における計算を開始することの前に、データは、Ｍｏｎｔｇｏｍｅｒｙ及びＲＮＳの形式にされる必要が依然としてあることもある。計算の後、データは、法の適切な倍数を減ずることによって剰余に簡約され（ｒｅｄｕｃｅｄ）なければならないこともある。Ｍｏｎｔｇｏｍｅｒｙ定数も、除かれなければならないこともあり、データは、ＲＮＳ表現などから再構築されなければならないこともある。
【０１１５】
前の節におけるアルゴリズムは、改良されることができ、実際に、アルゴリズムにおけるステップのうちの１つ（及び多分２つ）なしで行うことができる。ここで、改良を述べることにする。アイデアは、剰余が基底拡張ステップによりよく適合するように表現される仕方を変更することである。前と同じ表記及び仮定を用いることにする。例えば、一実施形態では、計算装置が示され、そこでは、少なくとも上側の層について法Ｍｍに対して定数Ｈｓ＿の系列が定義されるので、剰余ｘｓが、ｘｓ＝Ｈｓｙｓ  ｍｏｄ  Ｍｓである疑似剰余ｙｓとして表現される。ここで、少なくとも１つのＨｓはｍ−１  ｍｏｄ  Ｍｓと異なる。これらの表現は、Ｈｓ及びＭｓが互いに素であるという条件で、一意である。Ｈｓは、上で用いられた又は参照文献におけるＭｏｎｔｇｏｍｅｒｙ定数と異なっていてもよい。利点は、ｈ＝ｘｙの容易な計算である。なぜならば、全てのｓについて、剰余ｘｓ及びｙｓの表現のＭｏｎｔｇｏｍｅｒｙ乗算によるｈの剰余ｈｓの表現を見つけ出すことができる。
【０１１６】
私たちの出発点は、ｍに対して互いに素であり且つ限界ｎ≦Ｂ１を満たす全ての法ｎについて、拡張限界φ１及び定数−拡張限界φ１を用いて、Ｍｏｎｔｇｏｍｅｒｙ簡約ｚ＝Ｒ（ｎ，ｍ）（ｈ）、Ｍｏｎｔｇｏｍｅｒｙ乗算
【数７７】
2020515928.tif 000079
、及び“重み付けされた和”を（ソフトウェアで、又はハードウェアで）実行する装置を構築する或いは構成することができる。すなわち、０≦ｘ，ｙ＜φ１ｎ及び
【数７８】
2020515928.tif 000080
で整数ｘ、ｙ及びｈ並びに０≦ｃ＜ｎで整数定数ｃが与えられたなら、０≦ｚ＜φ１ｎでｚ≡ｈｍ−１  ｍｏｄ  ｎ又はｚ≡ｘｙｍ−１  ｍｏｄ  ｎを満たす整数ｚを計算するアルゴリズム及び０≦ｚ＜φ１ｎでｚ≡ｃｙｍ−１  ｍｏｄ  ｎを計算するアルゴリズムをもつ。さらに、
【数７９】
2020515928.tif 000081
という条件で、全てのｉ，・・・，ｔについて０≦ｃｉ＜ｎで所与の整数定数ｃ１，・・・，ｃｔ及び全てのｉについて０≦ｘｉ＜φ１ｎで整数ｘ１，・・・，ｘｔについて、“重み付けされた和”Ｓ＝ｃ１ｘ１＋・・・＋ｃｔｘｔの計算を全てのかかる法について実行する装置を構築することができることを仮定する。これに代えて、仮定は、例えば、対称な拡張限界を含んでもよい。すなわち、｜ｘ｜、｜ｙ｜≦φ１ｎ、
【数８０】
2020515928.tif 000082
及び｜ｃ｜≦ｎ／２を仮定して、アルゴリズムは、｜ｚ｜≦φ１ｎ又は｜ｚ｜≦φ１ｎでかかるｚを計算し、及び、全ての１について｜ｃｉ｜≦ｎ／２及び｜ｘｉ｜≦φ１ｎを仮定して、
【数８１】
2020515928.tif 000083
という条件で、かかるＳを計算する。さらにより一般には、仮定は、両側限界を含んでもよい（すなわち、疑似剰余ｖについて−θＬｎ＜ｖ＜θＲｎという種類の限界）。当業者は、問題なく、以下の記述を適用してこれらのより一般的な条件を当てはめるであろう。方法は、同一に維持され、単に、例えば、定数を含む間隔の正確な形式、及び方法が動作するように保証さされることができる必要な条件が適用される必要がある。簡単のために、私たちは、記載を仮定の最も単純な形式に制限する。
【０１１７】
仮定Ａ（ｍ，Ｂ１，φ１，φ１）が与えられて、適切な法Ｎ及びＭｏｎｔｇｏｍｅｒｙ定数Ｍについて、Ｍｏｎｔｇｏｍｅｒｙ定数Ｍ及びＭｏｎｔｇｏｍｅｒｙ簡約Ｒ（Ｎ，Ｍ）を用いてＮを法とする（Ｍｏｎｔｇｏｍｅｒｙ）乗算
【数８２】
2020515928.tif 000084
を実行する、私たちのアルゴリズムを記述する。先ず、左の（Ｇ）ＲＮＳ    Ｍ１，・・・，Ｍｋ、右の（Ｇ）ＲＮＳ  Ｍｋ＋１，・・・，Ｍｋ＋ｌ、及び冗長な法Ｍ０を選択する。（後に、ｋ及びｌが上側の限界を満たす必要があることがわかるであろう。）ここで、
・１，・・・，ｋ＋ｌについて、ｇｃｄ（Ｍｓ，ｍ）＝１且つＭｓ≦Ｂ１、
・ｉ＝１，・・・，ｋ及びｊ＝ｋ＋１，・・・，ｋ＋ｌについて、ｇｃｄ（Ｍｉ，Ｍｊ）＝１、
である法をとる。
・ｓ＝１，・・・，ｋ＋ｌについてｇｃｄ（Ｍ０，Ｍｓ）＝１であることを必要がある。また、Ｍ０は、十分の大きい必要がある。例えば、Ｍ０≧ｌφ１（仮定の他の形式について、この下側の限界が適用される必要あることもある）。さらに、剰余の法Ｍ０を法とする演算が正確になされることできる、すなわち、全ての剰余の法Ｍ０が間隔［０，Ｍ０）に含まれる（又は、大きさＭ０の他の間隔）。例えば、これらのより小さい法を法とする演算で、剰余の法Ｍ０は、より小さい法Ｍ０ｓの積であることができ、したがってＭ０を法とする演算は、正確である。
【０１１８】
Ｍ＝ｌｃｍ（Ｍ１，・・・，Ｍｋ）；Ｍ’＝ｌｃｍ（Ｍｋ＋１，・・・，Ｍｋ＋ｌ）
を定義して、Ｍ及びＭ’は、それぞれ、左と右のＲＮＲＳのダイナミックレンジである。基底拡張について、ｓ＝１，・・・，ｋ＋ｌについて０≦Ｌｓ＜Ｍｓである、全てのｓについてｖ≡ｖｓ  ｍｏｄ  Ｍｓである任意の整数ｖについて
【数８３】
2020515928.tif 000085
である（左のＧＮＲＳについて）定数Ｌ１，・・・，Ｌｋ及び（右のＧＲＮＳについて）Ｌｋ＋１，・・・，Ｌｋ＋ｌの存在に依拠する。
【０１１９】
かかる定数Ｌｓの存在は、論文（Ｏｒｅ−Ｔｈｅ  Ｇｅｎｅｒａｌ  Ｃｈｉｎｅｓｅ  Ｒｅｍａｉｎｄｅｒ  Ｔｈｅｒｏｒｅｍ）からの結果によって保証される。左と右のＧＲＮＳが実際に両ＲＮＳであるなら（すなわち、法が実際に互いに素であるなら）、Ｌｓは、ｉ＝１，・・・，ｋ及びｊ＝ｋ＋１，・・・，ｋ＋ｌについて、
Ｌｉ≡（Ｍ／Ｍ１）−１  ｍｏｄ  Ｍｉ、  Ｌｊ＝（Ｍ’／Ｍｊ）−１  ｍｏｄ  Ｍｊ
で、Ｍｓを法として一意に決定される。この最後の状態はＧＲＮＳについて一般には保証されることはできないことに注意されたい。
【０１２０】
次に、０＜ε＜１でεを選択する。法Ｎを、ｇｃｄ（Ｎ，Ｍ）＝１及びＮ≦Ｂを満たす正の整数とする。ここで、Ｕ＝ｋφ１でＢ＝ε（１−ε）Ｍ／Ｕである。φ＝Ｕ／ε及びφ＝φＮ／＋Ｕ≒Ｕ＋１−εとする。例えばＭ’≧（１−ε）Ｍ）とすることによって、φＮ≦Ｍ’を確実にする。（Ｂを最大化したい場合、ε＝１／２とすべきあり、後にε＜１／２とする他の理由があり得ることがわかるであろう。）またさらに、δ＿＝ｍａｘｉ≦ｋ＜ｊＭｉ／Ｍｊ、δ＋＝ｍａｘｉ≦ｋ＜ｊＭｊ／Ｍｉ、及びδ０＝ｍａｘｉ≦ｋＭ０／Ｍｉを設定する。（δ＿≒δ＋≒１及びδ０≒０であることに注意されたい。）次に、また、
【数８４】
2020515928.tif 000086
及び
【数８５】
2020515928.tif 000087
であることを要求する。（上記表現は、“一般的な”拡張限界に適用され、他の種類の拡張限界については、それらが適用されなければならないこともある。）
【０１２１】
今度は、仮定Ａ（Ｍ，Ｂ，φ，φ）が適用されることが求められる。この要求を表すアルゴリズムは、次のようなものである。先ず、ｓ＝１，・・・，ｋ＋ｌについて定数Ｈｓ（入力／出力  ｘ、ｙ、ｚの表現に用いられた）及びＫｓ（Ｍｏｎｔｇｏｍｅｒｙ簡約への入力ｈｓの表現に用いられた）を選択する。Ｈｓ及びＫｓはＭｓと互いに素であることが求められる。Ｈ０＝Ｋ０＝１を設定する。またさらに、アルゴリズムを最適化するために用いる、全てのｉについてＳｉとＭｉが互いに素で（小さい）定数Ｓ１，・・・，Ｓｋを選択する。例えば、ｓ＝１，・・・，ｋ＋ｌについてＨｓ＝Ｋｓ＝ｍ−１とすることができるので、全ての剰余は、Ｍｏｎｔｇｏｍｅｒｙ表現であり、ｉ＝１，・・・，ｋについてＳｉ＝１である。この選択を用いて、以下の方法は、前の１つに一致する。しかし、他の選択は、以下に説明されるように、より有利であることもある。次に、定数
【数８６】
2020515928.tif 000088
を予め計算する。
【０１２２】
ｘ及びｙが与えられて、それぞれ、０≦α０，β０＜Ｍ０で（又は、例えば、｜α０｜，｜β０｜≦Ｍ０／２で）で及び０≦αｓ，βｓ＜φ１Ｍｓ（又は、例えば、｜α０｜，｜β０｜≦φ１Ｍｓ）で、（α０，α１，・・・，αｋ＋ｌ）及び（β０，β１，・・・，βｋ＋ｌ）と表現されるので、ｓ＝０，１，・・・，ｋ＋ｌについてｘ≡αｓＨｓ  ｍｏｄ  Ｍｓ及びｙ≡βｓＨｓ  ｍｏｄ  Ｍｓであり、ｈ＝ｘｙでｚ＝Ｒ（Ｎ，Ｍ）（ｈ）として
【数８７】
2020515928.tif 000089
を計算する。先ず、
【数８８】
2020515928.tif 000090
を行う。次に、ｈ＝ｘｙは、定数
【数８９】
2020515928.tif 000091
、及び
【数９０】
2020515928.tif 000092
でｓ＝１，・・・，ｋ＋ｌについてχｓによって表現される。すなわち、ｓ＝１，・・・，ｋ＋ｌについて
【数９１】
2020515928.tif 000093
である。
【０１２３】
次に、ｈが、定数Ｋ１，・・・，Ｋｋ＋ｌについて疑似剰余ｘ０，・・・，ｘｋ＋ｌによって表現されると仮定するので、ｓ＝１，・・・，ｋ＋ｌについてｈ≡Ｋｓｘｓ  ｍｏｄ  Ｍｓ且つ及び
【数９２】
2020515928.tif 000094
である。ｚ＝Ｒ（Ｎ，Ｍ）（ｈ）を計算するために、次のステップを行う。
【数９３】
2020515928.tif 000095
今度は、（ξ０，ξ１，・・・，ξｋ＋ｌ）によって表現された、すなわち、それに対しｓ＝０，１，・・・，ｋ＋ｌについてｚ≡ξｓＨｓ  ｍｏｄ  Ｍｓである、数ｚが、要求される拡張限界をｘ，ｙ，ｈが満たすという条件で、ｚが拡張限界を満たしながら、
【数９４】
2020515928.tif 000096
を満たす。
【０１２４】
所見１．１  全てのＭｓを法とする演算が正確なら、Ｍｏｎｔｇｏｍｅｒｙ定数をｍ＝１にとることができる。この場合、
【数９５】
2020515928.tif 000097
をとることができるので、上述のアルゴリズムのステップ３及び６は、Ｍｏｎｔｇｏｍｅｒｙ簡約ステップを抜かすことによって簡単化されることができる。
【０１２５】
所見１．２  ある特別な選択をすることは、有利であることがある。
・ｓ＝１，・・・，ｌについて
【数９６】
2020515928.tif 000098
を選択するなら、Ｅｋ＋ｓ＝ｍであり、このために、全てのｓ＝１，・・・，ｌについてηｋ＋ｓ≡ｘｋ＋ｓ  ｍｏｄ  Ｍｋ＋ｓであり、結果として、上述のアルゴリズムのステップを抜かすことができる。所見１．３を参照されたい。
・同様に、
【数９７】
2020515928.tif 000099
を選択するなら、Ｃｉ＝ｍであり、このために、μｉ≡χｉであり、全てのｉ＝１，・・・，ｋについてこれが当てはまるなら、上記アルゴリズムのステップ２を飛ばすことができる。所見１．３を参照されたい。完全なＭｏｎｔｇｏｍｅｒｙ乗算アルゴリズムにおいて、ステップ１の後
【数９８】
2020515928.tif 000100
であり、結果として、簡単化のために、
【数９９】
2020515928.tif 000101
が必要とされる。その選択は、ＬｉとＭｉが互いに素である場合及び
【数１００】
2020515928.tif 000102
が２乗モジュロＭｉである場合のみ利用可能である。ｕ上に良いアプリオリな限界を得るために小さなＳｉが必要となる。１つの魅力的な選択は、Ｍｉ≡３  ｍｏｄ  ４でＭｉを素数にとることであるので、−１は、非２乗モジュロＭｉであり（最上のレベルの法のそのような制限はほとんどない）、その場合、Ｓｉ＝１又はＳｉ＝−１を選択して
【数１０１】
2020515928.tif 000103
を２乗にすることができる。これらの最後の選択は、対称拡張限界の使用と組み合わせて特別な魅力であり、実際その場合ｕ上の上側の限界は、Ｓｉの選択によって影響を受けないことになる。
・ステップ２及び４を飛ばすことに成功したなら、
【数１０２】
2020515928.tif 000104
についての全体のアルゴリズムは、きちんと行われることができることに注意されたい。一般に、アルゴリズムのほとんどは、χｉと異なるμｉ及びξｋ＋ｊと異なるηｋ＋ｊを保存する余分なレジスタを必要とすることを除いて、きちんと行われることができる。
【０１２６】
所見１．３  μｉ≡χｉを用いてステップ２を飛ばしステップ３においてμｉをχｉによって置換するなら、結果として生ずるｓｋ＋ｊは、より大きくなることもある。理由は、χｉがφ１Ｍｉによって限界内にとどめられている間μｉがφ１Ｍｉによって限界内にとどめられることである。限界をより詳細に検討する。前に、
Ｕ＝φ１ｋ、
を記述し、
Ｂ＝ε（１−ε）Ｍ／Ｕ）、φ＝Ｕ／ε、φ≒Ｕ＋１−ε≒Ｕ
である。
【０１２７】
最適に設計された系において、ε≒１／２であるので、φ≒２φである。下側の系が同様に設計されるなら、最適に設計された系においてε１＝１／２で、ある定数Ｕ１について、
Ｂ１＝ε１（１−ε１）ｍ／Ｕ１、φ＝Ｕ１／ε１、φ１≒Ｕ１＋１−ε１≒Ｕ１
である。おおよそ
【数１０３】
2020515928.tif 000105
であるときあるＭｉを法とするμｉのｋ項で重み付けされた和を扱うことができ、おおよそ
【数１０４】
2020515928.tif 000106
であり、ここでＵ１がε１に依存しないとき、あるＭｉを法とするχｉのｋ項で重み付けされた和を扱うことができることになる。したがって、ε１のより小さい値を選択することによって、例えば、ε１＝１／２に代えて、ε１＝１／４を用いて、扱うことができる（より大きい）項の数を増加させることができる。しかし、それは、Ｂ１の値が係数３／４によって減少することを意味する。ｌｏｇ２（３）≒１．６であるから、最上のレベルにおける全ての法Ｍｓは、約０．４ビット小さくなるであろうことがわかる。実施例にあるようなｋ＝ｌ≒３０については、これは、約１２ビット少ない値Ｍの結果となることになる。よって、このようにして約１２ビット少ない法Ｎの値を扱うことができ、そうでなければｋを１増加させなければならないことになる。下側のレベルにおける系を微調整することによって、最上のレベルにおける性能を最適化することができる。最上のレベルにおいて、Ｕ＝φ１ｋによって限界Ｕ＝φ１ｋを置換しなければならず、これはまた上側の限界Ｂを小さくするが、ε≒１／２である場合概ね係数２にすぎないことに注意されたい。
【０１２８】
同様の所見が、ステップ５及び６においてηｊをξｊによって置換することによってステップ４を飛ばしたいときに、当てはまる。実際、両方の置換は、同様の仕方を要求する。
【０１２９】
定数によってＭｏｎｔｇｏｍｅｒｙ乗算を実行するとき、χｋ＋ｊ及びηｋ＋ｌは、両方とも同一の限界φ１Ｍｋ＋ｌによって上側の限界内にとどめられることになり、その場合、改良は、更なる適応なしに行われることができる。同様の所見が、方法の第１の部分における可能な改良に当てはまる。
【０１３０】
方法を完了させるために、全てのｉについて０≦Ｓ＜φ２Ｎ２且つ０≦ｃ（ｉ）＜Ｎ且つ０≦ｘ（ｉ）＜φＮのとき、重み付けされた和Ｓ＝ｃ（１）ｘ（１）＋・・・＋ｃ（ｔ）ｘ（ｔ）をどのように実行するかを説明する。私たちの限界は、数ｈ＝ｘｙが完全なＲＮＲＳにおいて表現されることができ、すなわち、φ２Ｎ２≦ＭＭ’である。結果として、重み付けされた和Ｓも完全なＧＮＲＳに表現されることができる。したがって、完全なＧＮＲＳにおいてＳの剰余（の表現）を計算すること、すなわち、全てのｓについて、ある定数Ｋｓについて、
【数１０５】
2020515928.tif 000107
を計算することで、十分である。全てのｓについて、剰余
【数１０６】
2020515928.tif 000108
が、
【数１０７】
2020515928.tif 000109
である疑似剰余
【数１０８】
2020515928.tif 000110
によって表現されると仮定する。次に、全てのｉについて、
【数１０９】
2020515928.tif 000111
で
【数１１０】
2020515928.tif 000112
を計算すべきである。この計算を行う１つの方法は、
【数１１１】
2020515928.tif 000113
を設定することであり、次に、
【数１１２】
2020515928.tif 000114
を計算するので、全てのｓについて
【数１１３】
2020515928.tif 000115
である。私たちの仮定Ａ（ｍ，Ｂ１，φ１，φ１）によって、全てのｓについて
【数１１４】
2020515928.tif 000116
であることを保証することができる限り、これは、動作する。一方、Ｔｓ上の上側の限界が当てはまることを保証することができないなら、定数
【数１１５】
2020515928.tif 000117
を用いることができ、形式
【数１１６】
2020515928.tif 000118
においてＴｓを計算することができる。ここで、各Ｔｓ，ｊは形式
【数１１７】
2020515928.tif 000119
である（すなわち、“簡約木（ｒｅｄｕｃｔｉｏｎ  ｔｒｅｅ）”を構築する）。当業者は、これらのアイデアをより一般的な形式に適用することが容易にできるであろう。上述のアルゴリズムにおいて（ただ１つ、後置されて、簡約で）説明されたように、方法は、そこでは全てのｓについて
【数１１８】
2020515928.tif 000120
を単に要求することで十分である、２レベルの系において動作するであろうことを、注記する。
【０１３１】
以下に、モジュラ簡約の第３の変形が、Ｂａｒｒｅｔｔ乗算に基づいて、述べられる。整数ｈのモジュラ簡約｜ｈ｜Ｎは、
【数１１９】
2020515928.tif 000121
として得られることができる。
【０１３２】
Ｂａｒｒｅｔｔ乗算は、商
【数１２０】
2020515928.tif 000122
を推定しようとする、Ｂａｒｒｅｔｔ簡約と呼ばれる操作を含む。その最も一般的な形式において、Ｂａｒｒｅｔｔ簡約は、２つの追加の正の整数パラメータＭ、Ｍ’を含み、
【数１２１】
2020515928.tif 000123
と定義され、ここで、
【数１２２】
2020515928.tif 000124
は、予め計算されることができる定数である。Ｂａｒｒｅｔｔ簡約の有用性は、次の所見に基づく。Ｂ（Ｎ，Ｍ，Ｍ’）（ｈ）≡ｈｍｏｄＮ且つ｜ｈ｜Ｎ≦Ｂ（Ｎ，Ｍ，Ｍ’）（ｈ）≦｜ｈ｜Ｎ＋ΔｈＮとし、ここで、
【数１２３】
2020515928.tif 000125
である。
【０１３３】
モジュラ乗算を行うＢａｒｒｅｔｔ簡約Ｂ（Ｎ，Ｍ，Ｍ’）は、次のアルゴリズムによってＲＮＳにおいて実行されることができる。
【数１２４】
2020515928.tif 000126
と記述して、ｃがＢａｒｒｅｔｔ乗算のＲＮＳ実行ｃ＝ａｂ−Ｂ（Ｎ，Ｍ，Ｍ’）≡ａｂ  ｍｏｄ  Ｎによって得られた疑似剰余であることを表す。繰り返すと、ダイナミックレンジＭ＝Ｍ１・・・ＭＫをもつ基底の法Ｍｉ，・・・，ＭＫによって形成された基底のＲＮＳをもつ拡張されたＲＮＳ、及びダイナミックレンジＭ’＝ＭＫ＋１・・・ＭＫ＋Ｌをもつ拡張法ＭＫ＋１，・・・，ＭＫ＋Ｌによって形成された拡張ＲＮＳをもつ、拡張されたＲＮＳが用いられる。
１．ｈ＝ｘｙ、ｓ＝０，・・・，Ｋ＋Ｌについて
【数１２５】
2020515928.tif 000127
を介して行われる、
２．
【数１２６】
2020515928.tif 000128
、ｉ＝１，・・・，Ｋについて
【数１２７】
2020515928.tif 000129
を介して行われる、今
【数１２８】
2020515928.tif 000130
であり、ｐ＝（ｈ−ｕ）／Ｍは整数である、
３．ｊ＝Ｋ＋１，・・・，Ｋ＋Ｌについて
【数１２９】
2020515928.tif 000131
、
４．基底拡張を用いてｉ＝１，・・・，Ｋについてｐｉを見つける、
５．
【数１３０】
2020515928.tif 000132
、ｊ＝０について及びｊ＝Ｋ＋１，・・・，Ｋ＋Ｌについて
【数１３１】
2020515928.tif 000133
を介して行われる、今
【数１３２】
2020515928.tif 000134
であり及びｑ＝（ｐＣ−ｖ）／Ｍ’＝（Ｃ（ｈ−ｕ／Ｍ−ｖ）／Ｍ’は整数である、
６．
【数１３３】
2020515928.tif 000135
であり、それ故にｚ＝ｈ−ｑＮに対しｉ＝１，・・・，Ｋについて
【数１３４】
2020515928.tif 000136
である、
７．基底拡張を用いてｊ＝Ｋ＋１，・・・，Ｋ＋Ｌについてｚｊを見つける。
【０１３４】
Ｍｏｎｔｇｏｍｅｒｙアルゴリズムに匹敵する多数の法が必要であるが、この方法は、いくつかの余分な操作（１つに代えて２つの基底拡張）を必要とする。正しくアルゴリズムを動作させることを保証するために当てはまる必要がある限界は、今度は、導き出されることもできる。ＲＮＳを用いた１桁のＭｏｎｔｇｏｍｅｒｙ乗算アルゴリズムに適用されることができる同じ高速度化（同じ大きさのテーブル、後置の簡約、冗長な法の適切な選択）が、ここで適用され、同様の技術が適用されて要求される限界を導き出す。
【０１３５】
第４の実施例として、今度は、ＲＮＳを用いた桁ベースのＭｏｎｔｇｏｍｅｒｙ乗算アルゴリズムの概略を述べる。拡張係数φ１をもち、ダイナミックレンジＭ＝Ｍ１・・・ＭＫ及び冗長な法Ｍ０をもつＲＮＳ  Ｍ１，・・・，ＭＫを想定する。ここで、Ｍ≫ＢＳ及びＭＫ＝Ｂをとることができる。ＢＳｚ≡ｘｙ  ｍｏｄ  Ｎであるｚを計算するために、先ず、ｙを、概ねＢに関する形式で、ある拡張係数φ１について０≦ｅｔ＜φ１Ｂ及び０≦δ＜φ１で
【数１３５】
2020515928.tif 000137
として記述する。次に、次のアルゴリズムを走らせる。
１．ｚ（−１）＝０、
２．ｔ＝０，・・・，ｓ−１について、
ｈ（ｔ）＝ｚ（ｔ−１）＋ｘｅｔ
及び
ｚ（ｔ）＝Ｒ（Ｎ，Ｂ）（ｈ（ｔ））＝（ｈ（ｔ）＋ｕｔＮ）／Ｂ
を設定し、ここで
【数１３６】
2020515928.tif 000138
である。
３．ｚ’＝ｚ（Ｓ−１）、
４．ｚ＝ｚ’−ｘδ。
【０１３６】
ｕ＝ｕ０＋ｕ１Ｂ＋・・・＋ｕｓ−１ｕｓ−１と記述して、ＢＳｚ’＝ｘｅ＋ｕＮ及びＢＳｚ＝ｘｙ＋ｕＮであることは、容易に示される。全てのｉ＝０；１，・・・，Ｋについて疑似剰余
【数１３７】
2020515928.tif 000139
で、ｘについて完全なＲＮＳ表現ｘ＝（ｘ０；ｘ１，・・・，ｘＫ）があるので、ｙについて同様である。ＭＫ＝Ｂであるから、ＲＮＳを用いてｙの“桁”ｅｔ及び拡張係数φ１を用いて疑似剰余
【数１３８】
2020515928.tif 000140
を計算することができる。それ故に、ｕ＜φ１ＢＳであり、よって、ｘ，ｙ＜φＮなら、
【数１３９】
2020515928.tif 000141
であるという条件で、再びｚ’＜φＮであり、φ＝φ１／εを設定し、限界
Ｎ≦ε（１−ε）ＢＳ／φ１
が必要であることがわかる。
【０１３７】
さらに、全ての中間の結果ｚ（ｔ）が拡張限界ｚ（ｔ）＜θＮを満たすようにするために、
θ≧（φ＋１）φ１Ｂ／（Ｂ−１）
であることで十分であることが容易にわかる。
【０１３８】
十分に大きなダイナミックレンジをもつ限り、この方法は、拡張係数φ内で正しい結果を与える。
【０１３９】
上述で、この方法用いて多層ＲＮＳ系を構築するために十分であるはずである。
【０１４０】
本発明の有利な実施形態は、上述したように、２０４８ビットの法Ｎを用いたモジュラ乗算について最適化された、第２のモジュラ乗算法（Ｍｏｎｔｇｏｍｅｒｙをベースとした）に基づく２層の多層ＲＮＳである。そのような系において、ｋ≒ｌで底の０層の法ｍ０；ｍｉ，・・・，ｍｋ＋ｌを用い、及びｋ≒Ｌで最上の第１の層の法Ｍ０；Ｍｉ，・・・，ＭＫ＋Ｌを用い、及びモジュラ加算についての及びモジュラ乗算についてのテーブルルックアップを用いて実行される底の法ｍｉを法とする演算を用いて、Ｎを法とするモジュラ乗算のための多くのテーブルルックアップは、約２４ｋ２＋８Ｋ２ｋのテーブルルックアップをとる。さらに、大きくとも２ｔの大きさの底の法を用いて及び大きさ２ｂのＮを用いて、
【数１４０】
2020515928.tif 000142
及びＫ≒ｂ／（ｔｋ）をとることによってテーブルルックアップの数が最小化され、概ね
【数１４１】
2020515928.tif 000143
のテーブルルックアップとなる。ｂ＝２０４８及びｔ＝８をとることは、ｋ≒９及びＫ≒２８を与える。好ましい実施形態では、ｋ＝ｌ＝９及びＫ＝Ｌ＝３２とし、これは、上述した推定よりもわずかによりよいことがわかる。
【０１４１】
小さい法について、素数
１９１、１９３、１９７、１９９、２１１、２２３、２２７、２２９、２３３、２３９、２４１、２５１
をとり、これらは、２５６よりも小さい最大の素数であり、合成数
２５６＝２８、２５３＝１１・２３、２４９＝３・８３、２４７＝１３・１９、２３５＝５・４７、２１７＝７・３１は、ｍ＞１３でｐｉｍの素数からの最大の数であり、大きくとも２５６の大きさの互いに素である１８個の数の何れのかのリストについての最大の到達可能な積を生成する。２５５＝３・５・１７は、３及び５の両方について最悪の選択であり、同様に２４５＝５・７２は、５及び７の両方について最悪の選択であり、２、１１及び１３についての選択は、明らかに最適であることに注意されたい。結果として、小さい法は、少なくとも１９１の大きさの全ての素数、更に素数２、３、５、７、１１、１３、１９、２３、３１、４７、８３を、素数係数として含むことに注意されたい。冗長な法についてもそうなので、ｍ０＝１７＞ｋ＝９＝ｌをとることができる。
【０１４２】
ε１＝ｋ／（２ｋ＋１）を用いる。実際に、ε１＝１／２を用いることでも動作する。次に、ｍが最大でｍ’≧（１−ε１）ｍであるこれらの１８個の法の最良の分割は、
ｍ＝２０９７０６５９８３０１３２５４３０６５６０、ｍ’＝１１５３３８８２１６５６００３５７１５７２１で、
基底の法として、
２５６、２５１、２４９、２４７、２４１、２３９、２３５、１９９、１９７
をとり、拡張の法として、
１９１、１９３、２１１、２１７、２２３、２２７、２２９、２３３、２５３
をとることがわかる。
【０１４３】
今度は、最上の層についての大きい法の選択は、次のようなものである。ε２＝１／２をとると、Ｍｓについて最大の可能な上側の限界に至るので、
Ｍｓ≦Ｍｍａｘ＝ε（１−ε１）ｍ／ｋ＝５７６６９３１４５３２８６４４９３４３０
である大きい法をとる。
【０１４４】
ｂ＝２０４８ビットまで有するＮを法とするＲＳＡを扱う系を構築したいので、
Ｎｍｉｎ＝２２０４８−１≦ε２（１−ε２）Ｍ／Ｕ１
であることも要求され、Ｍｍａｘを下回るＫ＝３２素数をとる必要があり、Ｍを十分に大きくするために、最も小さいものは
５７６６９３１４５３２８６４４９２３７３
である。次に、Ｍ’≧（１−ε２）Ｎとするために、素数
５７６６９３１４５３２８６４４９１１８９
で始まる他のＬ＝３２素数が必要である。
【０１４５】
結果として生じる多層ＲＮＳが、Ｓａｇｅ及びＣ／Ｃ＋＋の両方で、コンピュータプログラムで実行された。Ｃ＋＋プログラムは、２０４８ビットモジュラ乗算について約１３７０００のテーブルルックアップを用い、５００のＭｏｎｔｇｏｍｅｒｙ乗算を計算するのに普通の３ＧＨｚのラップトップ上で０．５秒よりも少なくかかった。
【０１４６】
上述したように、実施形態は、例えば、ＲＳＡやＤｉｆｆｉｅ−Ｈｅｌｌｍａｎにおいて、また及び特にホワイトボックスコンテストにおいて要求されるように、べき乗を行うのにたいへん適している。同様に、本発明は、楕円曲線ＤＳＡ（Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ａｌｇｏｒｉｔｈｍ）などの楕円曲線暗号において用いられて、たいへん大きい素数ｐを法とする要求される演算を実行することができる。本方法は、ＬＲＡ（ｌｅａｋ−ｒｅｓｉｓｔａｎｔ  ａｒｉｔｈｍｅｔｉｃ）を実行するのにたいへん適している。単にアルゴリズムにおける定数のいくつかを変更することによってより高いレベルにおける法を容易に変更することができる。大きな法の大きさにおいて（例えば、６６ビット程度）、法の選択に利用可能なたいへん多くの素数があることに注意されたい。他の応用は、大きな整数の演算が求められ、共通のＲＮＳがあまりにも多くの法又はあまりにも大きな法をもつことになる状況である。
【０１４７】
さまざまな実施形態において、入力インタフェースは、さまざまな代替から選択されてもよい。例えば、入力インタフェースは、ローカル又はワイドエリアネットワーク、例えばインターネット、に対するネットワークインターフェース、内部又は外部保存装置に対するストレージインターフェース、キーボードなどであり得る。
【０１４８】
典型的には、装置２００は、装置２００に保存された適切なソフトウェアを実行するマイクロプロセッサ（分離して示されていない）を含み、例えば、ソフトウェアは、ダウンロードされていてもよく及び／又は対応するメモリ、例えばＲＡＭなどの揮発性メモリ又はフラッシュメモリなどの不揮発性メモリ（分離して示されていない）に保存されていてもよい。或いは、装置２００は、全体として又は部分的に、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）のようなプログラマブルロジックに実装されてもよい。装置２００は、全体として又は部分的に、いわゆる特定用途向け集積回路（ＡＳＩＣ）、すなわち、それらの特定の用途用にカスタマイズされた集積回路（ＩＣ）として、実装されてもよい。例えば、回路は、例えば、Ｖｅｒｉｌｏｇ、ＶＨＤＬその他などのハードウェア記述言語用いて、ＣＭＯＳで実装されてもよい。
【０１４９】
プロセッサ回路は、例えばマルチプルサブプロセッサのような、分散様式で実装されてもよい。保存装置は、電子メモリ、磁気メモリその他であってもよい。保存装置の一部は、不揮発性であってもよく、又は揮発性であってもよい。保存装置の一部は、読み取り専用であってもよい。
【０１５０】
図４は、計算方法４００の一実施形態の例を模式的に示す。
【０１５１】
方法は、整数が多層ＲＮＳフォーマットで保存される保存段階４１０を含む。例えば、整数が操作される計算アプリケーション、例えば、ＲＳＡ暗号化又はシグネチャアプリケーション（ｓｉｇｎａｔｕｒｅ  ａｐｐｌｉｃａｔｉｏｎ）などから得られることができる。数は、また、他のフォーマットから、例えば、基数フォーマットから、ＲＮＳフォーマットへ変換されてもよい。
【０１５２】
方法は、さらに、第１の整数と第２の整数の積が計算される計算段階４２０を含む。計算段階は、例えば、上述したように、少なくとも下側乗算部分と上側乗算部分とを含む。
【０１５３】
方法を実行する多くの異なる仕方が、当業者に明らかであるように、可能である。例えば、ステップの順序が変更されてもよく、又はいくつかのステップが並列に実行されてもよい。さらに、ステップの間に他の方法ステップが挿入されてもよい。挿入されたステップは、本明細書に記載されたような方法の改良を表すこともあり、又は方法に関係のないこともある。
【０１５４】
本発明による方法は、プロセッサシステムに方法４００を実行させるための命令を含む、ソフトウェアを用いて実行されてもよい。ソフトウェアは、システムの特定の下位構成要素によってとられるそれらのステップのみを含んでいてもよい。ソフトウェアは、ハードディスク、フロッピー、メモリ、光学ディスクなどの、適切な保存媒体に保存されてもよい。ソフトウェアは、有線、又は無線に沿った信号として、又は、データネットワーク、例えばインターネットを用いて、送られてもよい。ソフトウェアは、ダウンロードのために及び／又はサーバ上に遠隔使用のために利用できるようにされてもよい。本発明による方法は、プログラマブルロジック、例えば、フィールドプログラマブルゲート（ＦＰＧＡ）を構成して方法を実行するように設けられたビット配列を用いて実行されてもよい。
【０１５５】
本発明はまた、本発明を実施するために適用させられた、コンピュータプログラム、特にキャリア上の又は内のコンピュータプログラムにも適用される。プログラムは、ソースコード、オブジェクトコード、コード中間ソース、及び部分的にコンパイルされた形態などのオブジェクトコード、又は本発明による方法の実施における使用のための適切な何れの他の形態であってもよい。コンピュータプログラム製品に関連する実施形態は、述べられた方法のうちの少なくとも１つの処理ステップのそれぞれに対応するコンピュータ実行可能な命令を含む。これらの命令は、サブルーチンに細分されてもよく及び／又は静的に又は動的にリンクされてもよい１つ以上のファイルに保存されてもよい。コンピュータプログラム製品に関連する他の実施形態は、述べられたシステム及び／又は製品のうちの少なくとも１つの手段のそれぞれに対応するコンピュータ実行可能な命令を含む。
【０１５６】
図５ａは、実施形態に従う、プロセッサシステムに計算方法を実行させるための命令を含むコンピュータプログラム１０２０を含む書き込み可能な部分を有するコンピュータ可読媒体１０００を示す。コンピュータプログラム１０２０は、物理的な記号として又はコンピュータ可読媒体の磁化の手段によってコンピュータ可読媒体１０００に埋め込まれていてもよい。しかし、何れの他の適切な実施形態もまた考えられる。またさらに、コンピュータ可読媒体１０００はここでは光ディスクとして示されているけれども、コンピュータ可読媒体１０００は、ハードディスク、固体メモリ、フラッシュメモリなどの、何れの適切なコンピュータ可読媒体であってもよく、レコーダブルであっても又はレコーダブルでなくてもよい。コンピュータプログラム１０２０は、プロセッサシステムに上記計算方法を実行させる命令を含む。
【０１５７】
図５ｂは、一実施形態に従うプロセッサシステム１１４０の概略表現である。プロセッサシステムは、１つ以上の集積回路１１１０を含む。１つ以上の集積回路１１１０のアーキテクチャが、図５ｂに模式的に示されている。回路１１１０は、コンピュータプログラムコンポーネントを走らせて実施形態に従う方法を実行する及び／又はそのモジュール若しくはユニットを実装するための、プロセッシングユニット１１２０、例えばＣＰＵを含む。回路１１１０は、プログラミングコード、データなどを保存するためのメモリ１１２２を含む。メモリ１１２２の一部が、読み出し専用であってもよい。回路１１１０は、通信要素１１２６、例えば、アンテナ、コネクタ又は両方などを含んでいてもよい。回路１１１０は、方法に定義された処理の一部又は全てを実行するための専用の集積回路１１２４を含んでいてもよい。プロセッサ１１２０、メモリ１１２２、専用ＩＣ１１２４及び通信要素１１２６は、相互接続器１１３０、例えばバスを介して互いに接続されていてもよい。プロセッサシステム１１１０は、アンテナ及び／又はコネクタを用いて、接触及び／又は非接触通信用に設けられてもよい。
【０１５８】
例えば、一実施形態では、計算装置は、プロセッサ回路及びメモリを含み、プロセッサはメモリ回路に保存されたソフトウェアを実行するように設けられていてもよい。例えば、プロセッサ回路は、インテル  Ｃｏｒｅ  ｉ７プロセッサ、ＡＲＭ  Ｃｏｒｔｅｘ−７８などであってもよい。メモリ回路は、ＲＯＭ回路、又は不揮発性メモリ、例えばフラッシュメモリであってもよい。メモリ回路は、揮発性メモリ、例えばＳＲＡＭであってもよい。後者の場合、照合装置は、ソフトウェアを提供するために設けられた、不揮発性ソフトウェアインタフェース、例えば、ハードドライブ、ネットワークインターフェースなどを含んでいてもよい。
【０１５９】
次の項は、請求項ではないが、予想され、非限定的である。出願人は、新しい請求項が、本応用の又はそれから導き出される更なる何れかの応用の実行の間に、かかる項及び／又はかかる項の組合せ及び／又は明細書若しくは請求項からとられた特徴へ、正式に表されることもあることを、ここに注記する。
【０１６０】
項１．整数の積を計算するように設けられた電子計算装置（１００、２００）であって、電子計算装置は、
多層の剰余数系（ＲＮＳ）表現で整数（２１０、２２０）を保存する保存装置（１１０）であって、前記多層ＲＮＳ表現は、少なくとも上側の層のＲＮＳ及び下側の層のＲＮＳを有し、前記上側の層のＲＮＳは、複数の上側の法の系列（Ｍｉ）についての剰余数系であり、前記下側の層のＲＮＳは、複数の下側の法の系列（ｍｉ）についての剰余数系であり、整数（ｘ）が、前記上側の法の系列（Ｍｉ）を法とする複数の上側の剰余の系列（
【数１４２】
2020515928.tif 000144
）（２１１、２２１）によって前記保存装置内に表現されており、少なくとも１つの特定の上側の法（Ｍｊ）についての上側の剰余（ｘｊ；２１０．２、２２０．２）は、前記下側の法の系列（ｍｉ）を法とする前記上側の剰余（ｘｊ）の複数の下側の剰余の系列（
【数１４３】
2020515928.tif 000145
）（２１２、２２２）によって前記保存装置内に更に表現されており、前記複数の下側の法（ｍｉ）のうちの少なくとも１つは、前記複数の上側の法（Ｍｊ）の法を分割しない、保存装置（１１０）と、
−  第１の整数（ｘ）（２１０）と第２の整数（ｙ）（２２０）との積を計算するプロセッサ回路（１２０）であって、前記第１の整数（ｘ）と前記第２の整数（ｙ）とは、前記多層ＲＮＳ表現に従って前記保存装置内に保存されており、前記プロセッサは、少なくとも下側乗算ルーチン（１３１）と上側乗算ルーチン（１３２）とで構成されており、
−    前記下側乗算ルーチンは、前記上側の法（Ｍｊ）を法とする同一の上側の法（Ｍｊ）に対応する２つの更に表現された上側の剰余（ｘｊ、ｙｊ）の積を計算し、
−    前記上側乗算ルーチンは、前記第１の整数（ｘｉ）の上側の剰余と前記対応する法（Ｍｉ）を法とする前記第２の整数（ｙｉ）の対応する上側の剰余との成分に関する乗算によって前記第１の整数と前記第２の整数との積を計算し、前記上側乗算ルーチンは、更に表現されている前記上側の剰余を掛け合わせるように前記下側乗算ルーチンに求める、プロセッサ回路（１２０）とを含む、電子計算装置。
【０１６１】
項２．整数の積を計算する方法（４００）であって、
多層の剰余数系（ＲＮＳ）表現で整数（２１０、２２０）を保存することであって、前記多層ＲＮＳ表現は、少なくとも１つの上側の層のＲＮＳと下側の層のＲＮＳとを有し、前記上側の層のＲＮＳは複数の上側の法の系列（Ｍｉ）についての剰余数系であり、前記下側の層のＲＮＳは、複数の下側の法の系列（ｍｉ）についての剰余数系であり、整数（ｘ）が、前記上側の法（Ｍｉ）の系列を法とする複数の上側の剰余（
【数１４４】
2020515928.tif 000146
）（２１１、２２１）の系列によって前記保存装置に表現されており、少なくとも１つの特定の上側の法（Ｍｊ）についての上側の剰余（ｘｊ）（２１０．２、２２０．２）は、前記下側の法の系列（ｍｉ）を法とする前記上側の剰余（ｘｊ）の複数の下側の剰余の系列（
【数１４５】
2020515928.tif 000147
）によって前記保存装置に更に表現されており、前記複数の下側の法（ｍｉ）のうちの少なくとも１つは、前記複数の上側の法（Ｍｊ）の法を分割しない、保存することと、
−  第１の整数（ｘ）（２１０）と第２の整数（ｙ）（２２０）との積を計算すること（４２０）であって、前記第１の整数（ｘ）と前記第２の整数（ｙ）とは前記多層ＲＮＳ表現に従って前記保存装置に保存され、前記計算することは少なくとも下側乗算部分（４２４）と上側乗算部分（４２２）とを含み、
−    前記下側乗算部分は、前記上側の法（Ｍｊ）を法とする同一の上側の法（Ｍｊ）に対応する２つの更に表現された上側の剰余（ｘｊ、ｙｊ）の積を計算し（４２４）、
−    前記上側乗算部分は、前記第１の整数の上側の剰余（ｘｉ）と前記対応する法（Ｍｉ）を法とする前記第２の整数（ｙｉ）の対応する上側の剰余との積の成分に関する乗算によって前記第１の整数と前記第２の整数との積を計算し（４２２）、前記上側乗算ルーチンは、更に表現されている前記上側の剰余を掛け合わせるように前記下側乗算ルーチンに求める、計算することとを含む、方法。
【０１６２】
上述した実施形態は、本発明を限定するより表しており、当業者は、多くの代替の実施形態を作成することができるであろうことに、留意されたい。
【０１６３】
特許請求の範囲では、括弧内に記入された何れの参照番号も、請求項を限定するように解釈されるべきではない。動詞“ｃｏｍｐｒｉｓｅ”及びその活用形の使用は、請求項に述べられた要素又はステップ意外の存在を除外しない。要素の前の冠詞“ａ”又は“ａｎ”は、複数のその要素の存在を除外しない。本発明は、数個の異なる要素を含むハードウェアの手段によって、及び適切にプログラムされたコンピュータの手段によって、実行されてもよい。装置の請求項において、列挙された数個の手段、これらの手段のいくつかは、一つに及びハードウェアの同一のアイテムにまとめられてもよい。ある手段が互いに異なる請求項に記載されているという単なる事実は、これらの手段の組合せが用いられて利点となることはないということを表さない。
【０１６４】
請求項において、括弧内の参照番号は、例示する実施形態の図における参照符号又は実施形態の式を指し、したがって、請求項の明瞭性を増加させる。これら番号は、請求項を限定するように解釈されるべきではない。
【符号の説明】
【０１６５】
１００  電子計算装置
１１０  保存装置
１２０  プロセッサ回路
１３０  保存装置
１３１  下側乗算ルーチン
１３２  上側乗算ルーチン
１５０  より大きな計算装置
２００  電子計算装置
２１０、２２０  整数
２１０．１−２１０．３  上側の剰余
２１０．２．１−２１０．２．３  下側の剰余
２２０．１−２２０．３  上側の剰余
２２０．２．１−２２０．２．３  下側の剰余
２１１、２２１  複数の上側の剰余の系列
２１２、２２２  複数の下側の剰余の系列
２３０  保存装置
２４２  下側乗算ルーチン
２４４  上側乗算ルーチン
２４５  テーブル保存装置
３１０  整数
３１０．１−３１０．３  第１の層の剰余
３１０．２．１−３１０．２．３  第２の層の剰余
３１０．２．２．１  第３の層の剰余
３１１  複数の第１の層の剰余の系列
３１２  複数の第２の層の剰余の系列
３１３  複数の第３の層の剰余の系列
【図１】
2020515928.tif 000154
【図２ａ】
2020515928.tif 000155
【図２ｂ】
2020515928.tif 000156
【図３】
2020515928.tif 000157
【図４】
2020515928.tif 000158
【図５ａ】
2020515928.tif 000159
【図５ｂ】
2020515928.tif 000160
【国際調査報告】
2020515928.tif 000161
2020515928.tif 000162
2020515928.tif 000163