(57)【特許請求の範囲】
【請求項１】
最上位ビットについては１をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが０の場合には−１と０と１のいずれをとることも許され、その上位ビットが−１又は１の場合には０をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成装置であって、
−１、０又は１をとる３値の乱数を生成する３値乱数生成手段と、
前記条件に基づいて、前記３値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に１ビットずつ前記条件を満たすように各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成手段とを備えたことを特徴とする乱数系列生成装置。
【請求項２】
前記乱数系列生成手段は、
前記３値乱数生成手段により生成された乱数を、それまでに生成した前記乱数系列のその時点における最下位ビットとして連結したならば、これによって得られた乱数系列が前記条件を満たすものになるか否かを調べ、満たすものになる場合に、該乱数を、該それまでに生成した前記乱数系列のその時点における最下位ビットとして連結する処理を、繰り返し行うことによって、前記任意のビット長の乱数系列を生成することを特徴とする請求項１に記載の乱数系列生成装置。
【請求項３】
前記乱数系列生成手段は、
生成すべき前記任意のビット長の乱数系列の最上位ビットについて、前記３値乱数生成手段により生成される乱数を用いることなく、１を与え、生成すべき前記任意のビット長の乱数系列の最上位ビット以外の各ビットについて、最上位ビットの１つ下位のビットから最下位ビットへ向かって順に、当該ビットの上位ビットが−１又は１である場合には、前記３値乱数生成手段により生成される乱数を用いることなく、当該ビットとして０を与え、当該ビットの上位ビットが０である場合には、前記３値乱数生成手段により生成された乱数を、当該ビットの値として用いることによって、前記任意のビット長の乱数系列を生成することを特徴とする請求項１に記載の乱数系列生成装置。
【請求項４】
前記乱数系列生成手段は、
生成すべき前記任意のビット長の乱数系列の最上位ビットについて、前記３値乱数生成手段により生成される乱数を用いることなく、１を与え、生成すべき前記任意のビット長の乱数系列の最上位ビットの１つ下位のビットについて、前記３値乱数生成手段により生成される乱数を用いることなく、０を与え、生成すべき前記任意のビット長の乱数系列の最上位ビット及び最上位ビットの１つ下位のビット以外の各ビットについて、最上位ビットの１つ下位のビットから最下位ビットへ向かって順に、当該ビットの上位ビットが−１又は１である場合には、前記３値乱数生成手段により生成される乱数を用いることなく、当該ビットとして０を与え、当該ビットの上位ビットが０である場合には、前記３値乱数生成手段により生成された乱数を、当該ビットの値として用いることによって、前記任意のビット長の乱数系列を生成することを特徴とする請求項１に記載の乱数系列生成装置。
【請求項５】
前記３値乱数生成手段が前記乱数を生成するにあたっての−１の発生確率と０の発生確率と１の発生確率との比率を特定の比率とすることを特徴とする請求項１ないし４のいずれか１項に記載の乱数系列生成装置。
【請求項６】
前記乱数系列生成手段により生成された前記乱数系列を、最上位ビットから最下位ビットへ向かって順に、１ビット又は複数ビットずつ逐次出力する主力手段を更に備えたことを特徴とする請求項１ないし５のいずれか１項に記載の乱数系列生成装置。
【請求項７】
最上位ビットについては１をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが０の場合には−１と０と１のいずれをとることも許され、その上位ビットが−１又は１の場合には０をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成装置における乱数系列生成方法であって、
前記乱数系列生成装置が備える３値乱数生成手段が、−１、０又は１をとる３値の乱数を生成する３値乱数生成ステップと、
前記乱数系列生成装置が備える乱数系列生成手段が、前記条件に基づいて、前記３値乱数生成ステップにおいて前記３値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に１ビットずつ前記条件を満たすように各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成ステップとを有することを特徴とする乱数系列生成方法。
【請求項８】
最上位ビットについては１をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが０の場合には−１と０と１のいずれをとることも許され、その上位ビットが−１又は１の場合には０をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成装置としてコンピュータを機能させるためのプログラムであって、
−１、０又は１をとる３値の乱数を生成する３値乱数生成手段と、
前記条件に基づいて、前記３値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に１ビットずつ前記条件を満たすように各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成手段としてコンピュータを機能させることを特徴とするプログラム。
【請求項９】
最上位ビットについては１をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが０の場合には−１と０と１のいずれをとることも許され、その上位ビットが−１又は１の場合には０をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成部と、該乱数系列をべき指数として使用する演算を行う演算部とを備えた演算処理装置であって、
前記乱数系列生成部は、
−１、０又は１をとる３値の乱数を生成する３値乱数生成手段と、
前記条件に基づいて、前記３値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に１ビットずつ前記条件を満たすように各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成手段とを有するものであり、
前記演算部は、前記乱数系列生成手段による前記乱数系列の生成と並行して、前記乱数系列生成手段により生成された前記乱数系列を、その最上位ビットから最下位ビットへ向かって１又は複数ビットずつ順に使用しながら、特定の繰り返し処理を行う手段を有するものであることを特徴とする演算処理装置。
【請求項１０】
前記演算は、べき乗剰余算又は楕円曲線暗号のスカラー倍算であることを特徴とする請求項９に記載の演算処理装置。
【請求項１１】
最上位ビットについては１をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが０の場合には−１と０と１のいずれをとることも許され、その上位ビットが−１又は１の場合には０をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成部と、該乱数系列をべき指数として使用する演算を行う演算部とを備えた演算処理装置における演算処理方法であって、
前記乱数系列生成部が備える３値乱数生成手段が、−１、０又は１をとる３値の乱数を生成する３値乱数生成ステップと、
前記乱数系列生成部が備える乱数系列生成手段が、前記条件に基づいて、前記３値乱数生成ステップにおいて前記３値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に１ビットずつ前記条件を満たすように各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成ステップと、
前記演算部が、前記乱数系列生成ステップにおける前記乱数系列生成手段による前記乱数系列の生成と並行して、前記乱数系列生成ステップにおいて前記乱数系列生成手段により生成された前記乱数系列を、その最上位ビットから最下位ビットへ向かって１又は複数ビットずつ順に使用しながら、特定の繰り返し処理を行うステップとを有することを特徴とする演算処理方法。
【請求項１２】
最上位ビットについては１をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが０の場合には−１と０と１のいずれをとることも許され、その上位ビットが−１又は１の場合には０をとることのみ許される条件を満たす乱数系列を生成し、生成した該乱数系列をべき指数として使用する演算を行う演算処理装置としてコンピュータを機能させるためのプログラムであって、
−１、０又は１をとる３値の乱数を生成する３値乱数生成手段と、
前記条件に基づいて、前記３値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に１ビットずつ前記条件を満たすように各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成手段と、
前記乱数系列生成手段による前記乱数系列の生成と並行して、前記乱数系列生成手段により生成された前記乱数系列を、その最上位ビットから最下位ビットへ向かって１又は複数ビットずつ順に使用しながら、特定の繰り返し処理を行う演算手段としてコンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乱数系列を生成する乱数系列生成装置及び乱数系列生成方法、べき乗剰余算やスカラー倍算などの演算を行う演算処理装置及び演算処理方法、並びにプログラムに関する。
【背景技術】
【０００２】
公開鍵暗号方式やディジタル署名方式では、べき乗剰余算やスカラー倍算といった演算を用いるものが多く存在する。べき乗剰余算とは、ｙ＝ｘk ｍｏｄ ｎのような演算であり、ＥｌＧａｍａｌ暗号やＲＳＡ暗号などに用いられている。スカラー倍算とは、楕円曲線暗号系に用いられる演算で、楕円曲線上の、べき倍算Ｙ＝ｋＸのことを言う。
【０００３】
公開鍵暗号では１０２４ビットなどの大きなデータを扱うため、ＮＡＦなどの符号付整数を利用した冗長表現（バイナリ表現など）と、バイナリ法（Ｂｉｎａｒｙ法(Double-and-ADD method)）やｗｉｎｄｏｗ法などといったテクニックを組み合わせることによって、べき乗剰余算やスカラー倍算を効率的に行う様々な方法が知られている。
【０００４】
以下に、バイナリ法のアルゴリズムを示す。  
［バイナリ法］  
（Ｓｔｅｐ０）  Ｉｎｐｕｔ  ｋ，ｘ，ｎ  
（Ｓｔｅｐ１）  整数ｋを、ｋ＝Σ（ｋi・２i）と２進数表現する（ｉ＝０〜ｌ−１につきそれぞれｋiを求める）。ここで、ｋi∈Ｔ，Ｔ＝［０，１］とする。  
（Ｓｔｅｐ２）  ｙ＝１  
（Ｓｔｅｐ３）  ｉ＝ｌ−１から０までの間、次を繰り返す。  
（Ｓｔｅｐ３−１）  ｙ＝ｙ2 （ｍｏｄ ｎ）  
（Ｓｔｅｐ３−２）  ｋi＝１ならば、ｙ＝ｙ・ｘ （ｍｏｄ ｎ）  
（Ｓｔｅｐ４）  Ｏｕｔｐｕｔ  ｙ（＝ｘk ｍｏｄ ｎ）
バイナリ法などのビットの０，１の値に依存した演算アルゴリズムでは、べき指数を２進数表現したときのハミング重みが小さいほど計算量が少なくなることが分かっている。
【０００５】
上記のようなバイナリ表現に関しては、符号無し２進数表現（Ｔ＝［０，１］）は一意的に決まるが、符号付２進数表現（Ｔ＝［−１，０，１］）は一意的には決定しないという性質がある。なお、以下で用いる“-１”は“−１”を表すものとする。
【０００６】
例えば、ｋ＝１８１のとき、Ｔ＝［０，１］ならば、１８１＝１０１１０１０１である（一意的である）。これに対して、Ｔ＝［−１，０，１］ならば、１８１＝１-１１０-１１-１１-１＝１-１１-１１０１０１＝…である（一意的でない）。
【０００７】
この符号付２進数表現において、非ゼロ係数の数を最小にする方法として、ＮＡＦ表現が知られている。
【０００８】
ＮＡＦ表現とは、全てのｉ≧０に対してｋi×ｋi+1＝０となるような符号付２進数表現のことを言い、任意の正整数に変換アルゴリズムを作用させることで一意的に表現することができる。ＮＡＦ変換アルゴリズムの実装方法はいくつか考えられる。
【０００９】
以下に、基本的なＮＡＦ変換アルゴリズムを示す。  
［ＮＡＦ変換アルゴリズム］  
Ｉｎｐｕｔ  ｎ  
ｋ←ｎ  
Ｓ←＜  ＞  
ｗｈｉｌｅ  ｋ＞０  
Ｉｆ  ｋ：ｏｄｄ  ｕ←２−（ｋ ｍｏｄ ４）  
ｅｌｓｅ          ｕ←０  
ｋ←ｋ−ｕ  
Ｐｒｅｐｅｎｄ  ｕ  ｔｏ  Ｓ  
ｋ←ｋ／２  
ｅｎｄ  ｗｈｉｌｅ
Ｏｕｔｐｕｔ  Ｓ
例えば、正整数ｎ＝１８１のとき、符号付２進数表現Ｓ＝１０-１０-１０１０１が得られる。
【００１０】
さらに、バイナリ法を符号付２進数表現に拡張した符号付バイナリ法のアルゴリズムが知られている。
【００１１】
以下に、符号付バイナリ法のアルゴリズムを示す。なお、下記のｘ-1は、ｘの法ｎにおける逆元を表している。  
［符号付バイナリ法］  
（Ｓｔｅｐ０）  Ｉｎｐｕｔ  ｋ，ｘ，ｎ  
（Ｓｔｅｐ１）  整数ｋを、ｋ＝Σ（ｋi・２i）と２進数表現する（ｉ＝０〜ｌ−１につきそれぞれｋiを求める）。ここで、ｋi∈Ｔ，Ｔ＝［−１，０，１］とする。  
（Ｓｔｅｐ２）  ｙ＝１  
（Ｓｔｅｐ３）  ｉ＝ｌ−１から０までの間、次を繰り返す。  
（Ｓｔｅｐ３−１）  ｙ＝ｙ2 （ｍｏｄ ｎ）  
（Ｓｔｅｐ３−２）  ｋi＝１ならば、ｙ＝ｙ・ｘ （ｍｏｄ ｎ）  
（Ｓｔｅｐ３−３）  ｋi＝−１ならば、ｙ＝ｙ・ｘ-1 （ｍｏｄ ｎ）  
（Ｓｔｅｐ４）  Ｏｕｔｐｕｔ  ｙ（＝ｘk ｍｏｄ ｎ）
これらの符号付バイナリ法やＮＡＦ表現といったテクニックを用いることで、べき乗剰余算やスカラー倍算が効率よく演算できることになる。例えば、非特許文献１，２参照には、ＮＡＦを用いると非ゼロ係数の数が全体の約１／３となり（ゼロの数は約２／３）、べき乗剰余算（あるいはスカラー倍算）の計算量に関しては、ＮＡＦを用いない場合と比べて約１１％効率化が図れる旨が記述されている。
【００１２】
他方、公開鍵暗号方式やディジタル署名方式では、標準プロトコルの中で、乱数を生成し、生成した乱数をべき指数としてべき乗剰余算を行うことが多くある。例えば、ＥｌＧａｍａｌ暗号やＤＨ鍵共有法、ＤＳＡ署名などである。
【００１３】
それらの標準プロトコルにおいて、乱数とＮＡＦ表現を利用したべき乗剰余算処理部分は、次の３ステップから構成される（なお、ｋとｄは同値の整数である）。  
（Ｓｔｅｐ１）  乱数ｋを生成する。  
（Ｓｔｅｐ２）  ｋのＮＡＦ変換ｄ＝ＮＡＦ（ｋ）を行う。  
（Ｓｔｅｐ３）  べき乗剰余算ｙ＝ｘd ｍｏｄ ｎを計算する。
【非特許文献１】CRYPTOGRAPHY Theory and Practice SECOND EDITION(pp.258-259)，  Author: Douglas Stinson，  Publisher: Chapman & Hall/CRC，  ISBN: 1-58488-206-9
【非特許文献２】Guide to Elliptic Curve Cryptography(pp.98-100) ，  Author: Darrel Hankerson, Alfred J. Menezes, Scott Vanstone，  Publisher: Springer Professional Computing Series，  ISBN: 0-387-95273-X
【発明の開示】
【発明が解決しようとする課題】
【００１４】
バイナリ表現への変換処理を行い、符号付２進数表現を生成することに関して、特定の値をバイナリ変換し非ゼロ係数の数を削減することには意味があるが、乱数のようなランダムな値を変換する際には、変換処理を行う必要は無く、さらに効率良く符号付２進数表現された乱数系列を生成できる可能性が考えられる。
【００１５】
また、ＮＡＦ変換アルゴリズムでは、最下位ビット（ＬＳＢ）から最上位ビット（ＭＳＢ）へと１桁ごとに変換していく必要があるが、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）へ計算していく、べき乗剰余算やスカラー倍算等の演算方法との併用をすると、変換処理の重複を招き、結果的に演算処理時間が長くなるという欠点を持っている。
【００１６】
本発明は、上記事情を考慮してなされたもので、より効率的に、符号付２進数表現された乱数系列を生成できる乱数系列生成装置及び乱数系列生成方法、より効率的に、符号付２進数表現された乱数系列を生成するとともに、該乱数系列をべき指数として使用して、べき乗剰余算やスカラー倍算などの演算を行うことができる演算処理装置及び演算処理方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明は、最上位ビットについては１をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが０の場合には−１と０と１のいずれをとることも許され、その上位ビットが−１又は１の場合には０をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成装置であって、−１、０又は１をとる３値の乱数を生成する３値乱数生成手段と、前記条件に基づいて、前記３値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に１ビットずつ前記条件を満たすように各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成手段とを備えたことを特徴とする。  
また、本発明は、最上位ビットについては１をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが０の場合には−１と０と１のいずれをとることも許され、その上位ビットが−１又は１の場合には０をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成部と、該乱数系列をべき指数として使用する演算を行う演算部とを備えた演算処理装置であって、前記乱数系列生成部は、−１、０又は１をとる３値の乱数を生成する３値乱数生成手段と、前記条件に基づいて、前記３値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に１ビットずつ前記条件を満たすように各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成手段とを有するものであり、前記演算部は、前記乱数系列生成手段による前記乱数系列の生成と並行して、前記乱数系列生成手段により生成された前記乱数系列を、その最上位ビットから最下位ビットへ向かって１又は複数ビットずつ順に使用しながら、特定の繰り返し処理を行う手段を有するものであることを特徴とする。
【００１８】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る本発明は装置に係る発明としても成立する。  
また、装置または方法に係る本発明は、コンピュータに当該発明に相当する手順を実行させるための（あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための）プログラムとしても成立し、該プログラムを記録したコンピュータ読み取り可能な記録媒体としても成立する。
【発明の効果】
【００１９】
本発明によれば、より効率的に、符号付２進数表現された乱数系列を生成することができる。また、本発明によれば、より効率的に、符号付２進数表現された乱数系列を生成するとともに、該乱数系列をべき指数として使用して、べき乗剰余算やスカラー倍算などの演算を行うことができる。
【発明を実施するための最良の形態】
【００２０】
以下、図面を参照しながら本発明の実施形態について説明する。
【００２１】
（第１の実施形態）
図１に、本発明の第１の実施形態に係るＮＡＦ乱数系列生成装置の構成例を示す。
【００２２】
図１に示されるように、ＮＡＦ乱数系列生成装置１００は、制御部１０１、乱数系列生成部１０２、記憶部１０３、出力部１０４を備えている。
【００２３】
ＮＡＦ乱数系列生成装置１００は、例えば、ＩＣチップなどの暗号モジュール内に組み込まれ、暗号化、復号化、鍵生成又は署名生成などの際に、任意の正整数値ｌを入力すると、ＮＡＦの規則に従ったｌビットの乱数系列（符号付２進数表現）を生成し、出力する。
【００２４】
乱数生成部１０２は、［−１，０，１］の３値からなる乱数を生成する機能を有する。
【００２５】
制御部１０１は、本ＮＡＦ乱数系列生成装置１００により生成される乱数系列がＮＡＦ規則を満たすように制御する機能を有する。
【００２６】
記憶部１０３は、少なくとも１つ前に生成された乱数ビットを記憶しておく機能を有する。なお、新たに生成されたものから順にｕ（ｕは予め定められた複数）ビットを記憶する構成や、生成された全ビット列を記憶する構成も可能である。
【００２７】
出力部１０４は、記憶部１０３に蓄積されているＮＡＦ乱数ビットを、生成された順に（最上位ビットから最下位ビットへ向かって順に）、１ビットずつ逐次出力していく機能を有する。なお、記憶部１０３に蓄積されているＮＡＦ乱数ビットを、生成された順に（最上位ビットから最下位ビットへ向かって順に）、ｓ（ｓは予め定められた複数）ビットずつ逐次出力していく構成や、ＮＡＦ乱数系列の全ビットの生成が完了した後に、該ＮＡＦ乱数系列の全ビットを出力する構成も可能である。また、出力部１０４が１回に出力する乱数ビット数を、設定あるいはその都度指示できるようにしてもよい。
【００２８】
ここで、ＮＡＦの規則は、例えば、下記のような２つの規則（条件）で表現することができる。  
（ａ）当該乱数系列において、最上位ビットは、１であることのみ許される。  
（ｂ）当該乱数系列において、非ゼロのビット同士が隣接することは、許されない（０と０が隣接すること、０と１が隣接すること、０と−１が隣接することは、いずれも許されるが、１と１が隣接すること、１と−１が隣接すること、及び−１と−１が隣接することは、いずれも許されない）。
【００２９】
また、本実施形態において乱数系列を最上位ビットから最下位ビットへ向かって順番に生成することを考慮すると、ＮＡＦの規則は、例えば、下記のように表現することもできる。  
（Ａ）当該乱数系列において、最上位ビットは、１をとることのみ許される。  
（Ｂ）当該乱数系列において、最上位ビット以外のビットは、そのビットの上位ビットが０の場合には−１と０と１のいずれをとることも許され、そのビットの上位ビットが−１又は１の場合には０をとることのみ許される。
【００３０】
図２に、本実施形態のＮＡＦ乱数系列生成装置において実行される、ＮＡＦの規則を満たす乱数系列を、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）へ向かって順に生成する処理手順の一例を示す。
【００３１】
ここでは、生成すべきＮＡＦ乱数系列のビット長をｌとし、内部の乱数生成部１０２によって生成される乱数をｒ∈［−１，０，１］とし、生成されるＮＡＦ乱数系列をｄl-1，…，ｄ0とする。
【００３２】
本実施形態のＮＡＦ乱数系列生成装置にｌが入力されると、制御部１０１において、ｊ＝ｌが実行される（ステップＳ２１）。
【００３３】
以降は、ループ処理となる。
【００３４】
まず、ｊ＝ｊ−１が実行される（ステップＳ２２）。最初は、ｊ＝ｊ−１＝ｌ−１となり、これによって、最上位ビット（ｄl-1）に焦点があてられる。
【００３５】
次に、乱数生成部１０２により乱数ｒ∈［−１，０，１］を生成する（ステップＳ２３）。生成された乱数ｒ∈［−１，０，１］は、制御部１０１により受け取られる。
【００３６】
次に、制御部１０１において、乱数ｒがＮＡＦ規則を満たすか否か調べ（ステップＳ２４）、満たしている場合には、ステップＳ２５へ進み、満たしていない場合には、（該乱数ｒを破棄して）ステップＳ２３へ戻る。ＮＡＦ規則を満たすか否かを判定するアルゴリズムについては後述する。
【００３７】
ＮＡＦ規則を満たしていた場合には、ｄj＝ｒを実行する（ステップＳ２５）。最上位ビット（ｄl-1）に焦点があてられる場合には、ｄl-1＝ｒが実行される。ｄj＝ｒは、記憶部１０３に記憶され、出力部１０４により出力される。
【００３８】
ここで、ｊ＝０であるか否か調べ（ステップＳ２６）、ｊ≠０である場合には、ステップＳ２２へ戻り（ｊ＝ｊ−１が実行されて、１つ下位のビットに焦点があてられる）、以降、ステップＳ２６でｊ＝０となるまで繰り返し同様の処理が行われる。
【００３９】
また、ステップＳ２６でｊ＝０である場合には、ｌビットのＮＡＦ乱数系列が全て決定されたことになり、この処理を終了する。
【００４０】
なお、上記手順例において、乱数生成部１０２の動作とステップＳ２３の動作とは同期している（ステップＳ２３の実行タイミングにおいてのみ、乱数生成部１０２が動作する）ものであってもよいが、必ずしも同期している必要はなく、乱数生成部１０２は周囲の動作とは独立に常に乱数を発生し続ける形態も可能である。
【００４１】
ここで、上記のようなＮＡＦ規則を満たすか否かを判定するアルゴリズムについて説明する。
【００４２】
図３に、生成された乱数ｒを乱数系列の当該ビットに採用した場合にＮＡＦ規則が満されるか否かについて判定する手順の一例を示す。
【００４３】
まず、ｊ＝ｌ−１であるか否か（つまり、最上位ビットであるか否か）を判定する（ステップＳ３１）。ｊ＝ｌ−１である（最上位ビットである）場合には、ステップＳ３２へ進み、ｊ≠ｌ−１である（最上位ビットでない）場合には、ステップＳ３３へ進む。
【００４４】
ステップＳ３１でｊ＝ｌ−１である場合には、ＮＡＦ規則によれば最上位ビットｄl-1は１しか許されないので、（図２のステップＳ２３で得られた）乱数ｒが１であるか否かを調べ（ステップＳ３２）、ｒ＝１であるときは、「ｒがＮＡＦ規則を満たす」旨の判定結果とし、ｒ≠１であるときは、「ｒがＮＡＦ規則を満たさない」旨の判定結果とする。
【００４５】
他方、ステップＳ３１でｊ≠ｌ−１である（最上位ビットでない）場合には、１つ前（１つ上位）のビットｄj+1が０であるか否かを調べ（ステップＳ３３）、ｄj+1＝０であるときは、ＮＡＦ規則によればｒが［−１，０，１］のいずれの値を取ってもｄj＝ｒとして許されるので（ｒの値を調べることなく）、「ｒはＮＡＦ規則を満たす」旨を判定結果とする。また、ｄj+1≠０であるときは、ＮＡＦ規則によればｄj＝０しか許されないため、ｒ＝０であるか否かを調べ（ステップＳ３４）、ｒ＝０であれば「ｒはＮＡＦ規則を満たす」旨の判定結果とし、ｒ≠０であれば「ｒがＮＡＦ規則を満たさない」旨の判定結果とする。
【００４６】
以上のように、本実施形態によれば、ＮＡＦ規則を満たすようなＮＡＦ乱数系列を生成することが可能となる。
【００４７】
（第２の実施形態）
第１の実施形態は、ＮＡＦ規則を満たす乱数が発生されるまでループを繰り返す処理があるため、全ｌビットのＮＡＦ乱数系列が決定するまでの時間は不確定となるものであるが、第２の実施形態は、全ｌビットのＮＡＦ乱数系列が決定するまでの時間をほぼ一定とするものである。
【００４８】
本実施形態では、第１の実施形態と相違する点を中心に説明する。
【００４９】
本実施形態に係るＮＡＦ乱数系列生成装置の構成例は、第１の実施形態と同様である（図１参照）。
【００５０】
図４に、本実施形態のＮＡＦ乱数系列生成装置において実行される、ＮＡＦの規則を満たす乱数系列を、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）へ向かって順に生成する処理手順の一例を示す。
【００５１】
第１の実施形態と同様、生成すべきＮＡＦ乱数系列のビット長をｌとし、内部の乱数生成部１０２によって生成される乱数をｒ∈［−１，０，１］とし、生成されるＮＡＦ乱数系列をｄl-1，…，ｄ0とする。
【００５２】
本実施形態のＮＡＦ乱数系列生成装置にｌが入力されると、制御部１０１において、まず、ｊ＝ｌ−１とｄj＝１とが実行され（ステップＳ４１）、これによって、最上位ビットが決定される。この最上位ビットｄl-1＝１は、記憶部１０３に記憶され、出力部１０４により出力される。
【００５３】
以降は、ループ処理となる。
【００５４】
まず、ｊ＝ｊ−１が実行され（ステップＳ４２）、これによって、１つ下位のビットに焦点があてられる。
【００５５】
次に、記憶部１０３に記憶されている１つ前（上位）のビットｄj+1（最初のループでは、最上位ビットｄl-1）が０であるか否か調べ（ステップＳ４３）、ｄj+1≠０である場合には、ステップＳ４４へ進み、ｄj+1＝０である場合には、ステップＳ４５へ進む。
【００５６】
ステップＳ４３でｄj+1≠０である（すなわち、ｄj+1＝１ or −１である）場合には、次に来るビット値はＮＡＦ規則により必ず０となるので、ｄj＝０を実行して（ステップＳ４４）、ステップＳ４７へ進む。ｄj＝０は、記憶部１０３に記憶され、出力部１０４で出力される。
【００５７】
他方、ステップＳ４３でｄj+1＝０である場合には、ＮＡＦ規則から次に取り得るビット値として［−１，０，１］の３値が候補となるので、乱数生成部１０２によって乱数ｒ∈［−１，０，１］を生成し（ステップＳ４５）、次いで、ｄj＝ｒを実行して（ステップＳ４６）、ステップＳ４７へ進む。ｄj＝ｒは、記憶部１０３に記憶され、出力部１０４で出力される。
【００５８】
ここで、ｊ＝０であるか否か調べ（ステップＳ４７）、ｊ≠０である場合には、ステップＳ４２へ戻り（ｊ＝ｊ−１が実行されて、１つ下位のビットに焦点があてられる）、以降、ステップＳ４７でｊ＝０となるまで繰り返し同様の処理が行われる。
【００５９】
また、ステップＳ４７でｊ＝０である場合には、ｌビットのＮＡＦ乱数系列が全て決定されたことになり、この処理を終了する。
【００６０】
なお、上記処理手順では、生成すべきＮＡＦ乱数系列の最上位ビットについては、乱数の生成もループ処理も行わずに、１を与え、最上位ビット以外のビットについて、ループ処理を施すようにしたが、その代わりに、生成すべきＮＡＦ乱数系列の最上位ビット及びその１つ下位のビットについては、乱数の生成もループ処理も行わずに、それぞれ１及び０を与え、最上位ビット及びその１つ下位のビット以外のビットについて、ループ処理を施すような構成も可能である。
【００６１】
以上のように、本実施形態によれば、ＮＡＦ規則を満たすようなＮＡＦ乱数系列を生成することが可能となる。
【００６２】
べき指数として乱数系列を使用するようなべき乗剰余算やスカラー倍算等の演算を行うにあたって、従来は、乱数系列の生成が全て完了した後に、該乱数系列に対してＮＡＦ変換を施し、その後に、該ＮＡＦ変換した乱数系列を用いた、べき乗剰余算を行う、という手順を踏む必要があったが、第１，２の実施形態によれば、図５（ａ）のように、ＮＡＦ乱数系列生成装置において、直接、ＮＡＦ乱数系列を生成し、これを、べき乗剰余算やスカラー倍算等の演算を行う演算装置に与えることができるので、処理の高速化を図ることができる。また、図５（ａ）のように、ＮＡＦ乱数系列を全て生成してから、べき乗剰余算やスカラー倍算等の演算を行う代わりに、図５（ｂ）のように、ＮＡＦ乱数系列生成装置において、ＮＡＦ乱数系列を、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）へ向かって順に生成し、生成した乱数ビットをべき乗剰余算やスカラー倍算等の演算を行う演算装置に与えるとともに、これに並行して、演算装置において、べき乗剰余算やスカラー倍算等の演算を行うことができるようになるので、この場合には、さらに、処理の高速化を図ることができる。
【００６３】
ところで、第１の実施形態又は第２の実施形態のＮＡＦ乱数系列生成装置と、数値系列の最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）へ向かって順に１ビット又は所定の複数ビットを使用して所定の演算を行う装置と組み合わせて、演算処理装置を構成することも可能である。
【００６４】
以下、第３及び第４の実施形態では、この所定の演算を行う装置として、べき乗剰余算装置を用いる場合を例にとって説明し、第５の実施形態では、スカラー倍算装置を用いる場合を例にとって説明する。
【００６５】
（第３の実施形態）
図６に、第３の実施形態の演算処理装置２００の構成例を示す。
【００６６】
本実施形態の演算処理装置２００は、第１の実施形態のＮＡＦ乱数系列生成装置に相当するＮＡＦ乱数系列生成部１２０に、所定の演算を行う演算部として、べき乗剰余算を行う、べき乗剰余算部１０５を追加した構成になっている。なお、べき乗剰余算部１０５は、既存のもので構わない。
【００６７】
本実施形態では、第１の実施形態と相違する点を中心に説明する。
【００６８】
図７に、本実施形態の演算処理装置において実行される、ＮＡＦ乱数系列生成及びべき乗剰余算の処理手順の一例を示す。
【００６９】
第１の実施形態と同様、生成すべきＮＡＦ乱数系列のビット長をｌとし、内部の乱数生成部１０２によって生成される乱数をｒ∈［−１，０，１］とし、生成されるＮＡＦ乱数系列をｄl-1，…，ｄ0とする。また、本実施形態では、生成されるＮＡＦ乱数系列ｄl-1，…，ｄ0の１０進数値をべき乗剰余算におけるべき指数ｄとし、べき乗される値をｘとし、剰余演算の法をｎとする。
【００７０】
この手順例は、べき指数となるＮＡＦ乱数系列のビット長ｌと、べき乗される値ｘと、法ｎ（ｎ：ｐｒｉｍｅ）とを入力したとき、べき乗剰余算結果ｙ＝ｘd ｍｏｄ ｎが出力となるものであるが、その際、第１の実施形態と同様に、ＮＡＦの規則を満たす乱数系列を、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）へ向かって順に生成しながら、併せて、符号付バイナリ法を実行するものである。
【００７１】
本実施形態の演算処理装置にｌ、ｘ、ｎが入力されると、制御部１０１において、ｊ＝ｌが実行され、べき乗剰余算部１０５において、ｙ＝１が実行される（ステップＳ５１）。
【００７２】
以降は、ループ処理となる。
【００７３】
まず、ｊ＝ｊ−１が実行される（ステップＳ５２）。最初は、ｊ＝ｊ−１＝ｌ−１となり、これによって、最上位ビット（ｄl-1）に焦点があてられる。
【００７４】
次に、乱数生成部１０２により乱数ｒ∈［−１，０，１］を生成する（ステップＳ５３）。
【００７５】
次に、制御部１０１において、乱数ｒがＮＡＦ規則を満たすか否か調べ（ステップＳ５４）、満たしている場合には、ステップＳ５５へ進み、満たしていない場合には、（該乱数ｒを破棄して）ステップＳ５３へ戻る。
【００７６】
ＮＡＦ規則を満たしていた場合には、ｄj＝ｒを実行する（ステップＳ５５）。最上位ビット（ｄl-1）に焦点があてられている場合には、ｄl-1＝ｒが実行される。ｄj＝ｒは、べき乗剰余算部１０５へ与えられる。
【００７７】
べき乗剰余算部１０５では、まず、ｙ＝ｙ2 ｍｏｄ ｎの二乗剰余演算を行う（ステップＳ５６）。
【００７８】
次に、先に決定されたＮＡＦ乱数系列の当該ビットｄj（最初のループでは、最上位ビットｄl-1）が１であるか否か調べ（ステップＳ５７）、ｄj＝１である場合には、ステップＳ５８へ進み、ｄj＝１でない場合には、ステップＳ５９へ進む。ステップＳ５７でｄj＝１でないケースで、当該ビットｄjが−１であるか否か調べ（ステップＳ５９）、ｄj＝−１である場合には、ステップＳ６０へ進む。
【００７９】
上記の分岐でｄj＝１である場合には、ｙ＝ｙ・ｘ ｍｏｄ ｎの乗算剰余を行い（ステップＳ５８）、ステップＳ６１へ進む。ｄj＝−１である場合には、ｙ＝ｙ・ｘ-1 ｍｏｄ ｎの乗算剰余を行い（ステップＳ６０）、ステップＳ６１へ進む。ここで、ｘ-1は法ｎでのｘの逆元を表している。ｄj＝１でなく且つｄj＝−１でない場合（すなわち、ｄj＝０である場合）には、何もせずに、ステップＳ６１へ進む。
【００８０】
さて、ステップＳ５７，Ｓ５９によりｄjの値に応じて３分岐した処理がステップＳ６１に集束する。
【００８１】
そして、制御部１０１において、ｊ＝０であるか否か調べ（ステップＳ６１）、ｊ≠０である場合には、ステップＳ５２へ戻り（ｊ＝ｊ−１が実行されて、１つ下位のビットに焦点があてられる）、以降、ステップＳ６１でｊ＝０となるまで繰り返し同様の処理が行われる。
【００８２】
また、ステップＳ６１でｊ＝０である場合には、求めるべき出力ｙ（＝ｘd ｍｏｄ ｎ）が得られたことになり、この処理を終了する。
【００８３】
以上のように、本実施形態によれば、べき指数としてＮＡＦ乱数系列を用いたべき乗剰余演算の出力ｙ＝ｘd ｍｏｄ ｎを得ることができる。また、図５（ｂ）のように、処理の高速化を図ることができる。
【００８４】
（第４の実施形態）
第４の実施形態に係る演算処理装置の構成例は、第３の実施形態と同様である（図６参照）。ただし、第３の実施形態は、第１の実施形態のＮＡＦ乱数系列生成装置に相当するＮＡＦ乱数系列生成部１２０に、所定の演算を行う演算部として、べき乗剰余算を行う、べき乗剰余算部１０５を追加したものであるが、第４の実施形態は、第２の実施形態のＮＡＦ乱数系列生成装置に相当するＮＡＦ乱数系列生成部１２０に、所定の演算を行う演算部として、べき乗剰余算を行う、べき乗剰余算部１０５を追加したものである（本実施形態においても、べき乗剰余算部１０５は、既存のもので構わない）。
【００８５】
本実施形態では、第２，３の実施形態と相違する点を中心に説明する。
【００８６】
図８に、本実施形態の演算処理装置において実行される、ＮＡＦ乱数系列生成及びべき乗剰余算の処理手順の一例を示す。
【００８７】
第２の実施形態と同様、生成すべきＮＡＦ乱数系列のビット長をｌとし、内部の乱数生成部１０２によって生成される乱数をｒ∈［−１，０，１］とし、生成されるＮＡＦ乱数系列をｄl-1，…，ｄ0とする。また、第３の実施形態と同様、生成されるＮＡＦ乱数系列ｄl-1，…，ｄ0の１０進数値をべき乗剰余算におけるべき指数ｄとし、べき乗される値をｘとし、剰余演算の法をｎとする。
【００８８】
この手順例は、第３の実施形態と同様、べき指数となるＮＡＦ乱数系列のビット長ｌと、べき乗される値ｘと、法ｎとを入力したとき、べき乗剰余算結果ｙ＝ｘd ｍｏｄ ｎが出力となるものであるが、その際、第２の実施形態と同様に、ＮＡＦの規則を満たす乱数系列を、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）へ向かって順に生成しながら、併せて、符号付バイナリ法を実行するものである。
【００８９】
本実施形態の演算処理装置にｌ、ｘ、ｎが入力されると、制御部１０１において、ｊ＝ｌ−１とｄj＝１とが実行され（ステップＳ７１）、これによって、最上位ビットｄl-1が１に決定される。
【００９０】
また、最上位ビットｄl-1が１であるので、べき乗剰余算部１０５において、ｙ＝（１2・ｘ）ｍｏｄ ｎ＝ｘ ｍｏｄ ｎを実行する（ステップＳ７１）。
【００９１】
以降は、ループ処理となる。
【００９２】
まず、制御部１０１において、ｊ＝ｊ−１が実行され（ステップＳ７２）、これによって、１つ下位のビットに焦点があてられる。
【００９３】
次に、記憶部１０３に記憶されている１つ前（上位）のビットｄj+1（最初のループでは、最上位ビットｄl-1）が０であるか否か調べ（ステップＳ７３）、ｄj+1≠０である場合には、ステップＳ７４へ進み、ｄj+1＝０である場合には、ステップＳ７５へ進む。
【００９４】
ステップＳ７３でｄj+1≠０である（すなわち、ｄj+1＝１ or −１である）場合には、次に来るビット値はＮＡＦ規則により必ず０となるので、ｄj＝０を実行する（ステップＳ７４）。続いて、べき乗剰余算部１０５において、二乗剰余演算ｙ＝ｙ2 ｍｏｄ ｎを実行して（ステップＳ７８）、ステップＳ８３へ進む。
【００９５】
他方、ステップＳ７３でｄj+1＝０である場合には、ＮＡＦ規則から次に取り得るビット値として［−１，０，１］の３値が候補となるので、乱数生成部１０２によって乱数ｒ∈［−１，０，１］を生成し（ステップＳ７５）、制御部１０１において、ｄj＝ｒを実行し（ステップＳ７６）、これによって、ｄjの値が決定される。次いで、べき乗剰余算部１０５において、ｙ＝ｙ2 ｍｏｄ ｎの二乗剰余演算を実行して（ステップＳ７７）、ステップＳ７９へ進む。
【００９６】
次に、べき乗剰余算部１０５において、先に決定されたＮＡＦ乱数系列の当該ｄj（最初のループでは、最上位ビットの１つ下位のビットｄl-2）が１であるか否か調べ（ステップＳ７９）、ｄj＝１である場合には、ステップＳ８１へ進み、ｄj＝１でない場合には、ステップＳ８０へ進む。ステップＳ７９でｄj＝１でないケースで、先に決定されたＮＡＦ乱数系列の最上位ビットｄjが−１であるか否か調べ（ステップＳ８０）、ｄj＝−１である場合には、ステップＳ８２へ進む。
【００９７】
上記の分岐でｄj＝１である場合には、ｙ＝ｙ・ｘ ｍｏｄ ｎの乗算剰余を行い（ステップＳ８１）、ステップＳ８３へ進む。ｄj＝−１である場合には、ｙ＝ｙ・ｘ-1 ｍｏｄ ｎの乗算剰余を行い（ステップＳ８２）、ステップＳ８３へ進む。ここで、ｘ-1は法ｎでのｘの逆元を表している。ｄj＝１でなく且つｄj＝−１でない場合（すなわち、ｄl-1＝０である場合）には、何もせずに、ステップＳ８３へ進む。
【００９８】
さて、ステップＳ７３，Ｓ７９，Ｓ８０によりｄj+1やｄjの値に応じて分岐した処理がステップＳ８３に集束する。
【００９９】
そして、制御部１０１において、ｊ＝０であるか否か調べ（ステップＳ８３）、ｊ≠０である場合には、ステップＳ７２へ戻り（ｊ＝ｊ−１が実行されて、１つ下位のビットに焦点があてられる）、以降、ステップＳ８３でｊ＝０となるまで繰り返し同様の処理が行われる。
【０１００】
また、ステップＳ８３でｊ＝０である場合には、求めるべき出力ｙ（＝ｘd ｍｏｄ ｎ）が得られたことになり、この処理を終了する。
【０１０１】
なお、上記処理手順では、生成すべきＮＡＦ乱数系列の最上位ビットについては、乱数の生成もループ処理も行わずに、１を与え、また、これに対応して、ｙ＝ｘ ｍｏｄ ｎを実行し、最上位ビット以外のビットについて、ループ処理を施すようにしたが、その代わりに、生成すべきＮＡＦ乱数系列の最上位ビット及びその１つ下位のビットについては、乱数の生成もループ処理も行わずに、それぞれ１及び０を与え、最上位ビットの１に対応して、ｙ＝ｘ ｍｏｄ ｎを実行し、最上位ビット及びその１つ下位のビット以外のビットについて、ループ処理を施すような構成も可能である。
【０１０２】
以上のように、本実施形態によれば、べき指数としてＮＡＦ乱数系列を用いたべき乗剰余演算の出力ｙ＝ｘd ｍｏｄ ｎを得ることができる。また、図５（ｂ）のように、処理の高速化を図ることができる。
【０１０３】
なお、これまで説明した実施形態では、バイナリ法を用いた例を示したが、ｗｉｎｄｏｗ法などの方法を用いても同様に実施可能である。ｗｉｎｄｏｗ法などでは、ＮＡＦ乱数系列生成装置１００（ＮＡＦ乱数系列生成部１２０）からの出力を所望のビット長ずつ処理を行うことで同様に適用することが可能である。
【０１０４】
（第５の実施形態）
第３，４の実施形態では、べき乗剰余算を例にとって説明したが、楕円曲線暗号系に用いられる楕円曲線上の点のスカラー倍算で置き換えることも可能である。
【０１０５】
第５の実施形態では、第３，４の実施形態のべき乗剰余算をスカラー倍算に置き換えた例について説明する。
【０１０６】
ここで、スカラー倍算について簡単に説明する。
【０１０７】
スカラー倍算とは、楕円曲線上の点Ｐのｄ倍を導出する処理をいい、ｄ倍された点ＰをｄＰと表す。このｄをスカラー値と呼ぶ。
【０１０８】
符号付２進数表現を用いた場合のスカラー倍算アルゴリズムは以下のようになる。  
（Ｓｔｅｐ０）  Ｉｎｐｕｔ：ｄ，Ｐ  
（Ｓｔｅｐ１）  整数ｄを、ｄ＝Σ（ｄi・２i）と２進数表現する（ｉ＝０〜ｌ−１につきそれぞれｋiを求める）。ここで、ｋi∈Ｔ，Ｔ∈［−１，０，１］とする。  
（Ｓｔｅｐ２）  Ｑ←Ｐ  
（Ｓｔｅｐ３）  ｉ＝ｌ−２から０までの間、次を繰り返す。  
（Ｓｔｅｐ３−１）  Ｑ←２Ｑ  
（Ｓｔｅｐ３−２）  ｄi＝１ならば、Ｑ←Ｑ＋Ｐ  
（Ｓｔｅｐ３−３）  ｄi＝−１ならば、Ｑ←Ｑ−Ｐ  
（Ｓｔｅｐ４）  Ｏｕｔｐｕｔ  Q（＝ｄＰ）
図９に、本実施形態の演算処理装置３００の構成例を示す。
【０１０９】
本実施形態では、演算処理装置３００は、第１の実施形態のＮＡＦ乱数系列生成装置に相当するＮＡＦ乱数系列生成部１２０に、所定の演算を行う演算部１０６を追加した構成になっている。本実施形態では、演算部１０６は、スカラー倍算を行うスカラー倍算部である（スカラー倍算部は、既存のもので構わない）。
【０１１０】
本実施形態では、第１，３の実施形態と相違する点を中心に説明する。
【０１１１】
図１０に、本実施形態の演算処理装置において実行される、ＮＡＦ乱数系列生成及びスカラー倍算の処理手順の一例を示す。
【０１１２】
これまでの実施形態と同様、生成すべきＮＡＦ乱数系列のビット長をｌとし、内部の乱数生成部１０２によって生成される乱数をｒ∈［−１，０，１］とし、生成されるＮＡＦ乱数系列をｄl-1，…，ｄ0とする。
【０１１３】
この手順例は、スカラー値となるＮＡＦ乱数系列のビット長ｌと、スカラー倍される点Ｐとを入力したとき、スカラー倍算結果Q＝ｄＰが出力となるものであるが、その際、第１，３の実施形態と同様に、ＮＡＦの規則を満たす乱数系列を、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）へ向かって順に生成しながら、併せて、スカラー倍算を実行するものである。
【０１１４】
本実施形態の演算処理装置にｌ、Ｐが入力されると、制御部１０１において、ｊ＝ｌが実行され、スカラー倍算部１０６において、Ｑ←Οが実行される（ステップＳ９１）。ここで、Οは無限遠点を表し、有限体上の楕円曲線の単位元である（例、P+(-P)=Ο、P+Ο＝-P）。
【０１１５】
以降は、ループ処理となる。
【０１１６】
まず、ｊ＝ｊ−１が実行される（ステップＳ９２）。最初は、ｊ＝ｊ−１＝ｌ−１となり、これによって、最上位ビット（ｄl-1）に焦点があてられる。
【０１１７】
次に、乱数生成部１０２により乱数ｒ∈［−１，０，１］を生成する（ステップＳ９３）。
【０１１８】
次に、制御部１０１において、乱数ｒがＮＡＦ規則を満たすか否か調べ（ステップＳ９４）、満たしている場合には、ステップＳ９５へ進み、満たしていない場合には、（該乱数ｒを破棄して）ステップＳ９３へ戻る。
【０１１９】
ＮＡＦ規則を満たしていた場合には、ｄj＝ｒを実行する（ステップＳ９５）。最上位ビット（ｄl-1）に焦点があてられている場合には、ｄl-1＝ｒが実行される。ｄj＝ｒは、スカラー倍算部１０６へ与えられる。
【０１２０】
スカラー倍算部１０６では、まず、Ｑ←２Ｑの点２倍算を行う（ステップＳ９６）。
【０１２１】
次に、先に決定されたＮＡＦ乱数系列の当該ビットｄj（最初のループでは、最上位ビットｄl-1）が１であるか否か調べ（ステップＳ９７）、ｄj＝１である場合には、ステップＳ９８へ進み、ｄj＝１でない場合には、ステップＳ９９へ進む。ステップＳ９７でｄj＝１でないケースで、先に決定されたＮＡＦ乱数系列の最上位ビットｄjが−１であるか否か調べ（ステップＳ９９）、ｄj＝−１である場合には、ステップＳ１００へ進む。
【０１２２】
上記の分岐でｄj＝１である場合には、Ｑ←Ｑ＋Ｐの点加算を行い（ステップＳ９８）、ステップＳ１０１へ進む。ｄj＝−１である場合には、Ｑ←Ｑ−Ｐの点減算を行い（ステップＳ１００）、ステップＳ１０１へ進む。ここで、−ＰはＰの逆元を表している。ｄj＝１でなく且つｄj＝−１でない場合（すなわち、ｄj＝０である場合）には、何もせずに、ステップＳ１０１へ進む。
【０１２３】
さて、ステップＳ９７，Ｓ９９によりｄjの値に応じて３分岐した処理がステップＳ１０１に集束する。
【０１２４】
そして、制御部１０１において、ｊ＝０であるか否か調べ（ステップＳ１０１）、ｊ≠０である場合には、ステップＳ９２へ戻り（ｊ＝ｊ−１が実行されて、１つ下位のビットに焦点があてられる）、以降、ステップＳ１０１でｊ＝０となるまで繰り返し同様の処理が行われる。
【０１２５】
また、ステップＳ１０１でｊ＝０である場合には、求めるべき出力Q（＝ｄＰ）が得られたことになり、この処理を終了する。
【０１２６】
以上のように、本実施形態によれば、べき指数としてＮＡＦ乱数系列を用いたスカラー倍算の出力Q＝ｄＰを得ることができる。また、図５（ｂ）のように、処理の高速化を図ることができる。
【０１２７】
ここでは、スカラー倍算部１０６において最上位ビットから処理を行う方法を示したが、最上位ビットが必ず１であることを利用して、上に示したスカラー倍算アルゴリズムのように、初めにQ←Pとし、最上位ビットの次のビットから処理を行う方法も考えられる。
【０１２８】
なお、本実施形態では、第１の実施形態のＮＡＦ乱数系列生成装置（に相当するＮＡＦ乱数系列生成部１２０）に、所定の演算を行う演算部としてスカラー倍算を行うスカラー倍算部を組み合わせた演算処理装置を例にとって説明したが、第４の実施形態と同様に、第２の実施形態のＮＡＦ乱数系列生成装置（に相当するＮＡＦ乱数系列生成部１２０）に、スカラー倍算部を組み合わせた演算処理装置も実施可能である。
【０１２９】
また、第１或いは第２の実施形態のＮＡＦ乱数系列生成装置に、所定の演算を行う演算部として、スカラー倍算及びべき乗剰余算部以外の演算を行う装置（その演算の過程において、ＮＡＦ乱数系列生成装置により生成された乱数系列を、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）へ向かって順に１ビット又は所定の複数ビットを使用するもの）を組み合わせた演算処理装置も実施可能である。
【０１３０】
（バリエーション）
ところで、これまでの説明において、本実施形態のＮＡＦ乱数系列生成装置１００において、乱数生成部１０２で生成される［−１，０，１］の３値の発生確率をある一定の比率に変更することで、生成されるＮＡＦ乱数系列の特性を変更するができるようになる。
【０１３１】
例えば、図４のステップＳ４５等において、１つ前（上位）のビット値が０であった場合に、次に取り得るビット値として［−１，０，１］の３値が候補となるが、乱数生成部１０２の出力である３値の乱数ｒ∈［−１，０，１］の発生確率をそれぞれ１／４，１／２，１／４などとする方法が考えられる。０の発生確率が高いと、生成されるＮＡＦ乱数系列の非ゼロ係数の数が減少する傾向が見られると予想される。
【０１３２】
図２のステップＳ２３や図４のステップＳ４５等において、乱数生成部１０２からの出力の発生確率を任意の比率に変更する方法としては種々のバリエーションが考えられるが、例えば、乱数生成部１０２から出力される２ビット系列が００あるいは１１ならば０、０１ならば１、１０ならば−１と決定することで、３値の乱数ｒ∈［−１，０，１］の発生確率をそれぞれ１／４，１／２，１／４とすることで実現可能である。
【０１３３】
なお、以上の各機能は、ソフトウェアとして記述し適当な機構をもったコンピュータに処理させても実現可能である。  
また、本実施形態は、コンピュータに所定の手順を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるためのプログラムとして実施することもできる。加えて該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【０１３４】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１３５】
【図１】本発明の第１及び第２の実施形態に係るＮＡＦ乱数系列生成装置の構成例を示す図
【図２】本発明の第１の実施形態に係るＮＡＦ乱数系列生成装置の処理手順の一例を示すフローチャート
【図３】ＮＡＦ規則を満たすか否かについて判定する処理手順の一例を示すフローチャート
【図４】本発明の第２の実施形態に係るＮＡＦ乱数系列生成装置の処理手順の一例を示すフローチャート
【図５】ＮＡＦ乱数系列生成及びこれに続いて又はこれと並行して行われる演算について説明するための図
【図６】本発明の第３及び第４の実施形態に係る演算処理装置の構成例を示す図
【図７】本発明の第３の実施形態に係る演算処理装置の処理手順の一例を示すフローチャート
【図８】本発明の第４の実施形態に係る演算処理装置の処理手順の一例を示すフローチャート
【図９】本発明の第５の実施形態に係る演算処理装置の構成例を示す図
【図１０】本発明の第５の実施形態に係る演算処理装置の処理手順の一例を示すフローチャート
【符号の説明】
【０１３６】
１００…ＮＡＦ乱数系列生成装置、１０２…乱数生成部、１０１…制御部、１０３…記憶部、１０４…出力部、１０５…演算部、１０６…スカラー倍算部、１２０…ＮＡＦ乱数系列生成部、２００，３００…演算処理装置
【図１】
0004398904.tif 000002
【図２】
0004398904.tif 000003
【図３】
0004398904.tif 000004
【図４】
0004398904.tif 000005
【図５】
0004398904.tif 000006
【図６】
0004398904.tif 000007
【図７】
0004398904.tif 000008
【図８】
0004398904.tif 000009
【図９】
0004398904.tif 000010
【図１０】
0004398904.tif 000011