【誤訳訂正書】
【提出日】平成21年11月12日(2009.11.12)
【誤訳訂正１】
【訂正対象書類名】特許請求の範囲
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【特許請求の範囲】
【請求項１】
機密保護のために大きな素数に依存した暗号化適用による使用のためにプログラムを実現する際に処理装置によって実行される方法であって、
前記方法は前記暗号化適用で用いるための１以上の推定素数候補を生成し、
前記方法は以下の一連のステップを実行する暗号化適用のハードウェアで実行される命令を含み、前記一連のステップは、
指定された第１のビットサイズを有する擬似ランダム数を与えるステップと、
第１の増分と合計することによって、前記擬似ランダム数から第１の候補を生成するステップとを含み、前記第１の増分は、前記第１の候補が１組の非常に小さな素数にとって互いに素となるように選択され、前記一連のステップはさらに、
前記非常に小さな素数以外の小さな素数のリストに対する試し割算によって、前記リストにおける前記小さな素数のすべてに対して互いに素である候補が見つかるまで、前記第１の候補で始まる連続した候補を繰り返して検査するステップとを含み、連続した候補は以下のステップによって検査され、前記以下のステップは、
（ｉ） 第１の候補の１組のモジュラ約分を計算するステップを含み、この１組のモジュラ約分の要素は、前記小さな素数のリストにおける異なるグループの素数の対応する組の積の第１の候補の法と合同する残余であり、前記積は、前記第１のビットサイズよりも少なくとも４倍小さい、指定された最大の第２のビットサイズを有し、前記以下のステップはさらに、
（ｉｉ）各々の連続した候補のために更新される前記第１の増分で始まる主な増分値を維持するステップを含み、主な増分値の各々の連続した更新は、前記第１の候補の値に追加されたときに、組をなす非常に小さな素数に対して互いに素である次の連続した候補を与えるステップと、
（ｉｉｉ）主な増分値の最近の更新によって増分された１組のモジュラ約分の各々の要素について、候補が合成数であることがわかるまで、対応するグループの素数における素数の各々に対する試し割算によって増分要素を検査して、残余がゼロであるかどうかを決定し、そうであれば現在の候補を合成数として指定するステップとを含み、前記一連のステップはさらに、
前記リストにおける前記小さな素数のすべてに対して互いに素である候補を見つけた後で、第１の候補に現在の主な増分値を加えたものに等しい前記候補を、少なくとも１つの既知の厳しい推定素数検査にかけて、候補が何らかの１つの前記厳しい検査に従って合成数であることがわかった場合、以前の通り小さな素数の試し割算および前記厳しい検査の双方を通過した候補が見つかるまで、小さな素数のリストに対する試し割算による連続した候補の検査を継続して、このような候補は推定素数値と考えられ、前記一連のステップはさらに、
前記暗号化適用で推定素数値を用いるステップを含む、方法。
【請求項２】
前記処理装置は、汎用プログラマブルコンピュータシステムを含み、プログラムは、前記コンピュータシステムによって読取り可能なソフトウェアの形態である、請求項１に記載の方法。
【請求項３】
前記処理装置は集積回路チップを含み、プログラムは前記チップによってアクセス可能なファームウェアの形態である、請求項１に記載の方法。
【請求項４】
前記処理装置は、前記プログラムを実現するように構成されたフィールドプログラマブル論理アレイ等の構成可能な論理チップを含む、請求項１に記載の方法。
【請求項５】
プログラムステップを実行するように特別に設計された特定用途向け集積回路の形態である、請求項１に記載の方法。
【請求項６】
第１のビットサイズは少なくとも２５６ビットである、請求項１に記載の方法。
【請求項７】
第２のビットサイズは３２ビットである、請求項１に記載の方法。
【請求項８】
前記１組の非常に小さな素数は、２，３，５および７を含む、請求項１に記載の方法。
【請求項９】
前記小さな素数のリストは、１１から２４１の間のすべての連続した素数を含む、請求項８に記載の方法。
【請求項１０】
前記第１の増分は、擬似ランダム数である法２１０と合同な残余を、ゼロから２０９の値を示す２１０要素の表と比較することによって見つけられ、２，３，５および７のすべてに対して互いに素である値に対応する表の要素は、表において２，３，５または７のいずれかで割り切れる値に対応する要素から区別され、前記比較は、前記残余を、２，３，５および７のすべてに対して互いに素である値にもたらす増分を識別するために行なわれる、請求項８に記載の方法。
【請求項１１】
前記主な増分は、前記２１０要素の表と比較することによって見つけられ、各々の連続した素数増分値は、前記残余を表における次の互いに素である値にもたらす、請求項１０に記載の方法。
【請求項１２】
前記既知の厳しい推定素数検査はミラー・ラビン検査を含む、請求項１に記載の方法。
【請求項１３】
前記既知の厳しい推定素数検査はフェルマー検査を含む、請求項１に記載の方法。
【請求項１４】
推定素数値を用いて少なくとも１つの暗号キーを生成する、請求項１に記載の方法。
【誤訳訂正２】
【訂正対象書類名】明細書
【訂正対象項目名】０００９
【訂正方法】変更
【訂正の内容】
【０００９】
発明の開示
上記の目的は、スマート増分および小さな素数の検査技術を実現する方法および装置によって満たされ、非常に小さな素数（たとえば２，３，５および７）に対して互いに素の、ランダムに生成された第１の大きな候補で始まる連続した候補は、モジュール単位で減じられ、可能性のある候補がより厳しい推定素数検査のために識別されるまで、指定された組の小さな素数（たとえば１１から２４１までの素数）に対して検査される。
【誤訳訂正３】
【訂正対象書類名】明細書
【訂正対象項目名】００１０
【訂正方法】変更
【訂正の内容】
【００１０】
スマート増分プログラム機能は、選択された非常に小さな素数の法、つまり選択された非常に小さな素数の積（たとえば２１０を法とする）に対して互いに素である合同な値の表を用いて次の候補への増分（必ずしも２ではない）を識別することによって、連続する整数候補を見つける。この表は、未知の方法によって最終的に見つけれられる素数の形式を記録し、これは暗号化による機密保護のために強く望まれる。これは即座に、非常に明白な合成数の約４分の３をふるいにかけて、非常に小さな素数に対して互いに素であると知られる残余の候補のみが、プログラムの小さな素数の検査機能における試し割算にかけられるようにする。この表を用いることによって、増分を、試し割算をすることなく大きな整数候補それ自体によって見つけることができる。
【誤訳訂正４】
【訂正対象書類名】明細書
【訂正対象項目名】００１４
【訂正方法】変更
【訂正の内容】
【００１４】
この方法は、スマート増分技術を用いることによって、推定素数を見つける速度を増大して、可能性のない候補を検査するのを回避する。所望のビットサイズ（たとえば１０２４ビット）のランダムな数が選択され、非常に小さな素数２，３，５および７に対して互いに素である値に即座に増分されて、最初の候補を生成する。各々の候補は、小さな素数のリストを用いた試し整数割算で始まるプログラム化されたコンピュータシステムまたはチップによって検査され、合成数であるとわかった場合、それは選択された偶数（必ずしも２ではない）によって増分されて、非常に小さな素数２，３，５および７に対して互いに素である次の候補を得る。この方法は、このスマート増分技術を用いて、整数割算によって検査される合成数の数を最小にする。試し割算は、大きな候補数に対して直接行なわれるのではなく、候補の３２ビットのモジュラ約分に対して行なわれ、さらに方法を加速する。小さな素数の試し割算検査を通過した候補を見つけると、この可能性のある候補は次に、（ミラー・ラビン検査またはフェルマー検査等の）１つ以上の既知の厳しい推定素数検査アルゴリズムを用いて検査される。これら後者の検査はより時間がかかる（たとえば上記に挙げた検査の双方はモジュールのべき乗を採用する）ために、整数割算検査において小さな素数に対して互いに素であることがわかった可能性のある候補のみがより厳しい検査にかけられる。
【誤訳訂正５】
【訂正対象書類名】明細書
【訂正対象項目名】００１７
【訂正方法】変更
【訂正の内容】
【００１７】
このプログラムにおいて、“Alea”は、検査されるべきランダムに選択された候補の整数の名前である。必要サイズの非常に大きな奇数の候補を迅速に生成することのできるいかなるランダムまたは擬似ランダム数生成ルーチンも用いることができる。“SmallPrimesTest”および“SmartIncrement”は、以下で詳細に説明するが、これらはそれぞれ、小さな素数のリストに対する整数割算検査および本発明のスマート増分技術を行なう機能である。最後に、検査される小さな素数に対して互いに素である数が得られる（AleaIsComposite＝false）。さらに、利用可能ないかなる１つ以上の厳しい従来の素数検査の方法も（関数読出“Number_Is_Probably_Prime”で表わされる）その数に対して採用することができる。しかしながら、このような厳しい検査は、最初に“SmallPrimesTest”を通過した候補に対してのみ行なわれる（可能性のある候補のうち約９０％が、SmartIncrementおよびSmallPrimesTest機能によって検証済みの合成数として排除されるため、より厳しい検査は候補値の残りの１０％に対してのみ行なわれる）。候補が選択された厳しい素数検査に落ちた場合、新しい候補が生成され、そこでメインプログラムが中止される。
【誤訳訂正６】
【訂正対象書類名】明細書
【訂正対象項目名】００２０
【訂正方法】変更
【訂正の内容】
【００２０】
Table_210は、２，３，５または７で割り切れるすべてのエントリに対するゼロからなる。しかしながら、２，３，５および７に対して互いに素であるエントリについて、表は非ゼロ値、たとえば整数それ自体を有する。表において割り切れる値を示す要素と、互いに素の値を示す要素とを区別する他の方法を用いることもできる。この表は、SmallPrimesTest機能を用いて、SmartIncrementが、さらなる整数割算検査のための２，３，５および７に対して互いに素である候補を選択する助けをする。
【誤訳訂正７】
【訂正対象書類名】明細書
【訂正対象項目名】００２３
【訂正方法】変更
【訂正の内容】
【００２３】
SmartIncrementのこの実施例は、各々の後に続く候補が２，３，５および７で割り切れないことを保証する。Aleaは直接には用いられない。むしろ、増分の計算は、Alea％２１０（すなわちモジュールの残り）に基づいて行なわれる。機能は、それが非ゼロである、すなわち２，３，５および７に対して互いに素である（対応する値Alea＋Incrementと合同である）Mod_210のための次の値を見つけるまで、Table_210を実行する。暗号化の使用について、既知の特定の形式を有する素数を用いないことが重要である。したがって、たとえば、それが計算するのに簡単であったとしても、候補の選択肢を１ｍｏｄ２１０と合同なものに制限しない。２，３，５，７および１１に対して互いに素である整数を識別する２３１０値のより大きな表が、好適な修正とともに用いられるかもしれないが、表における非常に小さな素数の数が増加するとリターンが減じられる（Table_210は、候補のうちの４８／２１０または２２．８６％を除くすべてを排除し、一方でより大きなTable_2310は候補のうちの４８０／２３１０または２０．７８％を除くすべてを排除する。大きめの小さな素数（たとえば１１から２４１）は、表に基づくスマート増分ではなく試し割算の方を用いてより適切に検査される。
【誤訳訂正８】
【訂正対象書類名】明細書
【訂正対象項目名】００２６
【訂正方法】変更
【訂正の内容】
【００２６】
第１のおよび第２の表は、それぞれ２５０未満の第１の既知の素数およびこのリストからの素数グループの積のリストである。素数２，３，５および７は表から省略されている。なぜなら、ランダムな数“Alea”が奇数であるだけでなく、上記で詳述した“SmartIncrement”手順を用いて３，５および７に対して互いに素となるように選択されることを保証するからである。第２のリストにおける積は、割算を容易にするために３２ビットに制限されている（利用可能なハードウェアに依存して、６４ビットまたはさらに大きな積を代わりに用いることができる）。第３の「インデックス」表は、小さな素数のリストを第２のリストにおける積に対応する連続した部分集合にインデックス付けする機能を果たす。
【誤訳訂正９】
【訂正対象書類名】明細書
【訂正対象項目名】００２７
【訂正方法】変更
【訂正の内容】
【００２７】
表のサイズは、所望の検査の数に依存して拡大または縮小することができる。必要と考えられる検査の数は、典型的に、生成されなければならない素数のビットサイズに基づいている。ここで示されたよりも大きな表については、素数それ自体ではなく、２，３，５および７に対して互いに素であるすべての数から表を導き出すことの方が便利であるかもしれない。合成数の小さな数が素数に追加して含まれる（たとえば１２１，１４３，１６９，１８７，２０９，２２１および２４７が上記表に追加される）一方で、検査のための値の生成が容易であることは、検査を絶対的に必要以上にわずかに長くすることよりも勝るかもしれない。しかしながら、やはり素数のリストが長くなると、小さな素数の試し割算によって排除する検証済みの合成数のリターンが減少する。試し割算からより厳しいミラー・ラビン、フェルマーまたはいくつかの他の推定素数検査へ切換えることが望まれる点は、主に候補のビットサイズおよび所望のセキュリティレベルに依存する判断の問題である。