米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 株式会社東芝

発明の名称 乱数系列生成装置、乱数系列生成方法、演算処理装置、演算処理方法及びプログラム
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2007−4268(P2007−4268A)
公開日 平成19年1月11日(2007.1.11)
出願番号 特願2005−180747(P2005−180747)
出願日 平成17年6月21日(2005.6.21)
代理人 【識別番号】100058479
【弁理士】
【氏名又は名称】鈴江 武彦
発明者 三宅 秀享 / 清水 秀夫
要約 課題
より効率的に、符号付2進数表現された乱数系列を生成できる乱数系列生成装置を提供すること。

解決手段
乱数生成部102は、−1、0又は1をとる3値の乱数を生成する。制御部101は、乱数生成部102により生成された乱数を、それまでの生成途中の乱数系列のその時点における最下位ビットとして連結したならば、これによって得られた乱数系列が「最上位ビットについては1をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが0の場合には−1と0と1のいずれをとることも許され、その上位ビットが−1又は1の場合には0をとることのみ許される」という条件を満たすものになるか否かを調べ、満たすものになる場合に、該乱数を、該それまでの生成途中の乱数系列のその時点における最下位ビットとして連結する処理を、繰り返し行うことによって、任意のビット長の乱数系列を生成する。
特許請求の範囲
【請求項1】
最上位ビットについては1をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが0の場合には−1と0と1のいずれをとることも許され、その上位ビットが−1又は1の場合には0をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成装置であって、
−1、0又は1をとる3値の乱数を生成する3値乱数生成手段と、
前記条件に基づいて、前記3値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成手段とを備えたことを特徴とする乱数系列生成装置。
【請求項2】
前記乱数系列生成手段は、
前記3値乱数生成手段により生成された乱数を、それまでに生成した前記乱数系列のその時点における最下位ビットとして連結したならば、これによって得られた乱数系列が前記条件を満たすものになるか否かを調べ、満たすものになる場合に、該乱数を、該それまでに生成した前記乱数系列のその時点における最下位ビットとして連結する処理を、繰り返し行うことによって、前記任意のビット長の乱数系列を生成することを特徴とする請求項1に記載の乱数系列生成装置。
【請求項3】
前記乱数系列生成手段は、
生成すべき前記任意のビット長の乱数系列の最上位ビットについて、前記3値乱数生成手段により生成される乱数を用いることなく、1を与え、生成すべき前記任意のビット長の乱数系列の最上位ビット以外の各ビットについて、最上位ビットの1つ下位のビットから最下位ビットへ向かって順に、当該ビットの上位ビットが−1又は1である場合には、前記3値乱数生成手段により生成される乱数を用いることなく、当該ビットとして0を与え、当該ビットの上位ビットが0である場合には、前記3値乱数生成手段により生成された乱数を、当該ビットの値として用いることによって、前記任意のビット長の乱数系列を生成することを特徴とする請求項1に記載の乱数系列生成装置。
【請求項4】
前記乱数系列生成手段は、
生成すべき前記任意のビット長の乱数系列の最上位ビットについて、前記3値乱数生成手段により生成される乱数を用いることなく、1を与え、生成すべき前記任意のビット長の乱数系列の最上位ビットの1つ下位のビットについて、前記3値乱数生成手段により生成される乱数を用いることなく、0を与え、生成すべき前記任意のビット長の乱数系列の最上位ビット及び最上位ビットの1つ下位のビット以外の各ビットについて、最上位ビットの1つ下位のビットから最下位ビットへ向かって順に、当該ビットの上位ビットが−1又は1である場合には、前記3値乱数生成手段により生成される乱数を用いることなく、当該ビットとして0を与え、当該ビットの上位ビットが0である場合には、前記3値乱数生成手段により生成された乱数を、当該ビットの値として用いることによって、前記任意のビット長の乱数系列を生成することを特徴とする請求項1に記載の乱数系列生成装置。
【請求項5】
前記3値乱数生成手段が前記乱数を生成するにあたっての−1の発生確率と0の発生確率と1の発生確率との比率を特定の比率とすることを特徴とする請求項1ないし4のいずれか1項に記載の乱数系列生成装置。
【請求項6】
前記乱数系列生成手段により生成された前記乱数系列を、最上位ビットから最下位ビットへ向かって順に、1ビット又は複数ビットずつ逐次出力する主力手段を更に備えたことを特徴とする請求項1ないし5のいずれか1項に記載の乱数系列生成装置。
【請求項7】
最上位ビットについては1をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが0の場合には−1と0と1のいずれをとることも許され、その上位ビットが−1又は1の場合には0をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成装置における乱数系列生成方法であって、
−1、0又は1をとる3値の乱数を生成する3値乱数生成ステップと、
前記条件に基づいて、前記3値乱数生成ステップにより逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成ステップとを有することを特徴とする乱数系列生成方法。
【請求項8】
最上位ビットについては1をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが0の場合には−1と0と1のいずれをとることも許され、その上位ビットが−1又は1の場合には0をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成装置としてコンピュータを機能させるためのプログラムにおいて、
前記プログラムは、
−1、0又は1をとる3値の乱数を生成する3値乱数生成ステップと、
前記条件に基づいて、前記3値乱数生成ステップにより逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成ステップとをコンピュータに実行させることを特徴とするプログラム。
【請求項9】
最上位ビットについては1をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが0の場合には−1と0と1のいずれをとることも許され、その上位ビットが−1又は1の場合には0をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成部と、該乱数系列をべき指数として使用する演算を行う演算部とを備えた演算処理装置であって、
前記乱数系列生成部は、
−1、0又は1をとる3値の乱数を生成する3値乱数生成手段と、
前記条件に基づいて、前記3値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成手段とを有するものであり、
前記演算部は、前記乱数系列生成手段による前記乱数系列の生成と並行して、前記乱数系列生成手段により生成された前記乱数系列を、その最上位ビットから最下位ビットへ向かって1又は複数ビットずつ順に使用しながら、特定の繰り返し処理を行う手段を有するものであることを特徴とする演算処理装置。
【請求項10】
前記演算は、べき乗剰余算又は楕円曲線暗号のスカラー倍算であることを特徴とする請求項9に記載の演算処理装置。
【請求項11】
最上位ビットについては1をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが0の場合には−1と0と1のいずれをとることも許され、その上位ビットが−1又は1の場合には0をとることのみ許される条件を満たす乱数系列を生成するとともに、該乱数系列をべき指数として使用する演算を行う演算処理装置における演算処理方法であって、
−1、0又は1をとる3値の乱数を生成する3値乱数生成ステップと、
前記条件に基づいて、前記3値乱数生成ステップにより逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成ステップと、
前記乱数系列生成ステップによる前記乱数系列の生成と並行して、前記乱数系列生成ステップにより生成された前記乱数系列を、その最上位ビットから最下位ビットへ向かって1又は複数ビットずつ順に使用しながら、特定の繰り返し処理を行うステップとを有することを特徴とする演算処理方法。
【請求項12】
最上位ビットについては1をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが0の場合には−1と0と1のいずれをとることも許され、その上位ビットが−1又は1の場合には0をとることのみ許される条件を満たす乱数系列を生成するとともに、該乱数系列をべき指数として使用する演算を行う演算処理装置としてコンピュータを機能させるためのプログラムにおいて、
前記プログラムは、
−1、0又は1をとる3値の乱数を生成する3値乱数生成ステップと、
前記条件に基づいて、前記3値乱数生成ステップにより逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成ステップと、
前記乱数系列生成ステップによる前記乱数系列の生成と並行して、前記乱数系列生成ステップにより生成された前記乱数系列を、その最上位ビットから最下位ビットへ向かって1又は複数ビットずつ順に使用しながら、特定の繰り返し処理を行うステップとをコンピュータに実行させることを特徴とするプログラム。
発明の詳細な説明
【技術分野】
【0001】
本発明は、乱数系列を生成する乱数系列生成装置及び乱数系列生成方法、べき乗剰余算やスカラー倍算などの演算を行う演算処理装置及び演算処理方法、並びにプログラムに関する。
【背景技術】
【0002】
公開鍵暗号方式やディジタル署名方式では、べき乗剰余算やスカラー倍算といった演算を用いるものが多く存在する。べき乗剰余算とは、y=xk mod nのような演算であり、ElGamal暗号やRSA暗号などに用いられている。スカラー倍算とは、楕円曲線暗号系に用いられる演算で、楕円曲線上の、べき倍算Y=kXのことを言う。
【0003】
公開鍵暗号では1024ビットなどの大きなデータを扱うため、NAFなどの符号付整数を利用した冗長表現(バイナリ表現など)と、バイナリ法(Binary法(Double-and-ADD method))やwindow法などといったテクニックを組み合わせることによって、べき乗剰余算やスカラー倍算を効率的に行う様々な方法が知られている。
【0004】
以下に、バイナリ法のアルゴリズムを示す。
[バイナリ法]
(Step0) Input k,x,n
(Step1) 整数kを、k=Σ(ki・2i)と2進数表現する(i=0〜l−1につきそれぞれkiを求める)。ここで、ki∈T,T=[0,1]とする。
(Step2) y=1
(Step3) i=l−1から0までの間、次を繰り返す。
(Step3−1) y=y2 (mod n)
(Step3−2) ki=1ならば、y=y・x (mod n)
(Step4) Output y(=xk mod n)
バイナリ法などのビットの0,1の値に依存した演算アルゴリズムでは、べき指数を2進数表現したときのハミング重みが小さいほど計算量が少なくなることが分かっている。
【0005】
上記のようなバイナリ表現に関しては、符号無し2進数表現(T=[0,1])は一意的に決まるが、符号付2進数表現(T=[−1,0,1])は一意的には決定しないという性質がある。なお、以下で用いる“-1”は“−1”を表すものとする。
【0006】
例えば、k=181のとき、T=[0,1]ならば、181=10110101である(一意的である)。これに対して、T=[−1,0,1]ならば、181=1-110-11-11-1=1-11-110101=…である(一意的でない)。
【0007】
この符号付2進数表現において、非ゼロ係数の数を最小にする方法として、NAF表現が知られている。
【0008】
NAF表現とは、全てのi≧0に対してki×ki+1=0となるような符号付2進数表現のことを言い、任意の正整数に変換アルゴリズムを作用させることで一意的に表現することができる。NAF変換アルゴリズムの実装方法はいくつか考えられる。
【0009】
以下に、基本的なNAF変換アルゴリズムを示す。
[NAF変換アルゴリズム]
Input n
k←n
S←< >
while k>0
If k:odd u←2−(k mod 4)
else u←0
k←k−u
Prepend u to S
k←k/2
end while
Output S
例えば、正整数n=181のとき、符号付2進数表現S=10-10-10101が得られる。
【0010】
さらに、バイナリ法を符号付2進数表現に拡張した符号付バイナリ法のアルゴリズムが知られている。
【0011】
以下に、符号付バイナリ法のアルゴリズムを示す。なお、下記のx-1は、xの法nにおける逆元を表している。
[符号付バイナリ法]
(Step0) Input k,x,n
(Step1) 整数kを、k=Σ(ki・2i)と2進数表現する(i=0〜l−1につきそれぞれkiを求める)。ここで、ki∈T,T=[−1,0,1]とする。
(Step2) y=1
(Step3) i=l−1から0までの間、次を繰り返す。
(Step3−1) y=y2 (mod n)
(Step3−2) ki=1ならば、y=y・x (mod n)
(Step3−3) ki=−1ならば、y=y・x-1 (mod n)
(Step4) Output y(=xk mod n)
これらの符号付バイナリ法やNAF表現といったテクニックを用いることで、べき乗剰余算やスカラー倍算が効率よく演算できることになる。例えば、非特許文献1,2参照には、NAFを用いると非ゼロ係数の数が全体の約1/3となり(ゼロの数は約2/3)、べき乗剰余算(あるいはスカラー倍算)の計算量に関しては、NAFを用いない場合と比べて約11%効率化が図れる旨が記述されている。
【0012】
他方、公開鍵暗号方式やディジタル署名方式では、標準プロトコルの中で、乱数を生成し、生成した乱数をべき指数としてべき乗剰余算を行うことが多くある。例えば、ElGamal暗号やDH鍵共有法、DSA署名などである。
【0013】
それらの標準プロトコルにおいて、乱数とNAF表現を利用したべき乗剰余算処理部分は、次の3ステップから構成される(なお、kとdは同値の整数である)。
(Step1) 乱数kを生成する。
(Step2) kのNAF変換d=NAF(k)を行う。
(Step3) べき乗剰余算y=xd mod nを計算する。
【非特許文献1】CRYPTOGRAPHY Theory and Practice SECOND EDITION(pp.258-259), Author: Douglas Stinson, Publisher: Chapman & Hall/CRC, ISBN: 1-58488-206-9
【非特許文献2】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
【発明の開示】
【発明が解決しようとする課題】
【0014】
バイナリ表現への変換処理を行い、符号付2進数表現を生成することに関して、特定の値をバイナリ変換し非ゼロ係数の数を削減することには意味があるが、乱数のようなランダムな値を変換する際には、変換処理を行う必要は無く、さらに効率良く符号付2進数表現された乱数系列を生成できる可能性が考えられる。
【0015】
また、NAF変換アルゴリズムでは、最下位ビット(LSB)から最上位ビット(MSB)へと1桁ごとに変換していく必要があるが、最上位ビット(MSB)から最下位ビット(LSB)へ計算していく、べき乗剰余算やスカラー倍算等の演算方法との併用をすると、変換処理の重複を招き、結果的に演算処理時間が長くなるという欠点を持っている。
【0016】
本発明は、上記事情を考慮してなされたもので、より効率的に、符号付2進数表現された乱数系列を生成できる乱数系列生成装置及び乱数系列生成方法、より効率的に、符号付2進数表現された乱数系列を生成するとともに、該乱数系列をべき指数として使用して、べき乗剰余算やスカラー倍算などの演算を行うことができる演算処理装置及び演算処理方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【0017】
本発明は、最上位ビットについては1をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが0の場合には−1と0と1のいずれをとることも許され、その上位ビットが−1又は1の場合には0をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成装置であって、−1、0又は1をとる3値の乱数を生成する3値乱数生成手段と、前記条件に基づいて、前記3値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成手段とを備えたことを特徴とする。
また、本発明は、最上位ビットについては1をとることのみ許され、最上位ビット以外のビットについては、その上位ビットが0の場合には−1と0と1のいずれをとることも許され、その上位ビットが−1又は1の場合には0をとることのみ許される条件を満たす乱数系列を生成する乱数系列生成部と、該乱数系列をべき指数として使用する演算を行う演算部とを備えた演算処理装置であって、前記乱数系列生成部は、−1、0又は1をとる3値の乱数を生成する3値乱数生成手段と、前記条件に基づいて、前記3値乱数生成手段により逐次生成される乱数の全部又は一部をその生成順に用いながら、生成すべき任意のビット長の乱数系列の最上位ビットから最下位ビットへ向かって順に各ビットの値を決定していくことによって、前記条件を満たす乱数系列を生成する乱数系列生成手段とを有するものであり、前記演算部は、前記乱数系列生成手段による前記乱数系列の生成と並行して、前記乱数系列生成手段により生成された前記乱数系列を、その最上位ビットから最下位ビットへ向かって1又は複数ビットずつ順に使用しながら、特定の繰り返し処理を行う手段を有するものであることを特徴とする。
【0018】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る本発明は装置に係る発明としても成立する。
また、装置または方法に係る本発明は、コンピュータに当該発明に相当する手順を実行させるための(あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための)プログラムとしても成立し、該プログラムを記録したコンピュータ読み取り可能な記録媒体としても成立する。
【発明の効果】
【0019】
本発明によれば、より効率的に、符号付2進数表現された乱数系列を生成することができる。また、本発明によれば、より効率的に、符号付2進数表現された乱数系列を生成するとともに、該乱数系列をべき指数として使用して、べき乗剰余算やスカラー倍算などの演算を行うことができる。
【発明を実施するための最良の形態】
【0020】
以下、図面を参照しながら本発明の実施形態について説明する。
【0021】
(第1の実施形態)
図1に、本発明の第1の実施形態に係るNAF乱数系列生成装置の構成例を示す。
【0022】
図1に示されるように、NAF乱数系列生成装置100は、制御部101、乱数系列生成部102、記憶部103、出力部104を備えている。
【0023】
NAF乱数系列生成装置100は、例えば、ICチップなどの暗号モジュール内に組み込まれ、暗号化、復号化、鍵生成又は署名生成などの際に、任意の正整数値lを入力すると、NAFの規則に従ったlビットの乱数系列(符号付2進数表現)を生成し、出力する。
【0024】
乱数生成部102は、[−1,0,1]の3値からなる乱数を生成する機能を有する。
【0025】
制御部101は、本NAF乱数系列生成装置100により生成される乱数系列がNAF規則を満たすように制御する機能を有する。
【0026】
記憶部103は、少なくとも1つ前に生成された乱数ビットを記憶しておく機能を有する。なお、新たに生成されたものから順にu(uは予め定められた複数)ビットを記憶する構成や、生成された全ビット列を記憶する構成も可能である。
【0027】
出力部104は、記憶部103に蓄積されているNAF乱数ビットを、生成された順に(最上位ビットから最下位ビットへ向かって順に)、1ビットずつ逐次出力していく機能を有する。なお、記憶部103に蓄積されているNAF乱数ビットを、生成された順に(最上位ビットから最下位ビットへ向かって順に)、s(sは予め定められた複数)ビットずつ逐次出力していく構成や、NAF乱数系列の全ビットの生成が完了した後に、該NAF乱数系列の全ビットを出力する構成も可能である。また、出力部104が1回に出力する乱数ビット数を、設定あるいはその都度指示できるようにしてもよい。
【0028】
ここで、NAFの規則は、例えば、下記のような2つの規則(条件)で表現することができる。
(a)当該乱数系列において、最上位ビットは、1であることのみ許される。
(b)当該乱数系列において、非ゼロのビット同士が隣接することは、許されない(0と0が隣接すること、0と1が隣接すること、0と−1が隣接することは、いずれも許されるが、1と1が隣接すること、1と−1が隣接すること、及び−1と−1が隣接することは、いずれも許されない)。
【0029】
また、本実施形態において乱数系列を最上位ビットから最下位ビットへ向かって順番に生成することを考慮すると、NAFの規則は、例えば、下記のように表現することもできる。
(A)当該乱数系列において、最上位ビットは、1をとることのみ許される。
(B)当該乱数系列において、最上位ビット以外のビットは、そのビットの上位ビットが0の場合には−1と0と1のいずれをとることも許され、そのビットの上位ビットが−1又は1の場合には0をとることのみ許される。
【0030】
図2に、本実施形態のNAF乱数系列生成装置において実行される、NAFの規則を満たす乱数系列を、最上位ビット(MSB)から最下位ビット(LSB)へ向かって順に生成する処理手順の一例を示す。
【0031】
ここでは、生成すべきNAF乱数系列のビット長をlとし、内部の乱数生成部102によって生成される乱数をr∈[−1,0,1]とし、生成されるNAF乱数系列をdl-1,…,d0とする。
【0032】
本実施形態のNAF乱数系列生成装置にlが入力されると、制御部101において、j=lが実行される(ステップS21)。
【0033】
以降は、ループ処理となる。
【0034】
まず、j=j−1が実行される(ステップS22)。最初は、j=j−1=l−1となり、これによって、最上位ビット(dl-1)に焦点があてられる。
【0035】
次に、乱数生成部102により乱数r∈[−1,0,1]を生成する(ステップS23)。生成された乱数r∈[−1,0,1]は、制御部101により受け取られる。
【0036】
次に、制御部101において、乱数rがNAF規則を満たすか否か調べ(ステップS24)、満たしている場合には、ステップS25へ進み、満たしていない場合には、(該乱数rを破棄して)ステップS23へ戻る。NAF規則を満たすか否かを判定するアルゴリズムについては後述する。
【0037】
NAF規則を満たしていた場合には、dj=rを実行する(ステップS25)。最上位ビット(dl-1)に焦点があてられる場合には、dl-1=rが実行される。dj=rは、記憶部103に記憶され、出力部104により出力される。
【0038】
ここで、j=0であるか否か調べ(ステップS26)、j≠0である場合には、ステップS22へ戻り(j=j−1が実行されて、1つ下位のビットに焦点があてられる)、以降、ステップS26でj=0となるまで繰り返し同様の処理が行われる。
【0039】
また、ステップS26でj=0である場合には、lビットのNAF乱数系列が全て決定されたことになり、この処理を終了する。
【0040】
なお、上記手順例において、乱数生成部102の動作とステップS23の動作とは同期している(ステップS23の実行タイミングにおいてのみ、乱数生成部102が動作する)ものであってもよいが、必ずしも同期している必要はなく、乱数生成部102は周囲の動作とは独立に常に乱数を発生し続ける形態も可能である。
【0041】
ここで、上記のようなNAF規則を満たすか否かを判定するアルゴリズムについて説明する。
【0042】
図3に、生成された乱数rを乱数系列の当該ビットに採用した場合にNAF規則が満されるか否かについて判定する手順の一例を示す。
【0043】
まず、j=l−1であるか否か(つまり、最上位ビットであるか否か)を判定する(ステップS31)。j=l−1である(最上位ビットである)場合には、ステップS32へ進み、j≠l−1である(最上位ビットでない)場合には、ステップS33へ進む。
【0044】
ステップS31でj=l−1である場合には、NAF規則によれば最上位ビットdl-1は1しか許されないので、(図2のステップS23で得られた)乱数rが1であるか否かを調べ(ステップS32)、r=1であるときは、「rがNAF規則を満たす」旨の判定結果とし、r≠1であるときは、「rがNAF規則を満たさない」旨の判定結果とする。
【0045】
他方、ステップS31でj≠l−1である(最上位ビットでない)場合には、1つ前(1つ上位)のビットdj+1が0であるか否かを調べ(ステップS33)、dj+1=0であるときは、NAF規則によればrが[−1,0,1]のいずれの値を取ってもdj=rとして許されるので(rの値を調べることなく)、「rはNAF規則を満たす」旨を判定結果とする。また、dj+1≠0であるときは、NAF規則によればdj=0しか許されないため、r=0であるか否かを調べ(ステップS34)、r=0であれば「rはNAF規則を満たす」旨の判定結果とし、r≠0であれば「rがNAF規則を満たさない」旨の判定結果とする。
【0046】
以上のように、本実施形態によれば、NAF規則を満たすようなNAF乱数系列を生成することが可能となる。
【0047】
(第2の実施形態)
第1の実施形態は、NAF規則を満たす乱数が発生されるまでループを繰り返す処理があるため、全lビットのNAF乱数系列が決定するまでの時間は不確定となるものであるが、第2の実施形態は、全lビットのNAF乱数系列が決定するまでの時間をほぼ一定とするものである。
【0048】
本実施形態では、第1の実施形態と相違する点を中心に説明する。
【0049】
本実施形態に係るNAF乱数系列生成装置の構成例は、第1の実施形態と同様である(図1参照)。
【0050】
図4に、本実施形態のNAF乱数系列生成装置において実行される、NAFの規則を満たす乱数系列を、最上位ビット(MSB)から最下位ビット(LSB)へ向かって順に生成する処理手順の一例を示す。
【0051】
第1の実施形態と同様、生成すべきNAF乱数系列のビット長をlとし、内部の乱数生成部102によって生成される乱数をr∈[−1,0,1]とし、生成されるNAF乱数系列をdl-1,…,d0とする。
【0052】
本実施形態のNAF乱数系列生成装置にlが入力されると、制御部101において、まず、j=l−1とdj=1とが実行され(ステップS41)、これによって、最上位ビットが決定される。この最上位ビットdl-1=1は、記憶部103に記憶され、出力部104により出力される。
【0053】
以降は、ループ処理となる。
【0054】
まず、j=j−1が実行され(ステップS42)、これによって、1つ下位のビットに焦点があてられる。
【0055】
次に、記憶部103に記憶されている1つ前(上位)のビットdj+1(最初のループでは、最上位ビットdl-1)が0であるか否か調べ(ステップS43)、dj+1≠0である場合には、ステップS44へ進み、dj+1=0である場合には、ステップS45へ進む。
【0056】
ステップS43でdj+1≠0である(すなわち、dj+1=1 or −1である)場合には、次に来るビット値はNAF規則により必ず0となるので、dj=0を実行して(ステップS44)、ステップS47へ進む。dj=0は、記憶部103に記憶され、出力部104で出力される。
【0057】
他方、ステップS43でdj+1=0である場合には、NAF規則から次に取り得るビット値として[−1,0,1]の3値が候補となるので、乱数生成部102によって乱数r∈[−1,0,1]を生成し(ステップS45)、次いで、dj=rを実行して(ステップS46)、ステップS47へ進む。dj=rは、記憶部103に記憶され、出力部104で出力される。
【0058】
ここで、j=0であるか否か調べ(ステップS47)、j≠0である場合には、ステップS42へ戻り(j=j−1が実行されて、1つ下位のビットに焦点があてられる)、以降、ステップS47でj=0となるまで繰り返し同様の処理が行われる。
【0059】
また、ステップS47でj=0である場合には、lビットのNAF乱数系列が全て決定されたことになり、この処理を終了する。
【0060】
なお、上記処理手順では、生成すべきNAF乱数系列の最上位ビットについては、乱数の生成もループ処理も行わずに、1を与え、最上位ビット以外のビットについて、ループ処理を施すようにしたが、その代わりに、生成すべきNAF乱数系列の最上位ビット及びその1つ下位のビットについては、乱数の生成もループ処理も行わずに、それぞれ1及び0を与え、最上位ビット及びその1つ下位のビット以外のビットについて、ループ処理を施すような構成も可能である。
【0061】
以上のように、本実施形態によれば、NAF規則を満たすようなNAF乱数系列を生成することが可能となる。
【0062】
べき指数として乱数系列を使用するようなべき乗剰余算やスカラー倍算等の演算を行うにあたって、従来は、乱数系列の生成が全て完了した後に、該乱数系列に対してNAF変換を施し、その後に、該NAF変換した乱数系列を用いた、べき乗剰余算を行う、という手順を踏む必要があったが、第1,2の実施形態によれば、図5(a)のように、NAF乱数系列生成装置において、直接、NAF乱数系列を生成し、これを、べき乗剰余算やスカラー倍算等の演算を行う演算装置に与えることができるので、処理の高速化を図ることができる。また、図5(a)のように、NAF乱数系列を全て生成してから、べき乗剰余算やスカラー倍算等の演算を行う代わりに、図5(b)のように、NAF乱数系列生成装置において、NAF乱数系列を、最上位ビット(MSB)から最下位ビット(LSB)へ向かって順に生成し、生成した乱数ビットをべき乗剰余算やスカラー倍算等の演算を行う演算装置に与えるとともに、これに並行して、演算装置において、べき乗剰余算やスカラー倍算等の演算を行うことができるようになるので、この場合には、さらに、処理の高速化を図ることができる。
【0063】
ところで、第1の実施形態又は第2の実施形態のNAF乱数系列生成装置と、数値系列の最上位ビット(MSB)から最下位ビット(LSB)へ向かって順に1ビット又は所定の複数ビットを使用して所定の演算を行う装置と組み合わせて、演算処理装置を構成することも可能である。
【0064】
以下、第3及び第4の実施形態では、この所定の演算を行う装置として、べき乗剰余算装置を用いる場合を例にとって説明し、第5の実施形態では、スカラー倍算装置を用いる場合を例にとって説明する。
【0065】
(第3の実施形態)
図6に、第3の実施形態の演算処理装置200の構成例を示す。
【0066】
本実施形態の演算処理装置200は、第1の実施形態のNAF乱数系列生成装置に相当するNAF乱数系列生成部120に、所定の演算を行う演算部として、べき乗剰余算を行う、べき乗剰余算部105を追加した構成になっている。なお、べき乗剰余算部105は、既存のもので構わない。
【0067】
本実施形態では、第1の実施形態と相違する点を中心に説明する。
【0068】
図7に、本実施形態の演算処理装置において実行される、NAF乱数系列生成及びべき乗剰余算の処理手順の一例を示す。
【0069】
第1の実施形態と同様、生成すべきNAF乱数系列のビット長をlとし、内部の乱数生成部102によって生成される乱数をr∈[−1,0,1]とし、生成されるNAF乱数系列をdl-1,…,d0とする。また、本実施形態では、生成されるNAF乱数系列dl-1,…,d0の10進数値をべき乗剰余算におけるべき指数dとし、べき乗される値をxとし、剰余演算の法をnとする。
【0070】
この手順例は、べき指数となるNAF乱数系列のビット長lと、べき乗される値xと、法n(n:prime)とを入力したとき、べき乗剰余算結果y=xd mod nが出力となるものであるが、その際、第1の実施形態と同様に、NAFの規則を満たす乱数系列を、最上位ビット(MSB)から最下位ビット(LSB)へ向かって順に生成しながら、併せて、符号付バイナリ法を実行するものである。
【0071】
本実施形態の演算処理装置にl、x、nが入力されると、制御部101において、j=lが実行され、べき乗剰余算部105において、y=1が実行される(ステップS51)。
【0072】
以降は、ループ処理となる。
【0073】
まず、j=j−1が実行される(ステップS52)。最初は、j=j−1=l−1となり、これによって、最上位ビット(dl-1)に焦点があてられる。
【0074】
次に、乱数生成部102により乱数r∈[−1,0,1]を生成する(ステップS53)。
【0075】
次に、制御部101において、乱数rがNAF規則を満たすか否か調べ(ステップS54)、満たしている場合には、ステップS55へ進み、満たしていない場合には、(該乱数rを破棄して)ステップS53へ戻る。
【0076】
NAF規則を満たしていた場合には、dj=rを実行する(ステップS55)。最上位ビット(dl-1)に焦点があてられている場合には、dl-1=rが実行される。dj=rは、べき乗剰余算部105へ与えられる。
【0077】
べき乗剰余算部105では、まず、y=y2 mod nの二乗剰余演算を行う(ステップS56)。
【0078】
次に、先に決定されたNAF乱数系列の当該ビットdj(最初のループでは、最上位ビットdl-1)が1であるか否か調べ(ステップS57)、dj=1である場合には、ステップS58へ進み、dj=1でない場合には、ステップS59へ進む。ステップS57でdj=1でないケースで、当該ビットdjが−1であるか否か調べ(ステップS59)、dj=−1である場合には、ステップS60へ進む。
【0079】
上記の分岐でdj=1である場合には、y=y・x mod nの乗算剰余を行い(ステップS58)、ステップS61へ進む。dj=−1である場合には、y=y・x-1 mod nの乗算剰余を行い(ステップS60)、ステップS61へ進む。ここで、x-1は法nでのxの逆元を表している。dj=1でなく且つdj=−1でない場合(すなわち、dj=0である場合)には、何もせずに、ステップS61へ進む。
【0080】
さて、ステップS57,S59によりdjの値に応じて3分岐した処理がステップS61に集束する。
【0081】
そして、制御部101において、j=0であるか否か調べ(ステップS61)、j≠0である場合には、ステップS52へ戻り(j=j−1が実行されて、1つ下位のビットに焦点があてられる)、以降、ステップS61でj=0となるまで繰り返し同様の処理が行われる。
【0082】
また、ステップS61でj=0である場合には、求めるべき出力y(=xd mod n)が得られたことになり、この処理を終了する。
【0083】
以上のように、本実施形態によれば、べき指数としてNAF乱数系列を用いたべき乗剰余演算の出力y=xd mod nを得ることができる。また、図5(b)のように、処理の高速化を図ることができる。
【0084】
(第4の実施形態)
第4の実施形態に係る演算処理装置の構成例は、第3の実施形態と同様である(図6参照)。ただし、第3の実施形態は、第1の実施形態のNAF乱数系列生成装置に相当するNAF乱数系列生成部120に、所定の演算を行う演算部として、べき乗剰余算を行う、べき乗剰余算部105を追加したものであるが、第4の実施形態は、第2の実施形態のNAF乱数系列生成装置に相当するNAF乱数系列生成部120に、所定の演算を行う演算部として、べき乗剰余算を行う、べき乗剰余算部105を追加したものである(本実施形態においても、べき乗剰余算部105は、既存のもので構わない)。
【0085】
本実施形態では、第2,3の実施形態と相違する点を中心に説明する。
【0086】
図8に、本実施形態の演算処理装置において実行される、NAF乱数系列生成及びべき乗剰余算の処理手順の一例を示す。
【0087】
第2の実施形態と同様、生成すべきNAF乱数系列のビット長をlとし、内部の乱数生成部102によって生成される乱数をr∈[−1,0,1]とし、生成されるNAF乱数系列をdl-1,…,d0とする。また、第3の実施形態と同様、生成されるNAF乱数系列dl-1,…,d0の10進数値をべき乗剰余算におけるべき指数dとし、べき乗される値をxとし、剰余演算の法をnとする。
【0088】
この手順例は、第3の実施形態と同様、べき指数となるNAF乱数系列のビット長lと、べき乗される値xと、法nとを入力したとき、べき乗剰余算結果y=xd mod nが出力となるものであるが、その際、第2の実施形態と同様に、NAFの規則を満たす乱数系列を、最上位ビット(MSB)から最下位ビット(LSB)へ向かって順に生成しながら、併せて、符号付バイナリ法を実行するものである。
【0089】
本実施形態の演算処理装置にl、x、nが入力されると、制御部101において、j=l−1とdj=1とが実行され(ステップS71)、これによって、最上位ビットdl-1が1に決定される。
【0090】
また、最上位ビットdl-1が1であるので、べき乗剰余算部105において、y=(12・x)mod n=x mod nを実行する(ステップS71)。
【0091】
以降は、ループ処理となる。
【0092】
まず、制御部101において、j=j−1が実行され(ステップS72)、これによって、1つ下位のビットに焦点があてられる。
【0093】
次に、記憶部103に記憶されている1つ前(上位)のビットdj+1(最初のループでは、最上位ビットdl-1)が0であるか否か調べ(ステップS73)、dj+1≠0である場合には、ステップS74へ進み、dj+1=0である場合には、ステップS75へ進む。
【0094】
ステップS73でdj+1≠0である(すなわち、dj+1=1 or −1である)場合には、次に来るビット値はNAF規則により必ず0となるので、dj=0を実行する(ステップS74)。続いて、べき乗剰余算部105において、二乗剰余演算y=y2 mod nを実行して(ステップS78)、ステップS83へ進む。
【0095】
他方、ステップS73でdj+1=0である場合には、NAF規則から次に取り得るビット値として[−1,0,1]の3値が候補となるので、乱数生成部102によって乱数r∈[−1,0,1]を生成し(ステップS75)、制御部101において、dj=rを実行し(ステップS76)、これによって、djの値が決定される。次いで、べき乗剰余算部105において、y=y2 mod nの二乗剰余演算を実行して(ステップS77)、ステップS79へ進む。
【0096】
次に、べき乗剰余算部105において、先に決定されたNAF乱数系列の当該dj(最初のループでは、最上位ビットの1つ下位のビットdl-2)が1であるか否か調べ(ステップS79)、dj=1である場合には、ステップS81へ進み、dj=1でない場合には、ステップS80へ進む。ステップS79でdj=1でないケースで、先に決定されたNAF乱数系列の最上位ビットdjが−1であるか否か調べ(ステップS80)、dj=−1である場合には、ステップS82へ進む。
【0097】
上記の分岐でdj=1である場合には、y=y・x mod nの乗算剰余を行い(ステップS81)、ステップS83へ進む。dj=−1である場合には、y=y・x-1 mod nの乗算剰余を行い(ステップS82)、ステップS83へ進む。ここで、x-1は法nでのxの逆元を表している。dj=1でなく且つdj=−1でない場合(すなわち、dl-1=0である場合)には、何もせずに、ステップS83へ進む。
【0098】
さて、ステップS73,S79,S80によりdj+1やdjの値に応じて分岐した処理がステップS83に集束する。
【0099】
そして、制御部101において、j=0であるか否か調べ(ステップS83)、j≠0である場合には、ステップS72へ戻り(j=j−1が実行されて、1つ下位のビットに焦点があてられる)、以降、ステップS83でj=0となるまで繰り返し同様の処理が行われる。
【0100】
また、ステップS83でj=0である場合には、求めるべき出力y(=xd mod n)が得られたことになり、この処理を終了する。
【0101】
なお、上記処理手順では、生成すべきNAF乱数系列の最上位ビットについては、乱数の生成もループ処理も行わずに、1を与え、また、これに対応して、y=x mod nを実行し、最上位ビット以外のビットについて、ループ処理を施すようにしたが、その代わりに、生成すべきNAF乱数系列の最上位ビット及びその1つ下位のビットについては、乱数の生成もループ処理も行わずに、それぞれ1及び0を与え、最上位ビットの1に対応して、y=x mod nを実行し、最上位ビット及びその1つ下位のビット以外のビットについて、ループ処理を施すような構成も可能である。
【0102】
以上のように、本実施形態によれば、べき指数としてNAF乱数系列を用いたべき乗剰余演算の出力y=xd mod nを得ることができる。また、図5(b)のように、処理の高速化を図ることができる。
【0103】
なお、これまで説明した実施形態では、バイナリ法を用いた例を示したが、window法などの方法を用いても同様に実施可能である。window法などでは、NAF乱数系列生成装置100(NAF乱数系列生成部120)からの出力を所望のビット長ずつ処理を行うことで同様に適用することが可能である。
【0104】
(第5の実施形態)
第3,4の実施形態では、べき乗剰余算を例にとって説明したが、楕円曲線暗号系に用いられる楕円曲線上の点のスカラー倍算で置き換えることも可能である。
【0105】
第5の実施形態では、第3,4の実施形態のべき乗剰余算をスカラー倍算に置き換えた例について説明する。
【0106】
ここで、スカラー倍算について簡単に説明する。
【0107】
スカラー倍算とは、楕円曲線上の点Pのd倍を導出する処理をいい、d倍された点PをdPと表す。このdをスカラー値と呼ぶ。
【0108】
符号付2進数表現を用いた場合のスカラー倍算アルゴリズムは以下のようになる。
(Step0) Input:d,P
(Step1) 整数dを、d=Σ(di・2i)と2進数表現する(i=0〜l−1につきそれぞれkiを求める)。ここで、ki∈T,T∈[−1,0,1]とする。
(Step2) Q←P
(Step3) i=l−2から0までの間、次を繰り返す。
(Step3−1) Q←2Q
(Step3−2) di=1ならば、Q←Q+P
(Step3−3) di=−1ならば、Q←Q−P
(Step4) Output Q(=dP)
図9に、本実施形態の演算処理装置300の構成例を示す。
【0109】
本実施形態では、演算処理装置300は、第1の実施形態のNAF乱数系列生成装置に相当するNAF乱数系列生成部120に、所定の演算を行う演算部106を追加した構成になっている。本実施形態では、演算部106は、スカラー倍算を行うスカラー倍算部である(スカラー倍算部は、既存のもので構わない)。
【0110】
本実施形態では、第1,3の実施形態と相違する点を中心に説明する。
【0111】
図10に、本実施形態の演算処理装置において実行される、NAF乱数系列生成及びスカラー倍算の処理手順の一例を示す。
【0112】
これまでの実施形態と同様、生成すべきNAF乱数系列のビット長をlとし、内部の乱数生成部102によって生成される乱数をr∈[−1,0,1]とし、生成されるNAF乱数系列をdl-1,…,d0とする。
【0113】
この手順例は、スカラー値となるNAF乱数系列のビット長lと、スカラー倍される点Pとを入力したとき、スカラー倍算結果Q=dPが出力となるものであるが、その際、第1,3の実施形態と同様に、NAFの規則を満たす乱数系列を、最上位ビット(MSB)から最下位ビット(LSB)へ向かって順に生成しながら、併せて、スカラー倍算を実行するものである。
【0114】
本実施形態の演算処理装置にl、Pが入力されると、制御部101において、j=lが実行され、スカラー倍算部106において、Q←Οが実行される(ステップS91)。ここで、Οは無限遠点を表し、有限体上の楕円曲線の単位元である(例、P+(-P)=Ο、P+Ο=-P)。
【0115】
以降は、ループ処理となる。
【0116】
まず、j=j−1が実行される(ステップS92)。最初は、j=j−1=l−1となり、これによって、最上位ビット(dl-1)に焦点があてられる。
【0117】
次に、乱数生成部102により乱数r∈[−1,0,1]を生成する(ステップS93)。
【0118】
次に、制御部101において、乱数rがNAF規則を満たすか否か調べ(ステップS94)、満たしている場合には、ステップS95へ進み、満たしていない場合には、(該乱数rを破棄して)ステップS93へ戻る。
【0119】
NAF規則を満たしていた場合には、dj=rを実行する(ステップS95)。最上位ビット(dl-1)に焦点があてられている場合には、dl-1=rが実行される。dj=rは、スカラー倍算部106へ与えられる。
【0120】
スカラー倍算部106では、まず、Q←2Qの点2倍算を行う(ステップS96)。
【0121】
次に、先に決定されたNAF乱数系列の当該ビットdj(最初のループでは、最上位ビットdl-1)が1であるか否か調べ(ステップS97)、dj=1である場合には、ステップS98へ進み、dj=1でない場合には、ステップS99へ進む。ステップS97でdj=1でないケースで、先に決定されたNAF乱数系列の最上位ビットdjが−1であるか否か調べ(ステップS99)、dj=−1である場合には、ステップS100へ進む。
【0122】
上記の分岐でdj=1である場合には、Q←Q+Pの点加算を行い(ステップS98)、ステップS101へ進む。dj=−1である場合には、Q←Q−Pの点減算を行い(ステップS100)、ステップS101へ進む。ここで、−PはPの逆元を表している。dj=1でなく且つdj=−1でない場合(すなわち、dj=0である場合)には、何もせずに、ステップS101へ進む。
【0123】
さて、ステップS97,S99によりdjの値に応じて3分岐した処理がステップS101に集束する。
【0124】
そして、制御部101において、j=0であるか否か調べ(ステップS101)、j≠0である場合には、ステップS92へ戻り(j=j−1が実行されて、1つ下位のビットに焦点があてられる)、以降、ステップS101でj=0となるまで繰り返し同様の処理が行われる。
【0125】
また、ステップS101でj=0である場合には、求めるべき出力Q(=dP)が得られたことになり、この処理を終了する。
【0126】
以上のように、本実施形態によれば、べき指数としてNAF乱数系列を用いたスカラー倍算の出力Q=dPを得ることができる。また、図5(b)のように、処理の高速化を図ることができる。
【0127】
ここでは、スカラー倍算部106において最上位ビットから処理を行う方法を示したが、最上位ビットが必ず1であることを利用して、上に示したスカラー倍算アルゴリズムのように、初めにQ←Pとし、最上位ビットの次のビットから処理を行う方法も考えられる。
【0128】
なお、本実施形態では、第1の実施形態のNAF乱数系列生成装置(に相当するNAF乱数系列生成部120)に、所定の演算を行う演算部としてスカラー倍算を行うスカラー倍算部を組み合わせた演算処理装置を例にとって説明したが、第4の実施形態と同様に、第2の実施形態のNAF乱数系列生成装置(に相当するNAF乱数系列生成部120)に、スカラー倍算部を組み合わせた演算処理装置も実施可能である。
【0129】
また、第1或いは第2の実施形態のNAF乱数系列生成装置に、所定の演算を行う演算部として、スカラー倍算及びべき乗剰余算部以外の演算を行う装置(その演算の過程において、NAF乱数系列生成装置により生成された乱数系列を、最上位ビット(MSB)から最下位ビット(LSB)へ向かって順に1ビット又は所定の複数ビットを使用するもの)を組み合わせた演算処理装置も実施可能である。
【0130】
(バリエーション)
ところで、これまでの説明において、本実施形態のNAF乱数系列生成装置100において、乱数生成部102で生成される[−1,0,1]の3値の発生確率をある一定の比率に変更することで、生成されるNAF乱数系列の特性を変更するができるようになる。
【0131】
例えば、図4のステップS45等において、1つ前(上位)のビット値が0であった場合に、次に取り得るビット値として[−1,0,1]の3値が候補となるが、乱数生成部102の出力である3値の乱数r∈[−1,0,1]の発生確率をそれぞれ1/4,1/2,1/4などとする方法が考えられる。0の発生確率が高いと、生成されるNAF乱数系列の非ゼロ係数の数が減少する傾向が見られると予想される。
【0132】
図2のステップS23や図4のステップS45等において、乱数生成部102からの出力の発生確率を任意の比率に変更する方法としては種々のバリエーションが考えられるが、例えば、乱数生成部102から出力される2ビット系列が00あるいは11ならば0、01ならば1、10ならば−1と決定することで、3値の乱数r∈[−1,0,1]の発生確率をそれぞれ1/4,1/2,1/4とすることで実現可能である。
【0133】
なお、以上の各機能は、ソフトウェアとして記述し適当な機構をもったコンピュータに処理させても実現可能である。
また、本実施形態は、コンピュータに所定の手順を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるためのプログラムとして実施することもできる。加えて該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【0134】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【0135】
【図1】本発明の第1及び第2の実施形態に係るNAF乱数系列生成装置の構成例を示す図
【図2】本発明の第1の実施形態に係るNAF乱数系列生成装置の処理手順の一例を示すフローチャート
【図3】NAF規則を満たすか否かについて判定する処理手順の一例を示すフローチャート
【図4】本発明の第2の実施形態に係るNAF乱数系列生成装置の処理手順の一例を示すフローチャート
【図5】NAF乱数系列生成及びこれに続いて又はこれと並行して行われる演算について説明するための図
【図6】本発明の第3及び第4の実施形態に係る演算処理装置の構成例を示す図
【図7】本発明の第3の実施形態に係る演算処理装置の処理手順の一例を示すフローチャート
【図8】本発明の第4の実施形態に係る演算処理装置の処理手順の一例を示すフローチャート
【図9】本発明の第5の実施形態に係る演算処理装置の構成例を示す図
【図10】本発明の第5の実施形態に係る演算処理装置の処理手順の一例を示すフローチャート
【符号の説明】
【0136】
100…NAF乱数系列生成装置、102…乱数生成部、101…制御部、103…記憶部、104…出力部、105…演算部、106…スカラー倍算部、120…NAF乱数系列生成部、200,300…演算処理装置




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013