【手続補正書】
【提出日】平成23年3月8日(2011.3.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
整数の素数を判定するデータ処理システムであって、
前記整数の新たな表現を生成する再符号化ユニット、
複数の剰余演算操作を行うための剰余演算操作ユニット、
ループ制御ユニット、及び
入力整数の合成数又は素数を判定する判定ユニットを有し、
前記再符号化ユニットは、入力整数の複数のビットをスキャンし、前記スキャンされたビットにしたがって前記剰余演算操作ユニットによって演算される剰余演算操作を選択する、データ処理システム。
【請求項２】
前記剰余演算操作ユニットは剰余乗算ユニットを含む、請求１記載のデータ処理システム。
【請求項３】
前記剰余演算操作ユニットはモンゴメリー乗算ユニットである、請求項２記載のデータ処理システム。
【請求項４】
前記剰余演算操作ユニットは古典的な乗算ユニットである、請求項２記載のデータ処理システム。
【請求項５】
前記再符号化ユニットは、２ｗ（Ｗは正の整数）の表現形態に整数を再符号化する、請求項２記載のデータ処理システム。
【請求項６】
前記剰余演算操作ユニットは更に、左シフト回路、減算回路、右シフト回路、及び加算回路を有する、請求項２記載のデータ処理処システム。
【請求項７】
前記再符号化ユニットは、ＮＡＦの表現形態に整数を再符号化する、請求項６記載のデータ処理システム。
【請求項８】
前記再符号化ユニットは、ＦＡＮの表現形態に整数を再符号化する、請求項６記載のデータ処理システム。
【請求項９】
整数の素数を判定するためのデータ処理方法であって、コンピュータ装置を用いて実行される第１乃至第４処理を含み、
第１処理は、前記整数の複数ビットをスキャンする処理であり、
前記第２処理は、前記スキャンされたビットに従って少なくとも一つの剰余演算処理を選択する処理であり、
前記第３処理は選択された剰余演算処理を実行する処理であり、
前記第４処理は前記剰余演算処理の結果に基づいて前記整数の素数を決める処理である、データ処理方法。
【請求項１０】
前記スキャンされるビット数は予め決定され、
前記第３処理は、前記整数の全ビットに対して、剰余二乗演算と剰余乗算とを繰り返し行う処理を含む、請求項９記載のデータ処理方法。
【請求項１１】
前記剰余乗算の一つの乗算は２の累乗である、請求項１０記載のデータ処理方法。
【請求項１２】
前記スキャンされるビットは符号付きで表現され、
前記第３処理は、前記整数の前記符号付き表現の全ての桁に対して、前記整数の符号付き表現の桁をスキャンし、剰余二乗演算を行ない、１の桁の場合には剰余左シフト、−１の桁の場合には剰余右シフトする処理を繰り返し行なう処理を含む、請求項９記載のデータ処理方法。
【請求項１３】
前記整数の少なくとも３ビットがスキャンされ、
前記整数の全ビットに対して、前記第１処理、前記第２処理及び前記第３処理が繰り返される、請求項９記載のデータ処理方法。
【請求項１４】
前記第３処理は、
前記スキャンされたビットの最初の2ビットが０１又は１０のとき剰余二乗演算を1回行い、
前記スキャンされたビットが０１１のとき剰余二乗演算と剰余左シフトをそれぞれ1回行い、
前記スキャンされたビットが０１０のとき剰余二乗演算を２回行い且つ剰余左シフトを1回行い、
前記スキャンされたビットが１００のとき剰余二乗演算と剰余右シフトをそれぞれ1回行い、
前記スキャンされたビットが１０１のとき剰余二乗演算を２回行い且つ剰余右シフトを1回行う、処理を含む、請求項１３記載のデータ処理方法。
【請求項１５】
複数の小さい素数による整数の割算の剰余を計算するデータ処理システムであって、
前記小さい素数を生成する計算ユニットと、
前記整数と前記生成された小さい素数とから前記剰余を計算する剰余演算ユニットとを含み、
前記小さい素数は前記計算ユニットによって再構成される、データ処理システム。
【請求項１６】
前記剰余演算ユニットは古典的な剰余乗算ユニットである、請求項１５記載のデータ処理システム。
【請求項１７】
前記剰余演算ユニットはモンゴメリー乗算ユニットである、請求項１５記載のデータ処理システム。
【請求項１８】
前記小さい素数モンゴメリー定数を演算するためのモンゴメリ定数演算ユニットを更に含む請求項１７記載のデータ処理システム。
【請求項１９】
前記計算ユニットは、連続する素数の間の差のテーブルを格納するためのメモリユニットと、
小さい素数を格納するためのメモリユニットと、
追加ユニットとを有し、
前記追加ユニットは前記小さい素数と前記差のテーブルの要素とを加算する演算を行う、請求項１5記載のデータ処理システム。
【請求項２０】
前記計算ユニットは、
小整数を格納するメモリユニットと、
素数性のテストユニットと、
更新ユニットとを有し、
前記小整数は前記素数性テストユニットによって素数性がテストされ前記、小整数は当該小整数が素数でなない場合に前記更新ユニットによって更新される、請求項１５記載のデータ処理システム。
【請求項２１】
前記素数性テストユニットはミラーラビンテストユニットを含む、請求項２０記載のデータ処理システム。
【請求項２２】
前記素数性テストユニットはフェルマーテストニットを含む、請求項２０記載のデータ処理システム。
【請求項２３】
複数の小さい素数による整数の割算の剰余を計算するデータ処理方法であって、
一つの小さい素数を再構成する処理と、
前記再構成された小さい素数によって前記整数の割算の剰余を計算する処理とを含む、データ処理方法。
【請求項２４】
モンゴメリー定数を算出するステップをさらに含む、請求項２３記載のデータ処理方法。
【請求項２５】
少なくとも一つの小さい素数を再構成するステップと剰余を算出するステップとが並列的に実行される。請求項２３記載のデータ処理方法。
【請求項２６】
少なくとも一つの小さい素数を再構成するステップ、剰余を算出するステップ及びモンゴメリ定数を算出するステップが並列的に実行される請求項２４記載のデータ処理方法。
【請求項２７】
少なくとも一つの小さい素数を再構成するステップは、
連続する小さい素数間の差のテーブルを格納する処理と、
小さい素数を格納する処理と、
前記小さい素数の追加と前記差のテーブルの要素とを算出する処理と、を含む請求項２３記載のデータ処理方法。
【請求項２８】
少なくとも一つの小さい素数を再構成するステップは、
小整数を格納する処理と、
前記小整数の素数性を判定する処理と、
前記小整数が素数でない場合に当該小整数を更新する処理と、を含む請求項２３記載のデータ処理方法。
【請求項２９】
前記小整数の素数性を判定する処理はミラーラビンテストを行なう処理を含む請求項２８記載のデータ処理方法。
【請求項３０】
前記小整数の素数性を判定する処理はフェルマーテストを行なう処理を含む請求項２８記載のデータ処理方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００３
【補正方法】変更
【補正の内容】
【０００３】
ＲＳＡにおいて、メッセージはnビット整数としてコード化される。ＲＳＡ公開鍵はべき指数E（それは概して小さい）、ｎビットの法数Ｎから成る。ＲＳＡ秘密鍵はｎビット整数Ｄであり、E*D = 1 mod(P-1)*(Q-1)の関係がある。記号*は乗算を意味する。ここで、ＰとＱは秘密の素数であり、それはP*Q＝Nの関係を満足する。任意のメッセージ0＜=M＜N、（ＭE）D mod N＝Mに関して説明する。例えばアリスがＲＳＡ鍵となる（E,N）,Dの保有者であると仮定する、そして、ボブはアリスに暗号化されたメッセージＭを送りたいと仮定する。ボブはC=ME mod Nを計算し、アリスに暗号文を送る。次に、アリスはCD=(ME)D=M mod Nを計算して元の文を回復する。これにより、ＲＳＡの中心的な動作が累乗の剰余乗算XY mod N.であることが解る。Nが大きいとき、例えば２０４８ビットのようなとき、その累乗計算には時間がかかる。ＲＳＡの演算を高速化するには、中国の剰余定理を利用することができる。それは累乗の剰余乗算CD mod Nが２つの累乗の法PとＱに交換できることを言及する。N=P*QでありP及びQは法Ｎの約半分のデータサイズであるから、その中国の剰余定理によるアプローチ（ＲＳＡ−ＣＲＴ）によれば実際に演算を早く行うことができる。ＲＳＡ−ＣＲＴにおいて、その暗号化の手順は標準のＲＳＡと同様に、C=ME mod Nである。相違点は暗号からの復号手続きである。例えば、DP = D mod P-1 = E-1 mod P-1、DQ = D mod Q-1 = E-1 mod Q-1、Qinv =Q-1 mod P と定義されているとする。これにおいて、Z=X-1 mod YがZ*X=1 mod Y を満足する整数が1＜=Z＜Yであるとき、コンピュータによるＲＳＡ−ＣＲＴの復号処理は、MP = C^DP mod P、MQ = C^DQ mod Q、M = MQ + Q*[Qinv *（MP−MQ））mod P ]とされる。したがって、そのときのＲＳＡの鍵の対は、公開鍵であるE、N、標準ＲＳＡのための秘密鍵であるＤ及びＲＳＡ−ＣＲＴのためのＰ，Ｑ，ＤQ，ＤP，Ｑinvである。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００４２
【補正方法】変更
【補正の内容】
【００４２】
累乗演算のパフォーマンスを向上させる周知の方法は、ウインドウ方法を使用することである。ウィンドウ・サイズwを有するウインドウ方法において、べき指数からのwビットが同時に走査される。換言すれば、べき指数（それは通常メモリのそのバイナリの表現に保存される）は2wベースで再符号化（recoded）される。これらのwビットは整数ｊ（0＜=j＜2w）を表し、データBj mod Pが予め計算され、そしてウインドウ累乗技術ではA2 mod PおよびA*Bj mod Pが演算される。その代わりに標準のバイナリ法を用いると、A2の演算は同じであるが、w/2 の乗算が新たに必要になる。従ってウインドウ方法は乗算回数を減少させることができる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００４６
【補正方法】変更
【補正の内容】
【００４６】
ステップ1302において、べき指数P-1の最初の10のビットが走査されて、バッファjに書き込まれる。カウンタiはp-11に初期化される。そのカウンタの値は次に読むべきビット、即ちPp-11に一致されている。ステップ1303において、アキュムレータA（レジスタA）1121は、2jにセットされる。即ち、Aには最初0が書かれ、ｊ番目のビットは1にセットされる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
その後、べき乗演算が開始される。ステップ1312において、剰余乗算ユニット1113で10回連続してA2 mod Pが演算される。ウィンドウ・サイズがw=10だからである。ステップ1313では連続する10ビットPi,…,Pi-9がべき指数P-1から読み込まれる。ここで、Pはレジスタ1123に格納されており、整数値（Pi…Pi-9)2はバッファjに書き込まれる。jがゼロである場合、乗算は必要とはされず、フェルマーテストでは次の処理を続けることができる。ｊ＞0である場合、レジスタB 1122はステップ1322において2jにセットされる。すなわち、レジスタB1122はゼロにクリアされそのｊ番目のビット位置には1がセットされる。一旦レジスタB 1122がセットされると、A*B mod Pの剰余乗算がステップ1323で剰余付き演算操作ユニット1113を用いて実行される。最後に、ステップ1331で、べき指数の走査されたビットPiの位置を表しているインデックスiから10が減じられる。iが9より大きい限り（最も右の走査されたビットPi-9かP1以上であることを保証する）、上記のステップは繰り返される。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００６０
【補正方法】変更
【補正の内容】
【００６０】
ビットアレイフィルユニット1132への入力は、ビット配列1141、初期候補Pinit 1103および小さい素数z 1171から成る。最初に、バッファxはステップ1513で値Pinit mod zによって初期化される。この演算は計算が容易である。その理由は、次のことにある。Pinitが大きな整数であるにもかかわらず、zは単に16ビットだからである。次に、ビットアレイフィルユニットは、Pが奇数でP mod z=0であるような第1の整数P=Pinit+2iを計算する。Pinit mod z=0である場合、Pinitは全ての状態を満足しインデックスiがステップ1515で0にセットされる。一方、xはゼロでなく、Pinit=x mod zだからPinit+z-x=0 mod zである。一方、xが奇数なら、z-xは偶数であり、Pinit+z-xは奇数であり、要求される全ての状態を満たす。その結果、ステップ1522では、値（z-x）/2は、減算と右シフト（z-x)>>1を用いてバッファiに書き込まれる。他方、xが偶数の場合、Pinit+z-xは同様に偶数であるが、Pinit+2z-xは奇数である。したがって、ステップ1523で、減算と右シフトz-x>>1を用いて値（2z-x）/2=z-x/2がバッファに書き込まれる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００６３
【補正方法】変更
【補正の内容】
【００６３】
まず最初に、ビット配列は、ビット1だけを含む。換言すれば、Bが整数として表現される場合、そのバイナリの表現は、
B=(1111111111111111111111111111111111111111111111111111111111111111)2 
となる。Bは64ビットから成る。最初に、素数生成制御ユニットは、小さい素数テーブルT[0],…,T[15]を使用しているビット配列の適当な位置にゼロを書き込む。例えば、T[0]=3およびPinit mod 3 = 1である。1は奇数であり、それ故に、そのビットアレイにおいて(3-1)/2=1の位置で０を書き、そして、位置1+3=4および4+3=7の位置でそうする。T[0]=3によって篩にかけた後に、ビット配列は、
B=(1011011011011011011011011011011011011011011011011011011011011011)2 
になる。テーブルTの全ての小さい素数のためにその手順を繰り返して、ビット配列は、
B=(1001011000000001010011000010000001010010000001011001000010000010)2
になる。これによって、18ビットだけはまだ1にセットされたままなので、フェルマーテストで確かめられる整数Pinit+2iに対応する、より小さいインデックスiの値があることが解る。B[0]=1だから、Pinitはフェルマーテストで確かめられなければならない。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００７９
【補正方法】変更
【補正の内容】
【００７９】
《素数生成》
図9において、ステップ213および223では、素数P及びQ、秘密鍵素子DP =E-1mod P-1、DQ =E-1mod Q-1が発生される。この素数生成手順に対する入力301は、最初の偶数乱数Pinit（またはQinit）、公開べき指数E、ビット配列B[0],…,B[b-1]）、及びmri（ミラーラビンテストのための繰り返しの数）である。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００８２
【補正方法】変更
【補正の内容】
【００８２】
しかしながら、Pは更なる状態を満たさなければならない。すなわち、P-1と公開べき指数Eの最大公約数は、逆元DP=E-1 mod P-1が存在することを確実にするために、1（gcd(P-1,E)=1）でなければならない。したがって、ステップ331で、例えば非特許文献1に記載のバイナリ拡張GCDアルゴリズムを使用してDPが算出される。手順が「失敗」の場合は、gcd(P-1,E)が1でなく、Pは拒絶され、次の候補がテストされる。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００９５
【補正方法】変更
【補正の内容】
【００９５】
ステップ422または423が実行された後、Pinit +2j= 0mod z1のような第１のインデックスjは既に有効になっている。しかし、実際には、整数Pinit+2j+2z1、Pinit+2j+4z1、Pinit+2j+6z1およびその他もz1で割り切れる。したがって、ステップ432で、ゼロがビットB[j]に書かれ、jが範囲[ 0,…,b-1]にある限りＣＰＵ 122によってz1がインデックスjに追加される。そのように、ビットアレイに存在し、かつPk mod z1=0である全ての奇数Pk=Pinit+2*k*(j+z1)は、「不適当」な候補として識別される。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００９８
【補正方法】変更
【補正の内容】
【００９８】
実施の形態２ではモンゴメリー定数の計算にはRAM 112に配置された3個のバッファを使用し、バッファはステップ502で初期化される。バッファは2の累乗を格納し、xは部分的な結果を格納するアキュムレータであり、iは計算2p mod zの演算におけるべき指数pのスキャンに使われる。実施の形態２で使用される技術は、右から左へのバイナリの累乗である。基本的な考えは、y=2^(2^0)=21=2 mod z、y=2^(2^1)=22=4 mod z、y=2^(2^2)=24=16 mod z、y=2^(2^3)=28=256 mod zおよびその他を計算し、ｐのバイナリ表現を右から左にスキャンし、スキャンされたビットが１のとき、x=x*y mod zを計算するというものである。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０１０４
【補正方法】変更
【補正の内容】
【０１０４】
NAF再符号化は右から左に行われ、べき乗は左から右に行われるから、双方の処理を結合することはできない。即ち、最初に、べき指数（exponent）が再構成され、その新な表現の数が異なるRAM域に格納され、第２に、べき乗計算が行われる。この方法の欠点はべき指数が非常に大きいということであり、RAMにその再構成されたフォームを格納するための領域を予約しておかなければならない。再構成されたフォームは、少なくともオリジナルのべき指数に比べて大きい。前記再構成とべき乗演算が共に左から右に行われるとするなら、新たな表現を格納するためにRAMを割当てることを要しないであろう。前記双方の処理を一つに結合することが可能に成るからである。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０１０５
【補正方法】変更
【補正の内容】
【０１０５】
実施の形態２におけるフェルマーテストは次の結果を得ることができる。即ち、再構成とべき乗演算を一つの固有の処理フェーズに統合することができ、それゆえに、再構成された指数を格納するためのメモリの追加が必要とされない。これを達成するために、フェルマーテストはFAN表現を利用し、これは通常楕円曲線で使われ、楕円曲線については例えば特許文献２に記載があり、ここでは、wMOFと呼ばれている。FANはその生い立ちの点ではNAFと同様であるが、FAN再構成は左から右に実行され、べき乗演算フェーズと統合することはできる。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０１０６
【補正方法】変更
【補正の内容】
【０１０６】
FANべき乗演算における1つの繰り返しは、多くてもPi+1,Pi,Pi-1の3ビットのべき指数をスキャンすることである。その内容はケース１〜ケース6に分類できる。
[ケース1 ]：（Pi+1Pi)=(11)2は（Si)=(0)に再構成され、iは i-1にセットされる。
[ケース2 ]：（Pi+1PiPi-1)=(011)2は（SiSi-1)=(1)に再構成され、iは i-1にセットされる。
[ケース3 ]：（Pi+1PiPi-1)=(010)2は（Si)=(01)に再構成され、iは i-2にセットされる。
[ケース4 ]：（Pi+1Pi)=(00)2は（Si)=(0)に再構成され、iは i-1にセットされる。
[ケース5 ]：（Pi+1PiPi-1)=(100)2は（SiSi-1)=(-1)に再構成され、iは i-1にセットされる。
[ケース6 ]：（Pi+1PiPi-1)=(101)2は（Si)=(0-1)に再構成され、iは i-2にセットされる。
ケース1および4の場合、1回の二乗演算（square）がコプロセッサ123で行われる。ケース2の場合、1回の二乗演算がコプロセッサ123で行われ、CPUで1回の左シフト演算が行われる。ケース5の場合、1回の二乗演算がコプロセッサ123で行われ、CPUで1回の右シフト演算が行われる。ケース3の場合、2回の二乗演算がコプロセッサ123で行われ、CPUで1回の左シフトが行われる。ケース６の場合、2回の二乗演算がコプロセッサ123で行われ、CPUで1回の右シフトが行われる。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０１０９
【補正方法】変更
【補正の内容】
【０１０９】
Pi=1である場合、ビットPi+1の値はステップ612において点検される。それによる点検内容は以下の通りである。
[ ケース1 ]  Pi+1=0なら、検出されたケース１に対応するビット処理が行われる。ケース1は1つのモントゴメリー乗算処理だけを要求し、他の処理は必要とされず、次のビットの値がチェックされる。Pi+1=0である場合、ビットPi-1はケース2および3を区別するために点検されなければならない。したがって、ステップ622で、ビットPi-1の値が点検される。
[ケース2 ]  Pi-1=0の場合、検出されたケース２に対応されるビット処理が行われる。それゆえに、ステップ623でコプロセッサレジスタA 115のデータがCPU12により1ビットが左にシフトされる。シフト操作の後、レジスタA 115のデータはｐビットよりも多くなる。すなわち、この場合、ステップ625で必要に応じて何回もPはAから減じられなければならない。
[ケース3 ]   Pi-1=1の場合、検出されたケース３に対応されるビット処理が行われる。ステップ641で更にモンゴメリ乗算が行われ、カウンタiがもう1回デクリメントとされる。その後、コプロセッサレジスタA 115のデータがステップ623で左に1ビットシフトされ、ステップ625においてAがpビットよりも多いならば、PがAから減算される。しかしながら、i=1である場合、代わりにケース2が実行される。Pi=0である場合、ビットPi+1の値はステップ631において点検される。それによる点検内容は以下の通りである。
[ケース4 ]    Pi+1=0の場合、更なる動作は必要とされない。Pi+1=1である場合、ケース5および6を区別するためにPi-1が点検されなければならない。
[ケース5 ]  Pi-1=0の場合、Aは1ビット右へシフトされる。Aが偶数の場合、その最下位ビットは0であり、Aはステップ635でＣＰＵ122によって直接シフトされる。しかし、Aが奇数の場合、Pはステップ634でＣＰＵ 122によってAに加算される。AとPの両方とも奇数だから、A+Pは偶数であり、ステップ635で右へシフトされる。
[ケース6 ]   Pi-1=1の場合、モントゴメリー乗算が行われ、カウンタiはステップ642でデクリメントされ、その後、ステップ633に続く右シフトが行われる。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０１１１
【補正方法】変更
【補正の内容】
【０１１１】
《フェルマーテストの具体例》
この例では、整数P=109が素数性の判定対象であると仮定する。べき乗の剰余乗算2108 mod 109は、図13によるフェルマーテストを使用して計算される。二進数で、108=(1101100)2、であり、二進法に基づく左シフトを備えたフェルマーテストは3つの左シフトを行い、これはその最上位ビットの１に加えて1の桁が更に3桁あるからである。他方、108のFAN表現は108=(100-10-100)であり、2つの右シフトだけがある。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０１１２
【補正方法】変更
【補正の内容】
【０１１２】
詳しく説明する。P=109のビット長はp=7である。最初に、Aは2p+1 mod P = 28 mod 109で初期化される。28から= 256、28-2*109=38、レジスタA=38、カウンタiはp-2 = 5だからである。
[ i=5 ]の場合、レジスタAはMontMult(A,A,P)=MontMult(38,38,109)=76によって更新される。次のP5=1、P6=1、そして、対応する再符号は0であり、したがって、更なる操作は必要とされない。
[ i=4 ]の場合、レジスタAは、MontMult(76,76,109)=86によって更新される。次のP4=0、P5=1、P3=1、そして、対応する再符号が0-1である。レジスタAはMontMult(86,86,109)=68で更新され、カウンタiはデクリメントされる。68は偶数であるから、直接右シフトA>>1が実行され、レジスタAは34に更新される。
[ i=2 ]の場合、Aは、MontMult(34,34,109)=101に更新される。次のP2=1、P3=1、そして、対応する再符号は0である。
[ i=1 ]の場合、Aは、MontMult(101,101,109)=55によって更新される。次のP1=0、P2=1、P0=0、そして、対応する再符号は-1にある。レジスタAは偶数であるから、109がAに加えられ、右シフトが計算され、その結果、A=82を得る。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】０１１４
【補正方法】変更
【補正の内容】
【０１１４】
《ミラーラビンテスト》
ミラーラビンテストにおいてP-1は2j+1*Dと書かれる。ここで、j+1はP-1のバイナリの表現における末尾の０の数である。第１に、ある基数Bのために、累乗B←XD mod Pが計算される。XD mod P=1である場合、Pは多分素数であるだろう。他方、B=XD mod Pが1でない場合、Bは-1と比較される。Bが-1でない場合、Bはj回二乗演算され、各々の二乗演算の後、再び演算結果が-1と比較される。それら二乗演算を1つ行った後、B=-1のとき、ミラーラビンテストは停止され、Pはたぶん素数であるという結果が得られる。そうでなければPは合成数である。