(57)【要約】  乱数生成システム１０は、中心が正の値である１次元格子上の離散ガウス分布である第１離散分布に従う乱数を生成する乱数生成システムであって、第１離散分布において確率変数が正の範囲における所定の区間内の値になる確率である第１確率と０の間の一様乱数を生成する生成手段１１と、中心が原点である１次元格子上の離散ガウス分布である第２離散分布において確率変数が所定の区間内の値になる確率である第２確率以下の一様乱数が生成されると乱数の生成方法に第２離散分布を定める函数の値が用いられる累積法を選択し、第２確率よりも大きい一様乱数が生成されると乱数の生成方法に棄却サンプリング法を選択する選択手段１２とを含む。
2019030799.tif 000002
【特許請求の範囲】
【請求項１】
中心が正の値である１次元格子上の離散ガウス分布である第１離散分布に従う乱数を生成する乱数生成システムであって、
前記第１離散分布において確率変数が正の範囲における所定の区間内の値になる確率である第１確率と０の間の一様乱数を生成する生成手段と、
中心が原点である前記１次元格子上の離散ガウス分布である第２離散分布において確率変数が前記所定の区間内の値になる確率である第２確率以下の一様乱数が生成されると前記乱数の生成方法に前記第２離散分布を定める函数の値が用いられる累積法を選択し、前記第２確率よりも大きい一様乱数が生成されると前記乱数の生成方法に棄却サンプリング法を選択する選択手段とを含む
ことを特徴とする乱数生成システム。
【請求項２】
第２離散分布を定める函数の値が用いられる累積法で１次元格子上の離散ガウス分布に従う乱数を生成する累積法生成手段を含み、
選択手段は、累積法が選択された後に前記累積法生成手段に乱数の生成を指示し、
前記累積法生成手段は、指示を受けて乱数を生成する
請求項１記載の乱数生成システム。
【請求項３】
累積法生成手段は、第２離散分布を定める函数の値が記憶されている記憶手段を有する
請求項２記載の乱数生成システム。
【請求項４】
棄却サンプリング法で１次元格子上の離散ガウス分布に従う乱数を生成する棄却サンプリング法生成手段を含み、
選択手段は、棄却サンプリング法が選択された後に前記棄却サンプリング法生成手段に乱数の生成を指示し、
前記棄却サンプリング法生成手段は、指示を受けて乱数を生成する
請求項１から請求項３のうちのいずれか１項に記載の乱数生成システム。
【請求項５】
中心が正の値である１次元格子上の離散ガウス分布である第１離散分布に従う乱数を生成する乱数生成システムで実行される乱数生成方法であって、
前記第１離散分布において確率変数が正の範囲における所定の区間内の値になる確率である第１確率と０の間の一様乱数を生成し、
中心が原点である前記１次元格子上の離散ガウス分布である第２離散分布において確率変数が前記所定の区間内の値になる確率である第２確率以下の一様乱数が生成されると前記乱数の生成方法に前記第２離散分布を定める函数の値が用いられる累積法を選択し、
前記第２確率よりも大きい一様乱数が生成されると前記乱数の生成方法に棄却サンプリング法を選択する
ことを特徴とする乱数生成方法。
【請求項６】
中心が正の値である１次元格子上の離散ガウス分布である第１離散分布に従う乱数を生成するコンピュータで実行される乱数生成プログラムであって、
前記コンピュータに、
前記第１離散分布において確率変数が正の範囲における所定の区間内の値になる確率である第１確率と０の間の一様乱数を生成する生成処理、
中心が原点である前記１次元格子上の離散ガウス分布である第２離散分布において確率変数が前記所定の区間内の値になる確率である第２確率以下の一様乱数が生成されると前記乱数の生成方法に前記第２離散分布を定める函数の値が用いられる累積法を選択する第１選択処理、および
前記第２確率よりも大きい一様乱数が生成されると前記乱数の生成方法に棄却サンプリング法を選択する第２選択処理
を実行させるための乱数生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乱数生成システム、乱数生成方法および乱数生成プログラムに関し、特に格子暗号および署名に用いられ中心が原点でない離散ガウス分布に従う乱数を生成する乱数生成システム、乱数生成方法および乱数生成プログラムに関する。
【背景技術】
【０００２】
最初に、離散ガウス分布を定義する。実数s ∈R （R は実数全体の集合を表す記号）で定まる函数を、以下のように定義する。【０００３】
【数１】
2019030799.tif 000003
【０００４】
整数値u ∈Z （Z は整数全体の集合を表す記号）が確率φs(u)/ Σ∞j=−∞ φs(j)で出力された分布を、分散値がs である離散ガウス分布と呼ぶ。上記の離散ガウス分布に従って生成された乱数は、非特許文献１に記載されているように、格子が用いられた暗号（以下、格子暗号という。）に使用される。格子暗号は、耐量子暗号として使用されることが期待されている。さらに、格子暗号は、計算効率が良く、機能性の高い暗号スキームとして研究されている暗号システムである。【０００５】
離散ガウス分布は、全ての整数値を出力し得る確率分布である。しかし、離散ガウス分布に従って生成された乱数が格子暗号に用いられる場合、離散ガウス分布が出力する整数値の範囲が制限されることによって、確率変数の生成が効率化される場合が多い。【０００６】
例えば、以下のように離散ガウス分布が出力する整数値の範囲がセキュリティパラメータn ∈N （N は自然数全体の集合を表す記号）に依存する形で制限されることによって、確率変数の生成が効率化される。【０００７】
すなわち、t = ω(logn)1/2として、{k∈Z|− t・s ≦k ≦ t・s}が離散ガウス分布の出力範囲とされることによって、確率変数の生成が効率化される。なお、ωは、ランダウの記号である。離散ガウス分布が出力する整数の範囲が上記のように制限されても、格子暗号の安全性に影響が及ばないことが一般的に知られている。【０００８】
正規化定数W をW = Σ t・si= − t・s φs(i)のように定義するとき、出力する整数の範囲が上記のように制限された離散ガウス分布をΨs(x) = φs(x)/Wとおく。Ψs(x)が用いられる場合、整数値u ∈Z が確率Ψs(u)で出力される。【０００９】
以下、本明細書における「離散ガウス分布」は、出力する整数の範囲が{k∈Z|− t・s ≦k ≦ t・s}であり、整数値u ∈Z を確率Ψs(u)で出力する確率分布を指す。また、函数Ψs(x) = φs(x)/Wを、離散ガウス分布を定める函数と呼ぶ。【００１０】
次に、離散ガウス分布の中心を説明する。中心がc 、分散値がs である離散ガウス分布は、整数値u を確率Ψs(u−c)で出力する確率分布である。【００１１】
上記の内容は、１次元格子上の離散ガウス分布に対する定義である。次に、ｎ次元格子上の離散ガウス分布に対する定義を与える。【００１２】
ベクトル{b1→, ・・・,bn→} ∈Rnが横に並べられた行列をB と記載する。行列B が用いられたｎ次元の格子Λ(B) を、以下のように定める。【００１３】
【数２】
2019030799.tif 000004
【００１４】
また、中心がc→であるRn上のガウス函数を、パラメータs を用いて以下のように定義する。【００１５】
【数３】
2019030799.tif 000005
【００１６】
上記の式（３）で表現されるガウス函数を用いて、ｎ次元格子Λ上の離散ガウス分布を以下のように定義する。【００１７】
【数４】
2019030799.tif 000006
【００１８】
すなわち、ｎ次元格子上の離散ガウス分布は、確率変数が式（４）に従う確率分布である。以下、１次元格子上の離散ガウス分布、ｎ次元格子上の離散ガウス分布を、簡単のためそれぞれ１次元離散ガウス分布、ｎ次元離散ガウス分布とも呼ぶ。【００１９】
以上の内容が、１次元離散ガウス分布の定義、および多次元（ｎ次元）離散ガウス分布の定義である。次に、それぞれの離散ガウス分布に従う乱数を生成するためのサンプリング法を説明する。【００２０】
一般的に、１次元離散ガウス分布に従う乱数の生成方法であるサンプリング法には、累積法と棄却サンプリング法の２つの方法がある。なお、１次元離散ガウス分布を定める函数をφ(x) 、１次元離散ガウス分布の出力範囲を{k∈Z|− t・s ≦k ≦ t・s}とする。【００２１】
上記の２つのサンプリング法をそれぞれ、１次元離散ガウス分布の中心が原点である場合と１次元離散ガウス分布の中心が原点でない場合とに分けて説明する。【００２２】
最初に、中心が原点である１次元離散ガウス分布に従う乱数を累積法で生成する処理を、非特許文献２に記載されている内容に基づいて説明する。図９は、１次元離散ガウス分布に従う乱数を生成する一般的な乱数生成システムの構成例を示すブロック図である。【００２３】
図９に示すように、中心が原点である１次元離散ガウス分布に従う乱数を生成する乱数生成システム９１０は、記憶装置９１１と、探索器９１２と、一様乱数生成器９１３とで構成されている。【００２４】
図９に示すような構成要素を有する中心が原点である１次元離散ガウス分布に従う乱数を生成する一般的な乱数生成システム９１０は、以下のように動作する。最初に、φ(0)/2,φ(1),φ(2),・・・ ,φ(t・s)の各値が事前に計算され、記憶装置９１１に記憶される。図９に示す記憶装置９１１内の各縦線が、φ(0)/2,φ(1) 等の記憶された各値を表す。【００２５】
次いで、一様乱数生成器９１３が、実数値x ∈[0,1] を出力する。出力されたx ∈R は、探索器９１２に入力される。x が入力された探索器９１２は、記憶装置９１１に記憶されている各値の中からφ(z−1)≦x ＜φ(z) を満たすz ∈Z を二分探索する。【００２６】
次いで、探索器９１２は、符号sign= ±を一様に選ぶ。次いで、探索器９１２は、sign・z ∈Z を１次元離散ガウス分布に従う乱数として出力する。以上の内容が、累積法による中心が原点である１次元離散ガウス分布に従う乱数の生成方法である。【００２７】
なお、中心が原点でない、例えば中心がa である１次元離散ガウス分布に従う乱数の累積法による生成方法は、上記の中心が原点である１次元離散ガウス分布に従う乱数の生成方法においてφ(x) をφ(x−a)に置き換えればよい。【００２８】
累積法の場合、記憶装置に記憶されるデータの数が t・s に比例する。なお、記憶装置に記憶されるデータは、中心が原点である１次元離散ガウス分布が用いられる場合はφ(0)/2,φ(1),φ(2),・・・ ,φ(t・s)である。また、中心が原点でなくa である１次元離散ガウス分布が用いられる場合はφ(0−a)/2, φ(1−a), φ(2−a), ・・・ ,φ(t・s −a)である。【００２９】
すなわち、累積法には、分散値s が大きい離散ガウス分布が使用される場合、函数の値の記憶に要するメモリ量が多くなるという問題がある。既存の格子暗号において分散値s は、比較的大きな値をとる。【００３０】
函数の値の記憶に要する具体的なメモリ量として、例えば、図１０に示す値が非特許文献４に記載されている。図１０は、累積法が使用される時に消費されるメモリ量の例を示す説明図である。図１０に示すように、分散値が大きくなるほど消費されるメモリ量も多くなる。【００３１】
なお、図１０に示す中心の「q-種類/1署名」は、１回の署名生成につき、q=2Kの中心が用意されることを意味する。同様に、「2-種類/1署名」は、１回の署名生成につき、２種類の中心しか用意されないことを意味する。【００３２】
また、図１０に示すUseageは、各方式でガウス分布が使用される用途を表す。例えば、方式「LWE-plane 」では、「鍵生成」の用途でガウス分布が使用される。また、方式「GPV 」等では、「署名生成」の用途でガウス分布が使用される。「署名生成」の用途でガウス分布が使用される場合、ガウス分布は何度も使用される。【００３３】
RSA 等の格子暗号では、一般的に求められる計算量が少ない。よって、格子暗号は、センサ機器や携帯電話のような計算資源や記憶容量が小さいデバイスでの利用が期待されている。【００３４】
しかし、格子暗号のサブルーチンである離散ガウス分布に従う乱数の生成に累積法が用いられると、累積法で使用されるデータの保存のために多くの記憶容量が使用される。すなわち、記憶容量の小さいデバイスでの格子暗号の利用が困難になるという問題がある。【００３５】
次に、棄却サンプリング法を説明する。棄却サンプリング法は、離散ガウス分布に限られず、任意の離散型確率分布に従う乱数が生成される際に使用される方法である。【００３６】
最初に、一般の確率変数X に対する離散型確率分布に従う乱数を生成する棄却サンプリング法を、非特許文献５に記載されている内容に基づいて説明する。その後に、１次元離散ガウス分布に従う乱数を生成する棄却サンプリング法を説明する。【００３７】
離散型確率分布p(X=xi) に従う乱数を棄却サンプリング法を利用して生成するために、最初に全てのxiに対してt(xi) ≧p(xi) を満足する函数t(x)のうち、効率的に計算可能なt(x)を準備する。【００３８】
次いで、t(x)が正規化された函数r(x)を、r(x)=t(x)/Σt(xi) とする。次いで、以下の手順を実行することによって、確率変数X に対する離散型確率分布p(X=xi) （確率分布函数）に従う乱数を、棄却サンプリング法を利用して生成する。【００３９】
(Step 1)  確率分布函数r(x)に従う乱数Y を生成する。
(Step 2)  Y と独立に区間[0,1] 内の一様乱数U を発生させる。
(Step 3)  U ≦p(Y)/t(Y) が満たされる場合、乱数X をX=Y とする。U ≦p(Y)/t(Y) が満たされない場合、再度(Step 1)の処理を行う。【００４０】
なお、非特許文献５に記載されているAlgorithm A1における1/ε、g 、f がそれぞれ上記の手順では1 、t 、p に変換されている。【００４１】
次に、１次元離散ガウス分布に従う乱数を生成する棄却サンプリング法を、非特許文献３に記載されている内容に基づいて説明する。なお、非特許文献３に記載されている方法は、上述した棄却サンプリング法が、函数t(x)が恒等的に１である場合に対して適応された方法である。【００４２】
非特許文献３に記載されている方法を実現するための装置の構成例を図１１に示す。図１１は、１次元離散ガウス分布に従う乱数を生成する一般的な乱数生成システムの他の構成例を示すブロック図である。【００４３】
図１１に示すように、中心が原点である１次元離散ガウス分布に従う乱数を生成する乱数生成システム９２０は、棄却判定器９２１と、一様乱数生成器９２２と、出力装置９２３とで構成されている。【００４４】
図１１に示すような構成要素を有する中心が原点である１次元離散ガウス分布に従う乱数を生成する一般的な乱数生成システム９２０は、以下のように動作する。最初に、一様乱数生成器９２２は、{k∈Z|− t・s ≦k ≦ t・s}の範囲で一様乱数u1∈Z を生成する。【００４５】
次いで、一様乱数生成器９２２は、[0, φ(0)]の範囲で実数値の乱数u2∈R を生成する。一様乱数生成器９２２は、生成されたu1∈Z とu2∈R を棄却判定器９２１に入力する。【００４６】
次いで、棄却判定器９２１は、φ(u1)とu2∈R を比較する。比較した結果u2≦φ(u1)であれば、棄却判定器９２１は、u1∈Z を出力装置９２３に入力する。出力装置９２３は、中心が原点である１次元離散ガウス分布に従う乱数としてu1∈Z を出力する。【００４７】
比較した結果u2＞φ(u1)であれば、乱数生成システム９２０は、最初のステップに戻り、同じ操作を再度実行する。以上の内容が、棄却サンプリング法による中心が原点である１次元離散ガウス分布に従う乱数の生成方法である。【００４８】
なお、中心が原点でない、例えば中心がa である１次元離散ガウス分布に従う乱数の棄却サンプリング法による生成方法は、上記の中心が原点である１次元離散ガウス分布に従う乱数の生成方法においてφ(x) をφ(x−a)に置き換えればよい。【００４９】
棄却サンプリング法では、上記の(Step 3)に相当する処理における条件が満たされない場合、再度同様の処理が繰り返し実行される。すなわち、棄却サンプリング法には、生成された一様乱数が棄却される度に離散ガウス分布を定める函数を再度計算することが求められるため、計算効率が低下するという問題がある。【００５０】
以上の内容をまとめると、累積法の長所は、計算コストが小さいことである。一方、累積法の短所は、メモリコストが大きいことである。また、棄却サンプリング法の長所は、メモリコストが小さいことである。一方、棄却サンプリング法の短所は、計算コストが大きいことである。【００５１】
次に、多次元格子上の離散ガウス分布に従う乱数の生成方法を、非特許文献３に記載されている内容に基づいて説明する。説明の前に、いくつかの事項を用意する。【００５２】
ベクトルa1→,・・・,an→に対する各Gram-Schmidt直交化ベクトルa1~→, ・・・ ,an~→を、以下のように計算されるベクトルとする。【００５３】
【数５】
2019030799.tif 000007
【００５４】
なお、本明細書においてテキスト中で使用する記号である「−」「→」「〜」等は、本来直前の文字の真上に記載されるべきであるが、テキスト記法の制限により上記のように当該文字の直後に記載する。式中および図面においてはこれらの記号は本来の位置に記載される。【００５５】
図１２は、多次元格子上の離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。図１２に示すアルゴリズムの４行目〜９行目のループでは、１回の処理で乱数ziが生成され、生成されたziを基にci−1 が更新される。また、次の処理では更新されたci−1 を基に離散ガウス分布が更新された上で乱数zi−1 が生成される。すなわち、乱数zn, ・・・ ,z1が、それぞれ逐次的に生成される。【００５６】
図１２に示すアルゴリズムの７行目の処理におけるDZ,c’i,σi は、中心がc’i 、分散値がσi である１次元離散ガウス分布を表す。ループを構成する各処理でci−1 が更新されるため、中心が異なる１次元離散ガウス分布に従う乱数の生成も毎回求められる。
【先行技術文献】
【非特許文献】
【００５７】
【非特許文献１】Regev, "On lattices, learning with errors, random linear codes, and cryptography," STOC 2005, ACM, 2005, pages 84-93.
【非特許文献２】Chris Peikert, "An efficient and parallel Gaussian Sampler for lattices," CRYPTO, 2010, pages 80-97.
【非特許文献３】Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan, "How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions," STOC, 2008, pages 197-206.
【非特許文献４】DWARAKANATH, N. C, GALBRAITH, S. D, "Sampling From Discrete Gaussians for Lattice-Based Cryptography on a Constrained Device," Appl. Algebra Engrg. Comm. Comput. 25, 2014, pages 159-180.
【非特許文献５】George Casella, Christian P. Robert, and Martin T. Wells, "Generalized Accept-Reject sampling schemes," A Festschrift for Herman Rubin Institute of Mathematical Statistics Lecture Notes - Monograph Series Vol. 45, 2004, pages 342-347.
【発明の概要】
【発明が解決しようとする課題】
【００５８】
多次元（ｎ次元）格子上の離散ガウス分布に従う乱数を生成する場合、中心が原点であるとは限られない１次元格子上の離散ガウス分布に従う乱数をｎ回生成することが求められる。中心が原点であるとは限られない１次元格子上の離散ガウス分布に従う乱数の生成方法に、上記の累積法および棄却サンプリング法が使用される。【００５９】
累積法を用いて多次元格子上の離散ガウス分布に従う乱数を生成する時の課題と、棄却サンプリング法を用いて多次元格子上の離散ガウス分布に従う乱数を生成する時の課題をそれぞれ順に述べる。【００６０】
累積法が用いられて多次元格子上の離散ガウス分布に従う乱数が生成される場合、出力対象の格子の次元の数だけ１次元離散ガウス分布に従う乱数が生成される。また、累積法では、乱数の生成に用いられる１次元離散ガウス分布の中心が異なる度に新しい数値を記憶装置に保存することが求められる。【００６１】
よって、乱数の生成に用いられる複数の１次元離散ガウス分布の中心が殆ど異なるような場合、多くのメモリ量が消費される。すなわち、多次元格子上の離散ガウス分布に従う乱数の生成に使用される累積法は、メモリ量の観点において効率的なサンプリング法ではない。【００６２】
棄却サンプリング法を用いて多次元格子上の離散ガウス分布に従う乱数を生成する時の課題は、１次元離散ガウス分布に従う乱数の生成速度が遅い点である。その理由は、生成された一様乱数が棄却される度に離散ガウス分布を定める函数の計算が求められるので、全体的な計算効率が低下するためである。【００６３】
［発明の目的］
そこで、本発明は、上述した課題を解決する、多次元格子上の離散ガウス分布に従う乱数の生成に掛かるメモリコストと計算コストをより低減できる乱数生成システム、乱数生成方法および乱数生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００６４】
本発明による乱数生成システムは、中心が正の値である１次元格子上の離散ガウス分布である第１離散分布に従う乱数を生成する乱数生成システムであって、第１離散分布において確率変数が正の範囲における所定の区間内の値になる確率である第１確率と０の間の一様乱数を生成する生成手段と、中心が原点である１次元格子上の離散ガウス分布である第２離散分布において確率変数が所定の区間内の値になる確率である第２確率以下の一様乱数が生成されると乱数の生成方法に第２離散分布を定める函数の値が用いられる累積法を選択し、第２確率よりも大きい一様乱数が生成されると乱数の生成方法に棄却サンプリング法を選択する選択手段とを含むことを特徴とする。【００６５】
本発明による乱数生成方法は、中心が正の値である１次元格子上の離散ガウス分布である第１離散分布に従う乱数を生成する乱数生成システムで実行される乱数生成方法であって、第１離散分布において確率変数が正の範囲における所定の区間内の値になる確率である第１確率と０の間の一様乱数を生成し、中心が原点である１次元格子上の離散ガウス分布である第２離散分布において確率変数が所定の区間内の値になる確率である第２確率以下の一様乱数が生成されると乱数の生成方法に第２離散分布を定める函数の値が用いられる累積法を選択し、第２確率よりも大きい一様乱数が生成されると乱数の生成方法に棄却サンプリング法を選択することを特徴とする。【００６６】
本発明による乱数生成プログラムは、中心が正の値である１次元格子上の離散ガウス分布である第１離散分布に従う乱数を生成するコンピュータで実行される乱数生成プログラムであって、コンピュータに、第１離散分布において確率変数が正の範囲における所定の区間内の値になる確率である第１確率と０の間の一様乱数を生成する生成処理、中心が原点である１次元格子上の離散ガウス分布である第２離散分布において確率変数が所定の区間内の値になる確率である第２確率以下の一様乱数が生成されると乱数の生成方法に第２離散分布を定める函数の値が用いられる累積法を選択する第１選択処理、および第２確率よりも大きい一様乱数が生成されると乱数の生成方法に棄却サンプリング法を選択する第２選択処理を実行させることを特徴とする。
【発明の効果】
【００６７】
本発明によれば、多次元格子上の離散ガウス分布に従う乱数の生成に掛かるメモリコストと計算コストをより低減できる。
【図面の簡単な説明】
【００６８】
【図１】中心が原点である１次元離散ガウス分布と中心が原点でない１次元離散ガウス分布とを示す説明図である。
【図２】累積法が適用される領域と棄却サンプリング法が適用される領域とを示す説明図である。
【図３】本発明による乱数生成システムの第１の実施形態の構成例を示すブロック図である。
【図４】第１の実施形態の生成方法選択装置１１０の構成例を示すブロック図である。
【図５】第１の実施形態の棄却サンプリング装置１２０の構成例を示すブロック図である。
【図６】第１の実施形態の累積法サンプリング装置１３０の構成例を示すブロック図である。
【図７】第１の実施形態の乱数生成システム１００による乱数生成処理の動作を示すフローチャートである。
【図８】本発明による乱数生成システムの概要を示すブロック図である。
【図９】１次元離散ガウス分布に従う乱数を生成する一般的な乱数生成システムの構成例を示すブロック図である。
【図１０】累積法が使用される時に消費されるメモリ量の例を示す説明図である。
【図１１】１次元離散ガウス分布に従う乱数を生成する一般的な乱数生成システムの他の構成例を示すブロック図である。
【図１２】多次元格子上の離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。
【発明を実施するための形態】
【００６９】
［第１の実施形態］
以下、本発明の実施形態を、図面を参照して説明する。本実施形態では、中心が原点である１次元離散ガウス分布を、以下に示す方法で中心が原点でない１次元離散ガウス分布に仮想的に変換することを考える。
【００７０】
図１は、中心が原点である１次元離散ガウス分布と中心が原点でない１次元離散ガウス分布とを示す説明図である。なお、説明の簡略化のために、図１には１次元離散ガウス分布の出力範囲のうち正の範囲のみが示されている。図１に示すように、１次元離散ガウス分布は線対称な分布であるため、出力範囲のうち正の範囲のみが考慮されればよい。
【００７１】
図１を参照すると、中心が原点でなくa である１次元離散ガウス分布の大部分は、中心が原点である１次元離散ガウス分布に含まれていることが分かる。例えば、図１に示す第１区間（便宜上、横軸の長さを１とする。）における確率φ(1) は、確率φ(1−a)の大部分を占めている。
【００７２】
同様に、図１に示す第２区間（便宜上、横軸の長さを１とする。）における確率φ(2) は、確率φ(2−a)の大部分を占めている。以下、全ての区間において同様の特徴が見受けられる。
【００７３】
すなわち、中心が原点でない１次元離散ガウス分布に従う第１区間における乱数は、φ(1)/φ(1−a)の確率で中心が原点である１次元離散ガウス分布に従う乱数であると考えられる。本実施形態では、上記の特徴が用いられている。
【００７４】
図２は、累積法が適用される領域と棄却サンプリング法が適用される領域とを示す説明図である。図２に示す確率P は、確率φ(1−a)、・・・、確率φ(t・s −a)の総和である。すなわち、確率P は、中心が原点でない１次元離散ガウス分布に従って乱数が出力される確率である。
【００７５】
また、図２に示すように、確率p{1-dim}は、確率φ(1) 、・・・、確率φ(t・s)の総和である。すなわち、確率p{1-dim}は、中心が原点である１次元離散ガウス分布に従って乱数が出力される確率である。
【００７６】
本実施形態の乱数生成システムは、区間[0, P]で取られた一様乱数r がp{1-dim}以下である場合、中心が原点である１次元離散ガウス分布を定める函数φ(x) の値が用いられる累積法で、中心が原点でない１次元離散ガウス分布に従う乱数を生成する。
【００７７】
また、図２に示すように、確率p{rjc}は、確率 {φ(1−a)−φ(1)}、・・・、確率 {φ(t・s −a)−φ(t・s)} の総和である。すなわち、確率p{rjc}は、中心が原点でない１次元離散ガウス分布に従って乱数が出力される確率P と中心が原点である１次元離散ガウス分布に従って乱数が出力される確率p{1-dim}との差である。
【００７８】
本実施形態の乱数生成システムは、区間[0, P]で取られた一様乱数r がp{1-dim}より大きい場合、棄却サンプリング法で中心が原点でない１次元離散ガウス分布に従う乱数を生成する。
【００７９】
確率p{1-dim}の方が確率p{rjc}よりも十分に大きいため、棄却サンプリング法で乱数が生成される確率は低い。すなわち、棄却サンプリング法で乱数が生成される機会が減るため、乱数の生成に掛かる全体の計算コストが低減される。
【００８０】
また、累積法では常に中心が原点である１次元離散ガウス分布を定める函数φ(x) の値が用いられるので、記憶装置には函数φ(x) の値さえ記憶されていればよい。すなわち、乱数の生成に掛かる全体のメモリコストも低減される。
【００８１】
なお、上記では中心が原点から右にずれている１次元離散ガウス分布に従う乱数の生成方法を説明したが、中心が原点から左にずれている１次元離散ガウス分布に従う乱数も同様の方法で生成される。本実施形態の乱数生成システムは、１次元格子上の離散ガウス分布の中心を仮想的に変換することによって、多次元格子上の離散ガウス分布に従う乱数を効率的に生成する。
【００８２】
［構成の説明］
図３は、本発明による乱数生成システムの第１の実施形態の構成例を示すブロック図である。図３に示すように、本実施形態の乱数生成システム１００は、生成方法選択装置１１０と、棄却サンプリング装置１２０と、累積法サンプリング装置１３０とを含む。
【００８３】
図４は、第１の実施形態の生成方法選択装置１１０の構成例を示すブロック図である。図４に示すように、本実施形態の生成方法選択装置１１０は、区間一様乱数生成手段１１１と、生成方法選択手段１１２とを有する。
【００８４】
区間一様乱数生成手段１１１は、区間[0, P]の一様乱数r を生成する機能を有する。また、生成方法選択手段１１２は、生成された一様乱数r と確率p{1-dim}とを比較した上で乱数の生成方法を選択する機能を有する。
【００８５】
生成方法選択手段１１２は、一様乱数r が確率p{1-dim}以下である場合、乱数の生成方法として累積法を選択する。選択した後、生成方法選択手段１１２は、累積法サンプリング装置１３０に乱数を生成するように指示する。
【００８６】
また、生成方法選択手段１１２は、一様乱数r が確率p{1-dim}より大きい場合、乱数の生成方法として棄却サンプリング法を選択する。選択した後、生成方法選択手段１１２は、棄却サンプリング装置１２０に乱数を生成するように指示する。
【００８７】
図５は、第１の実施形態の棄却サンプリング装置１２０の構成例を示すブロック図である。図５に示すように、本実施形態の棄却サンプリング装置１２０は、一様乱数生成手段１２１と、棄却判定手段１２２とを有する。
【００８８】
一様乱数生成手段１２１が有する機能は、一様乱数生成器９２２が有する機能と同様である。すなわち、一様乱数生成手段１２１は、{k∈Z|−(t・s −a)≦k ≦(t・s −a)} の範囲で一様乱数u1∈Z を生成する。
【００８９】
次いで、一様乱数生成手段１２１は、[0, φ (−a)] の範囲で実数値の乱数u2∈R を生成する。一様乱数生成手段１２１は、生成されたu1∈Z とu2∈R を棄却判定手段１２２に入力する。
【００９０】
また、棄却判定手段１２２が有する機能は、棄却判定器９２１が有する機能、および出力装置９２３が有する機能と同様である。すなわち、棄却判定手段１２２は、φ (u1−a)とu2∈R を比較する。比較した結果u2≦φ (u1−a)であれば、棄却判定手段１２２は、中心が原点でない１次元離散ガウス分布に従う乱数としてu1∈Z を出力する。
【００９１】
また、比較した結果u2＞φ (u1−a)であれば、棄却判定手段１２２は、最初のステップに戻り、同じ操作を再度実行する。
【００９２】
図６は、第１の実施形態の累積法サンプリング装置１３０の構成例を示すブロック図である。図６に示すように、本実施形態の累積法サンプリング装置１３０は、一様乱数生成手段１３１と、探索手段１３２と、記憶手段１３３と、出力手段１３４とを有する。
【００９３】
一様乱数生成手段１３１が有する機能は、一様乱数生成器９１３が有する機能と同様である。すなわち、一様乱数生成手段１３１は、実数値x ∈[0,1] を出力する。
【００９４】
また、探索手段１３２が有する機能は、探索器９１２が有する機能と同様である。すなわち、探索手段１３２は、記憶手段１３３に記憶されている各値の中からφ(z−a −1)≦x ＜φ(z−a)を満たすz ∈Z を二分探索する。
【００９５】
また、記憶手段１３３が有する機能は、記憶装置９１１が有する機能と同様である。すなわち、記憶手段１３３は、φ(0−a)/2, φ(1−a), φ(2−a), ・・・ ,φ(t・s −a)の各値を記憶する。
【００９６】
出力手段１３４は、探索手段１３２が探索した乱数を中心が原点でない１次元離散ガウス分布に従う乱数として出力する機能を有する。
【００９７】
本実施形態の乱数生成システム１００は、累積法による１次元離散ガウス分布に従う乱数の生成に掛かるメモリコストで、また毎回のサンプリング処理が累積法で実行されたときの計算コストに近い計算コストで、多次元格子上の離散ガウス分布に従う乱数を生成できる。
【００９８】
［動作の説明］
以下、本実施形態の乱数生成システム１００が中心が原点でない１次元離散ガウス分布に従う乱数を生成する動作を図７を参照して説明する。図７は、第１の実施形態の乱数生成システム１００による乱数生成処理の動作を示すフローチャートである。
【００９９】
最初に、区間一様乱数生成手段１１１は、区間[0, P]の一様乱数r を生成する（ステップS101）。区間一様乱数生成手段１１１は、生成された一様乱数r を生成方法選択手段１１２に入力する。
【０１００】
次いで、生成方法選択手段１１２は、入力された一様乱数r が確率p{1-dim}より大きいか否かを判定する（ステップS102）。
【０１０１】
一様乱数r が確率p{1-dim}より大きい場合（ステップS102におけるTrue）、生成方法選択手段１１２は、乱数のサンプリング処理の方法として棄却サンプリング法を選択する（ステップS103）。次いで、生成方法選択手段１１２は、棄却サンプリング装置１２０に乱数の生成を指示する。
【０１０２】
乱数の生成を指示された棄却サンプリング装置１２０は、棄却サンプリング法で中心が原点でない１次元離散ガウス分布に従う乱数を生成する（ステップS104）。生成した後、棄却サンプリング装置１２０は、生成された乱数を出力する（ステップS105）。出力した後、乱数生成システム１００は、乱数生成処理を終了する。
【０１０３】
一様乱数r が確率p{1-dim}以下である場合（ステップS102におけるFalse ）、生成方法選択手段１１２は、乱数のサンプリング処理の方法として累積法を選択する（ステップS106）。次いで、生成方法選択手段１１２は、累積法サンプリング装置１３０に乱数の生成を指示する。
【０１０４】
乱数の生成を指示された累積法サンプリング装置１３０は、累積法で中心が原点でない１次元離散ガウス分布に従う乱数を生成する（ステップS107）。累積法サンプリング装置１３０は、中心が原点である１次元離散ガウス分布を定める函数の値が用いられる累積法で乱数を生成する。
【０１０５】
生成した後、累積法サンプリング装置１３０は、生成された乱数を出力する（ステップS108）。出力した後、乱数生成システム１００は、乱数生成処理を終了する。ｎ次元格子上の離散ガウス分布に従う乱数が生成される場合、乱数生成システム１００は、図７に示す乱数生成処理をｎ回実行する。
【０１０６】
［効果の説明］
確率p{rjc}の値に比べて確率p{1-dim}の値が十分大きいため、生成方法選択手段１１２は、殆どの場合中心が原点である１次元離散ガウス分布を定める函数の値が用いられる累積法を乱数の生成方法として選択する。すなわち、本実施形態の乱数生成システム１００が使用されると、多次元格子上の離散ガウス分布に従う乱数が生成される際に毎回実行されるサンプリング処理が、殆どの確率で累積法によるサンプリング処理になる。
【０１０７】
よって、乱数生成システム１００による乱数生成処理全体に要するメモリコストは、中心が原点である１次元離散ガウス分布に従う乱数が累積法で生成される際に要するメモリコストと同程度の値まで削減される。
【０１０８】
また、乱数生成システム１００による乱数生成処理全体に要する計算コストは、毎回実行されるサンプリング処理が累積法によるサンプリング処理である場合に要する計算コストに近い値まで削減される。
【０１０９】
なお、本実施形態の乱数生成システム１００は、例えば、非一時的な記憶媒体に格納されているプログラムに従って処理を実行する中央処理装置(CPU(Central Processing Unit))等のプロセッサ、またはデータ処理装置によって実現されてもよい。すなわち、区間一様乱数生成手段１１１、生成方法選択手段１１２、一様乱数生成手段１２１、棄却判定手段１２２、一様乱数生成手段１３１、探索手段１３２、および出力手段１３４は、例えば、プログラム制御に従って処理を実行するCPU によって実現されてもよい。
【０１１０】
また、記憶手段１３３は、例えばRAM(Random Access Memory) で実現されてもよい。
【０１１１】
また、本実施形態の乱数生成システム１００における各部は、ハードウェア回路によって実現されてもよい。一例として、区間一様乱数生成手段１１１、生成方法選択手段１１２、一様乱数生成手段１２１、棄却判定手段１２２、一様乱数生成手段１３１、探索手段１３２、記憶手段１３３、および出力手段１３４が、それぞれLSI(Large Scale Integration)で実現される。また、それらが１つのLSI で実現されていてもよい。
【０１１２】
次に、本発明の概要を説明する。図８は、本発明による乱数生成システムの概要を示すブロック図である。本発明による乱数生成システム１０は、中心が正の値である１次元格子上の離散ガウス分布である第１離散分布に従う乱数を生成する乱数生成システムであって、第１離散分布において確率変数が正の範囲における所定の区間内の値になる確率である第１確率と０の間の一様乱数を生成する生成手段１１（例えば、区間一様乱数生成手段１１１）と、中心が原点である１次元格子上の離散ガウス分布である第２離散分布において確率変数が所定の区間内の値になる確率である第２確率以下の一様乱数が生成されると乱数の生成方法に第２離散分布を定める函数の値が用いられる累積法を選択し、第２確率よりも大きい一様乱数が生成されると乱数の生成方法に棄却サンプリング法を選択する選択手段１２（例えば、生成方法選択手段１１２）とを含む。
【０１１３】
そのような構成により、乱数生成システムは、多次元格子上の離散ガウス分布に従う乱数の生成に掛かるメモリコストと計算コストをより低減できる。
【０１１４】
また、乱数生成システム１０は、第２離散分布を定める函数の値が用いられる累積法で１次元格子上の離散ガウス分布に従う乱数を生成する累積法生成手段（例えば、累積法サンプリング装置１３０）を含み、選択手段１２は、累積法が選択された後に累積法生成手段に乱数の生成を指示し、累積法生成手段は、指示を受けて乱数を生成してもよい。また、累積法生成手段は、第２離散分布を定める函数の値が記憶されている記憶手段（例えば、記憶手段１３３）を有してもよい。
【０１１５】
そのような構成により、乱数生成システムは、累積法で中心が原点でない１次元格子上の離散ガウス分布に従う乱数を生成できる。
【０１１６】
また、乱数生成システム１０は、棄却サンプリング法で１次元格子上の離散ガウス分布に従う乱数を生成する棄却サンプリング法生成手段（例えば、棄却サンプリング装置１２０）を含み、選択手段１２は、棄却サンプリング法が選択された後に棄却サンプリング法生成手段に乱数の生成を指示し、棄却サンプリング法生成手段は、指示を受けて乱数を生成してもよい。
【０１１７】
そのような構成により、乱数生成システムは、棄却サンプリング法で中心が原点でない１次元格子上の離散ガウス分布に従う乱数を生成できる。
【０１１８】
以上、実施形態および実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１１９】
また、上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下に限られない。
【０１２０】
（付記１）中心が負の値である１次元格子上の離散ガウス分布である第３離散分布に従う乱数を生成する乱数生成システムであって、前記第３離散分布において確率変数が負の範囲における所定の区間内の値になる確率である第３確率と０の間の一様乱数を生成する生成手段と、中心が原点である前記１次元格子上の離散ガウス分布である第４離散分布において確率変数が前記所定の区間内の値になる確率である第４確率以下の一様乱数が生成されると前記乱数の生成方法に前記第４離散分布を定める函数の値が用いられる累積法を選択し、前記第４確率よりも大きい一様乱数が生成されると前記乱数の生成方法に棄却サンプリング法を選択する選択手段とを含むことを特徴とする乱数生成システム。
【０１２１】
（付記２）第４離散分布を定める函数の値が用いられる累積法で１次元格子上の離散ガウス分布に従う乱数を生成する累積法生成手段を含み、選択手段は、累積法が選択された後に前記累積法生成手段に乱数の生成を指示し、前記累積法生成手段は、指示を受けて乱数を生成する付記１記載の乱数生成システム。
【０１２２】
（付記３）累積法生成手段は、第４離散分布を定める函数の値が記憶されている記憶手段を有する付記２記載の乱数生成システム。
【０１２３】
（付記４）棄却サンプリング法で１次元格子上の離散ガウス分布に従う乱数を生成する棄却サンプリング法生成手段を含み、選択手段は、棄却サンプリング法が選択された後に前記棄却サンプリング法生成手段に乱数の生成を指示し、前記棄却サンプリング法生成手段は、指示を受けて乱数を生成する付記１から付記３のうちのいずれか１項に記載の乱数生成システム。
【０１２４】
（付記５）中心が負の値である１次元格子上の離散ガウス分布である第３離散分布に従う乱数を生成する乱数生成システムで実行される乱数生成方法であって、前記第３離散分布において確率変数が負の範囲における所定の区間内の値になる確率である第３確率と０の間の一様乱数を生成し、中心が原点である前記１次元格子上の離散ガウス分布である第４離散分布において確率変数が前記所定の区間内の値になる確率である第４確率以下の一様乱数が生成されると前記乱数の生成方法に前記第４離散分布を定める函数の値が用いられる累積法を選択し、前記第４確率よりも大きい一様乱数が生成されると前記乱数の生成方法に棄却サンプリング法を選択することを特徴とする乱数生成方法。
【０１２５】
（付記６）中心が負の値である１次元格子上の離散ガウス分布である第３離散分布に従う乱数を生成するコンピュータで実行される乱数生成プログラムであって、前記コンピュータに、前記第３離散分布において確率変数が負の範囲における所定の区間内の値になる確率である第３確率と０の間の一様乱数を生成する生成処理、中心が原点である前記１次元格子上の離散ガウス分布である第４離散分布において確率変数が前記所定の区間内の値になる確率である第４確率以下の一様乱数が生成されると前記乱数の生成方法に前記第４離散分布を定める函数の値が用いられる累積法を選択する第３選択処理、および前記第４確率よりも大きい一様乱数が生成されると前記乱数の生成方法に棄却サンプリング法を選択する第４選択処理を実行させるための乱数生成プログラム。
【符号の説明】
【０１２６】
１０、１００、９１０、９２０  乱数生成システム
１１  生成手段
１２  選択手段
１１０  生成方法選択装置
１１１  区間一様乱数生成手段
１１２  生成方法選択手段
１２０  棄却サンプリング装置
１２１、１３１  一様乱数生成手段
１２２  棄却判定手段
１３０  累積法サンプリング装置
１３２  探索手段
１３３  記憶手段
１３４  出力手段
９１１  記憶装置
９１２  探索器
９１３、９２２  一様乱数生成器
９２１  棄却判定器
９２３  出力装置
【図１】
2019030799.tif 000008
【図２】
2019030799.tif 000009
【図３】
2019030799.tif 000010
【図４】
2019030799.tif 000011
【図５】
2019030799.tif 000012
【図６】
2019030799.tif 000013
【図７】
2019030799.tif 000014
【図８】
2019030799.tif 000015
【図９】
2019030799.tif 000016
【図１０】
2019030799.tif 000017
【図１１】
2019030799.tif 000018
【図１２】
2019030799.tif 000019
【国際調査報告】
2019030799.tif 000020
2019030799.tif 000021