(57)【特許請求の範囲】
【請求項１】
整数区間［０，ｒ−１］に対して、ｒ−１を２進数で表現可能な最小のビット数ｍをビット数として有するランダムな２進乱数列（ｂ０ｂ１…ｂｍ−１）を生成する２進乱数列生成部と、
前記２進乱数列（ｂ０ｂ１…ｂｍ−１）を整数に変換する整数変換部と、
前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属するか否かを判断して、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属しない場合には、前記２進乱数列生成部に前記２進乱数列（ｂ０ｂ１…ｂｍ−１）に対する更新を要請し、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属する場合には、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数を整数乱数として出力する整数乱数出力部とを含み、
前記２進乱数列生成部は、前記整数乱数出力部の更新要請に応じて、ランダムな追加２進乱数列を生成し、前記生成された追加２進乱数列と前記２進乱数列（ｂ０ｂ１…ｂｍ−１）とを組み合わせて算出した２進乱数列に前記２進乱数列（ｂ０ｂ１…ｂｍ−１）を更新することを特徴とする、２進乱数列を整数乱数に変換する装置。｛ここで、ｒは、１より大きい整数である。｝
【請求項２】
前記２進乱数列生成部は、前記整数乱数出力部の更新要請に応じて、ｂｉ＞ｒｉに相当するｉの最小値であるｄを算出してｄ＋１のビット数を有するランダムな追加２進乱数列（ｂｍｂｍ＋１…ｂｍ＋ｄ）を生成し、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）と前記追加２進乱数列（ｂｍｂｍ＋１…ｂｍ＋ｄ）に基づいて算出した２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｍ＋ｄ）に前記２進乱数列（ｂ０ｂ１…ｂｍ−１）を更新することを特徴とする、請求項１に記載の２進乱数列を整数乱数に変換する装置。｛ここで、ｂｉは、２進乱数列（ｂ０ｂ１…ｂｍ−１）のｉ番目ビット値であり、ｒｉは、ｒ−１をビット数ｍを有する２進数列（ｒ０ｒ１…ｒｍ−１）で表現した時のｉ番目ビット値である。｝
【請求項３】
前記整数変換部は、前記２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｍ＋ｄ）に更新された２進乱数列（ｂ０ｂ１…ｂｍ−１）を整数に変換し、
前記整数乱数出力部は、前記更新された２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属するか否かを判断して、前記更新された２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属する場合には、前記更新された２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数を整数乱数として出力することを特徴とする、請求項２に記載の２進乱数列を整数乱数に変換する装置。
【請求項４】
整数区間［０，ｒｎ−１］に対して、ｒｎ−１を２進数で表現可能な最小のビット数ｋをビット数として有するランダムな２進乱数列（ｂ０ｂ１…ｂｋ−１）を生成する２進乱数列生成部と、
前記２進乱数列（ｂ０ｂ１…ｂｋ−１）を整数（ａ）に変換する整数変換部と、
前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）が前記整数区間［０，ｒｎ−１］に属するか否かを判断して、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数が前記整数区間［０，ｒｎ−１］に属しない場合には、前記２進乱数列生成部に前記２進乱数列（ｂ０ｂ１…ｂｋ−１）に対する更新を要請し、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）が前記整数区間［０，ｒｎ−１］に属する場合には、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）に対して、
【数１】
0005636489.tif 000015
に基づいて算出したｎ個の整数乱数（ａ０，…，ａｎ−１）で構成される整数乱数列（ａ０ａ１…ａｎ−１）を出力する整数乱数列出力部とを含み、
前記２進乱数列生成部は、前記整数乱数列出力部の更新要請に応じて、ランダムな追加２進乱数列を生成し、前記生成された追加２進乱数列と前記２進乱数列（ｂ０ｂ１…ｂｋ−１）とを組み合わせて算出した２進乱数列に前記２進乱数列（ｂ０ｂ１…ｂｋ−１）を更新することを特徴とする、２進乱数列を整数乱数列に変換する装置。（ここで、ｒは、１より大きい整数である。）
【請求項５】
前記２進乱数列生成部は、前記整数乱数列出力部の更新要請に応じて、ｂｉ＞ｒｉに相当するｉの最小値であるｄを算出してｄ＋１のビット数を有するランダムな追加２進乱数列（ｂｋｂｋ＋１…ｂｋ＋ｄ）を生成し、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）と前記追加２進乱数列（ｂｋｂｋ＋１…ｂｋ＋ｄ）に基づいて算出した２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｋ＋ｄ）に前記２進乱数列（ｂ０ｂ１…ｂｋ−１）を更新することを特徴とする、請求項４に記載の２進乱数列を整数乱数列に変換する装置。｛ここで、ｂｉは、２進乱数列（ｂ０ｂ１…ｂｋ−１）のｉ番目ビット値であり、ｒｉは、ｒｎ−１をビット数ｋを有する２進数列（ｒ０ｒ１…ｒｋ−１）で表現した時のｉ番目ビット値である。｝
【請求項６】
前記整数変換部は、前記２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｋ＋ｄ）に更新された２進乱数列（ｂ０ｂ１…ｂｋ−１）を整数（ａ）に変換し、
前記整数乱数列出力部は、前記更新された２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）が前記整数区間［０，ｒｎ−１］に属するか否かを判断して、前記更新された２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）が前記整数区間［０，ｒｎ−１］に属する場合には、前記更新された２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）に対して、
【数２】
0005636489.tif 000016
に基づいて算出したｎ個の整数乱数（ａ０，ａ１，…，ａｎ−１）で構成される整数乱数列（ａ０ａ１…ａｎ−１）を出力することを特徴とする、請求項５に記載の２進乱数列を整数乱数列に変換する装置。
【請求項７】
ランダムな２進乱数列を生成する第１ステップと、
前記２進乱数列を整数に変換する第２ステップと、
前記２進乱数列から変換された整数が予め設定された整数区間に属するか否かを判断する第３ステップと、
前記２進乱数列から変換された整数が予め設定された整数区間に属する場合、前記２進乱数列から変換された整数に基づいて算出した整数乱数または整数乱数列を出力する第４ステップと、
前記２進乱数列から変換された整数が予め設定された整数区間に属しない場合、ランダムな追加２進乱数列を生成し、前記生成された追加２進乱数列と前記２進乱数列とを組み合わせて算出した２進乱数列に前記２進乱数列を更新して前記第２ステップないし第４ステップを繰り返し行う第５ステップとを含むことを特徴とする、２進乱数列を整数乱数に変換する方法。
【請求項８】
前記ランダムな２進乱数列を生成する第１ステップは、
整数区間［０，ｒ−１］に対して、ｒ−１を２進数で表現可能な最小のビット数ｍをビット数として有するランダムな２進乱数列（ｂ０ｂ１…ｂｍ−１）を生成することを特徴とする、請求項７に記載の２進乱数列を整数乱数に変換する方法。｛ここで、ｒは、１より大きい整数である。｝
【請求項９】
前記ランダムな２進乱数列を生成する第１ステップは、
整数区間［０，ｒｎ−１］に対して、ｒｎ−１を２進数で表現可能な最小のビット数ｋをビット数として有するランダムな２進乱数列（ｂ０ｂ１…ｂｋ−１）を生成することを特徴とする、請求項７に記載の２進乱数列を整数乱数に変換する方法。｛ここで、ｒは、１より大きい整数である。｝
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２進乱数列を整数乱数に変換する装置および方法に関するものであって、より詳細には、ランダムに生成した２進乱数列を整数乱数に変換した後、当該整数乱数が予め定めた整数区間範囲に含まれるかを確認し、ランダムな２進乱数列から生成された整数乱数が予め定めた整数区間範囲に含まれない場合には、当該整数区間に含まれる整数乱数が算出されるまで、２進乱数列を繰り返し更新することによって、予め定めた整数区間に含まれ、かつ、分布が均一な整数乱数を出力できるようにする２進乱数列を整数乱数に変換する装置および方法に関するものである。
【背景技術】
【０００２】
一般的に、乱数生成器は、所与の初期値を用いてランダムな２進数列または整数列を生成するための手段であって、用途に応じて多様な決定的アルゴリズムを選択的に使用することができる。ランダムな２進数列を出力する乱数生成器は、主に、ブロック暗号、ハッシュ関数などの秘密鍵暗号技術を基盤として構成され、効率性に優れているが、ランダム整数列を出力する乱数生成器は、整数に対する数学的演算を活用して構成されるため、効率性に優れない。したがって、公開鍵暗号、署名など、比較的大きさの大きい整数を用いる暗号基盤技術で要求される乱数を生成する場合には、２進数列を出力する乱数生成器を活用して、生成したランダム２進数列を特定範囲の整数に変換してランダムな整数列を生成することによって、効率性を図ったりする。
【０００３】
このような変換のために、従来既に知られた方法としては、米国国立標準技術研究所であるＮＩＳＴ（Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ）で発行した文書８００−９０Ａの「Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  ｆｏｒ  Ｒａｎｄｏｍ  Ｎｕｍｂｅｒ  Ｇｅｎｅｒａｔｉｏｎ  Ｕｓｉｎｇ  Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｒａｎｄｏｍ  Ｂｉｔ  Ｇｅｎｅｒａｔｏｒｓ」（Ｅｌａｉｎｅ  Ｂａｒｋｅｒ  ａｎｄ  Ｊｏｈｎ  Ｋｅｌｓｅｙ、２０１２．１）で明示している方法がある。特に、「Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  ｆｏｒ  Ｒａｎｄｏｍ  Ｎｕｍｂｅｒ  Ｇｅｎｅｒａｔｉｏｎ  Ｕｓｉｎｇ  Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｒａｎｄｏｍ  Ｂｉｔ  Ｇｅｎｅｒａｔｏｒｓ」で開示している方法の中では、出力整数の分布が均一分布に従うことによって乱数性が保障できるが、使用されずに捨てられる２進数列が発生する単純廃棄手法（Ｓｉｍｐｌｅ  Ｄｉｓｃａｒｄ  Ｍｅｔｈｏｄ、ＳＤＭ）と複合廃棄手法（Ｃｏｍｐｌｅｘ  Ｄｉｓｃａｒｄ  Ｍｅｔｈｏｄ、ＣＤＭ）、そして、所与の２進数列はすべて活用するが、出力整数の分布が均一分布に従わずにスキュー（ｓｋｅｗ）が発生する単純モジュラー手法（Ｓｉｍｐｌｅ  Ｍｏｄｕｌａｒ  Ｍｅｔｈｏｄ、ＳＭＭ）と複合モジュラー手法（Ｃｏｍｐｌｅｘ  Ｍｏｄｕｌａｒ  Ｍｅｔｈｏｄ、ＣＭＭ）がある。
【０００４】
単純廃棄手法と複合廃棄手法は、所与の２進数列の整数表現が当該区間に含まれるかを確認して、そうでない場合、所与の２進数列を廃棄し、新たな２進数列を生成して再確認する方式であり、単純モジュラー手法と複合モジュラー手法は、所与の２進数列を整数で表現した後、所与の区間によって定義される特定の整数で除した余りを取る方式である。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、ランダム２進数列に基づいて出力される整数の分布が均一分布に従い、かつ、使用されずに廃棄される２進数列の量を最小化する乱数変換手法を提供することである。
【課題を解決するための手段】
【０００６】
上記の目的を達成するための、本発明の一実施形態にかかる２進乱数列を整数乱数に変換する装置は、整数区間［０，ｒ−１］に対して、ｒ−１を２進数で表現可能な最小のビット数ｍをビット数として有するランダムな２進乱数列（ｂ０ｂ１…ｂｍ−１）を生成する２進乱数列生成部と、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）を整数に変換する整数変換部と、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属するか否かを判断して、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属しない場合には、前記２進乱数列生成部に前記２進乱数列（ｂ０ｂ１…ｂｍ−１）に対する更新を要請し、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属する場合には、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数を整数乱数として出力する整数乱数出力部とを含み、前記２進乱数列生成部は、前記整数乱数出力部の更新要請に応じて、ランダムな追加２進乱数列を生成し、前記生成された追加２進乱数列と前記２進乱数列（ｂ０ｂ１…ｂｍ−１）とを組み合わせて算出した２進乱数列に前記２進乱数列（ｂ０ｂ１…ｂｍ−１）を更新することを特徴をする。ここで、ｒは、１より大きい整数である。
【０００７】
この時、前記２進乱数列生成部は、前記整数乱数出力部の更新要請に応じて、ｂｉ＞ｒｉに相当するｉの最小値であるｄを算出してｄ＋１のビット数を有するランダムな追加２進乱数列（ｂｍｂｍ＋１…ｂｍ＋ｄ）を生成し、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）と前記追加２進乱数列（ｂｍｂｍ＋１…ｂｍ＋ｄ）に基づいて算出した２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｍ＋ｄ）に前記２進乱数列（ｂ０ｂ１…ｂｍ−１）を更新することができる。ここで、ｂｉは、２進乱数列（ｂ０ｂ１…ｂｍ−１）のｉ番目ビット値であり、ｒｉは、ｒ−１をビット数ｍを有する２進数列（ｒ０ｒ１…ｒｍ−１）で表現した時のｉ番目ビット値である。
【０００８】
この時、前記整数変換部は、前記２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｍ＋ｄ）に更新された２進乱数列（ｂ０ｂ１…ｂｍ−１）を整数に変換し、前記整数乱数出力部は、前記更新された２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属するか否かを判断して、前記更新された２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属する場合には、前記更新された２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数を整数乱数として出力することができる。ここで、前記整数変換部は、前記２進乱数列生成部によって更新された２進乱数列から変換される整数が前記整数区間［０，ｒ−１］に属するまで、前記２進乱数列生成部に新たな追加２進乱数列（ｂｍｂｍ＋１…ｂｍ＋ｄ）の生成および２進乱数列の再更新動作を繰り返し行うように要請することができる。
【０００９】
また、上記の目的を達成するための、本発明の他の実施形態にかかる２進乱数列を整数乱数列に変換する装置は、整数区間［０，ｒｎ−１］に対して、ｒｎ−１を２進数で表現可能な最小のビット数ｋをビット数として有するランダムな２進乱数列（ｂ０ｂ１…ｂｋ−１）を生成する２進乱数列生成部と、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）を整数（ａ）に変換する整数変換部と、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）が前記整数区間［０，ｒｎ−１］に属するか否かを判断して、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数が前記整数区間［０，ｒｎ−１］に属しない場合には、前記２進乱数列生成部に前記２進乱数列（ｂ０ｂ１…ｂｋ−１）に対する更新を要請し、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）が前記整数区間［０，ｒｎ−１］に属する場合には、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）に対して、
【数１】
0005636489.tif 000002
【００１０】
に基づいて算出したｎ個の整数乱数（ａ０，…，ａｎ−１）で構成される整数乱数列（ａ０ａ１…ａｎ−１）を出力する整数乱数列出力部とを含み、前記２進乱数列生成部は、前記整数乱数列出力部の更新要請に応じて、ランダムな追加２進乱数列を生成し、前記生成された追加２進乱数列と前記２進乱数列（ｂ０ｂ１…ｂｋ−１）とを組み合わせて算出した２進乱数列に前記２進乱数列（ｂ０ｂ１…ｂｋ−１）を更新することを特徴とする。
【００１１】
この時、前記２進乱数列生成部は、前記整数乱数列出力部の更新要請に応じて、ｂｉ＞ｒｉに相当するｉの最小値であるｄを算出してｄ＋１のビット数を有するランダムな追加２進乱数列（ｂｋｂｋ＋１…ｂｋ＋ｄ）を生成し、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）と前記追加２進乱数列（ｂｋｂｋ＋１…ｂｋ＋ｄ）に基づいて算出した２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｋ＋ｄ）に前記２進乱数列（ｂ０ｂ１…ｂｋ−１）を更新することができる。ここで、ｂｉは、２進乱数列（ｂ０ｂ１…ｂｋ−１）のｉ番目ビット値であり、ｒｉは、ｒｎ−１をビット数ｋを有する２進数列（ｒ０ｒ１…ｒｋ−１）で表現した時のｉ番目ビット値である。
【００１２】
この時、前記整数変換部は、前記２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｋ＋ｄ）に更新された２進乱数列（ｂ０ｂ１…ｂｋ−１）を整数（ａ）に変換し、前記整数乱数列出力部は、前記更新された２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）が前記整数区間［０，ｒｎ−１］に属するか否かを判断して、前記更新された２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）が前記整数区間［０，ｒｎ−１］に属する場合には、前記更新された２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）に対して、
【数２】
0005636489.tif 000003
【００１３】
に基づいて算出したｎ個の整数乱数（ａ０，ａ１，…，ａｎ−１）で構成される整数乱数列（ａ０ａ１…ａｎ−１）を出力することができる。ここで、前記整数変換部は、前記２進乱数列生成部によって更新された２進乱数列から変換される整数（ａ）が前記整数区間［０，ｒｎ−１］に属するまで、前記２進乱数列生成部に新たな追加２進乱数列（ｂｋｂｋ＋１…ｂｋ＋ｄ）の生成および２進乱数列の再更新動作を繰り返し行うように要請することができる。
【００１４】
一方、上記の目的を達成するための、本発明の一実施形態にかかる２進乱数列を整数乱数に変換する方法は、ランダムな２進乱数列を生成する第１ステップと、前記２進乱数列を整数に変換する第２ステップと、前記２進乱数列から変換された整数が予め設定された整数区間に属するか否かを判断する第３ステップと、前記２進乱数列から変換された整数が予め設定された整数区間に属する場合、前記２進乱数列から変換された整数に基づいて算出した整数乱数を出力する第４ステップと、前記２進乱数列から変換された整数が予め設定された整数区間に属しない場合、ランダムな追加２進乱数列を生成し、前記生成された追加２進乱数列と前記２進乱数列とを組み合わせて算出した２進乱数列に前記２進乱数列を更新して前記第２ステップないし第４ステップを繰り返し行う第５ステップとを含むことを特徴とする。
【００１５】
この時、前記ランダムな２進乱数列を生成する第１ステップでは、整数区間［０，ｒ−１］に対して、ｒ−１を２進数で表現可能な最小のビット数ｍをビット数として有するランダムな２進乱数列（ｂ０ｂ１…ｂｍ−１）を生成することができる。
【００１６】
この時、前記２進乱数列を整数に変換する第２ステップでは、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）を整数に変換することができる。
【００１７】
この時、前記２進乱数列から変換された整数が予め設定された整数区間に属するか否かを判断する第３ステップでは、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属するか否かを判断することができる。
【００１８】
この時、前記２進乱数列から変換された整数に基づいて算出した整数乱数を出力する第４ステップでは、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属する場合、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数を整数乱数として出力することができる。
【００１９】
この時、前記２進乱数列を更新して前記第２ステップないし第４ステップを繰り返し行う第５ステップでは、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属しない場合、ｂｉ＞ｒｉに相当するｉの最小値であるｄを算出してｄ＋１のビット数を有するランダムな追加２進乱数列（ｂｍｂｍ＋１…ｂｍ＋ｄ）を生成し、前記２進乱数列（ｂ０ｂ１…ｂｍ−１）と前記追加２進乱数列（ｂｍｂｍ＋１…ｂｍ＋ｄ）に基づいて算出した２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｍ＋ｄ）に２進乱数列（ｂ０ｂ１…ｂｍ−１）を更新して前記第２ステップないし第４ステップを繰り返し行うことができる。
【００２０】
この時、前記２進乱数列を更新して前記第２ステップないし第４ステップを繰り返し行う第５ステップでは、前記２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｍ＋ｄ）に更新された２進乱数列（ｂ０ｂ１…ｂｍ−１）から変換された整数が前記整数区間［０，ｒ−１］に属するまで、前記第２ステップないし第４ステップを繰り返し行うことができる。
【００２１】
また、上記の目的を達成するための、本発明の他の実施形態にかかる２進乱数列を整数乱数列に変換する方法は、ランダムな２進乱数列を生成する第１ステップと、前記２進乱数列を整数に変換する第２ステップと、前記２進乱数列から変換された整数が予め設定された整数区間に属するか否かを判断する第３ステップと、前記２進乱数列から変換された整数が予め設定された整数区間に属する場合、前記２進乱数列から変換された整数に基づいて算出した整数乱数列を出力する第４ステップと、前記２進乱数列から変換された整数が予め設定された整数区間に属しない場合、ランダムな追加２進乱数列を生成し、前記生成された追加２進乱数列と前記２進乱数列とを組み合わせて算出した２進乱数列に前記２進乱数列を更新して前記第２ステップないし第４ステップを繰り返し行う第５ステップとを含むことを特徴とする。
【００２２】
一方、前記ランダムな２進乱数列を生成する第１ステップでは、整数区間［０，ｒｎ−１］に対して、ｒｎ−１を２進数で表現可能な最小のビット数ｋをビット数として有するランダムな２進乱数列（ｂ０ｂ１…ｂｋ−１）を生成することができる。
【００２３】
この時、前記２進乱数列を整数に変換する第２ステップでは、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）を整数（ａ）に変換することができる。
【００２４】
この時、前記２進乱数列から変換された整数が予め設定された整数区間に属するか否かを判断する第３ステップでは、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）が前記整数区間［０，ｒｎ−１］に属するか否かを判断することができる。
【００２５】
この時、前記２進乱数列から変換された整数に基づいて算出した整数乱数列を出力する第４ステップでは、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）が前記整数区間［０，ｒｎ−１］に属する場合、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）に対して、
【数３】
0005636489.tif 000004
【００２６】
に基づいて算出したｎ個の整数乱数（ａ０，ａ１，…，ａｎ−１）で構成される整数乱数列（ａ０ａ１…ａｎ−１）を出力することができる。
【００２７】
この時、前記２進乱数列を更新して前記第２ステップないし第４ステップを繰り返し行う第５ステップでは、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数が前記整数区間［０，ｒｎ−１］に属しない場合、ｂｉ＞ｒｉに相当するｉの最小値であるｄを算出してｄ＋１のビット数を有するランダムな追加２進乱数列（ｂｋｂｋ＋１…ｂｋ＋ｄ）を生成し、前記２進乱数列（ｂ０ｂ１…ｂｋ−１）と前記追加２進乱数列（ｂｋｂｋ＋１…ｂｋ＋ｄ）に基づいて算出した２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｋ＋ｄ）に２進乱数列（ｂ０ｂ１…ｂｋ−１）を更新して前記第２ステップないし第４ステップを繰り返し行うことができる。
【００２８】
この時、前記２進乱数列を更新して前記第２ステップないし第４ステップを繰り返し行う第５ステップでは、前記２進乱数列（ｂｄ＋１ｂｄ＋２…ｂｋ＋ｄ）に更新された２進乱数列（ｂ０ｂ１…ｂｋ−１）から変換された整数（ａ）が前記整数区間［０，ｒｎ−１］に属するまで、前記第２ステップないし第４ステップを繰り返し行うことができる。
【発明の効果】
【００２９】
本発明によれば、２進乱数列から変換された整数が予め定めた区間に含まれない場合、廃棄するビット数が、整数を生成するために選択されたビット数より少ない効果がある。
【００３０】
また、本発明によれば、２進乱数列から変換された整数が予め定めた整数区間に含まれない場合、選択されたビットをすべて廃棄する従来の単純廃棄手法および複合廃棄手法に比べて、同じ個数の整数を出力するために必要なビット数が少ないので効率的である。
【００３１】
さらに、本発明によれば、２進乱数列を生成する乱数生成器の動作回数を減少させることによって、乱数生成器を用いるシステムの効率性が全体的に増大する効果がある。
【図面の簡単な説明】
【００３２】
【図１】単純部分廃棄手法（ＳＰＤＭ）によって整数乱数を出力する、本発明の一実施形態にかかる２進乱数列を整数乱数に変換する装置の構成を説明するためのブロック図である。
【図２】複合部分廃棄手法（ＣＰＤＭ）によって整数乱数列を出力する、本発明の他の実施形態にかかる２進乱数列を整数乱数列に変換する装置の構成を説明するためのブロック図である。
【図３】本発明にかかる２進乱数列を整数乱数に変換する方法を説明するためのフローチャートである。
【図４】単純部分廃棄手法（ＳＰＤＭ）によって２進乱数列を整数乱数に変換する方法を説明するためのフローチャートである。
【図５】複合部分廃棄手法（ＣＰＤＭ）によって２進乱数列を整数乱数列に変換する方法を説明するためのフローチャートである。
【発明を実施するための形態】
【００３３】
以下、本発明を添付した図面を参照して詳細に説明する。ここで、繰り返される説明、本発明の要旨を不明にする可能性がある公知の機能、および構成に関する詳細な説明は省略する。本発明の実施形態は、当業界における平均的な知識を有する者に本発明をより完全に説明するために提供されるものである。したがって、図面における要素の形状および大きさなどは、より明確な説明のために誇張されることがある。
【００３４】
本発明にかかるランダム２進乱数列を整数乱数または整数乱数列に変換する手法は、ランダムに選定される２進乱数列を１つの整数乱数または複数の整数乱数からなる整数乱数列に変換する。特に、本発明では、ランダムに選定される２進乱数列を１つの整数乱数に変換する手法を単純部分廃棄手法（Ｓｉｍｐｌｅ  Ｐａｒｔｉａｌ  Ｄｉｓｃａｒｄ  Ｍｅｔｈｏｄ、ＳＰＤＭ）と定義し、ランダムに選定される２進乱数列を複数の整数乱数からなる整数乱数列に変換する手法を複合部分廃棄手法（Ｃｏｍｐｌｅｘ  Ｐａｒｔｉａｌ  Ｄｉｓｃａｒｄ  Ｍｅｔｈｏｄ、ＣＰＤＭ）と定義する。一方、本発明にかかる単純部分廃棄手法または複合部分廃棄手法によって閉区間［α，β］に設定される範囲に含まれる１つの整数乱数または複数の整数乱数からなる整数乱数列を出力するにあたり、β−α値をｒ−１と定義し、閉区間［０，ｒ−１］（ここで、ｒは、１より大きい整数）の範囲に含まれる１つの整数ｔ（ここで、０≦ｔ≦ｒ−１）または複数の整数ａ０，…，ａｎ−１（ここで、０≦ａ０，…，ａｎ−１≦ｒ−１）を算出し、算出された１つの整数ｔまたは複数の整数ａ０，…，ａｎ−１にαを加えて出力する方式が使用できる。
【００３５】
以下では、図１および図２を参照して、本発明にかかる２進乱数列を整数乱数に変換する装置の構成およびその動作について説明する。
【００３６】
図１は、ランダム２進乱数列を１つの整数乱数に変換する単純部分廃棄手法（ＳＰＤＭ）によって整数乱数を出力する、本発明の一実施形態にかかる２進乱数列を整数乱数に変換する装置の構成を説明するためのブロック図である。
【００３７】
図１を参照すれば、本発明の単純部分廃棄手法によって２進乱数列を整数乱数に変換する装置１００は、２進乱数列生成部１２０と、整数変換部１４０と、整数乱数出力部１６０とを含む。
【００３８】
２進乱数列生成部１２０は、ランダムな２進乱数列を生成し、生成された初期２進乱数列を整数変換部１４０に伝達する。ここで、整数乱数出力部１６０が整数区間［０，ｒ−１］内に含まれる整数乱数を出力するようにするために、２進乱数列生成部１２０は、ｒ−１を２進数で表現するのに必要な最小限のビット数ｍをビット数として有するランダムな２進乱数列ｂ０ｂ１…ｂｍ−１を生成し、ランダムな２進乱数列ｂ０ｂ１…ｂｍ−１を整数変換部１４０に伝達する。２進乱数列生成部１２０によって生成される２進ビット列ｂ０ｂ１…ｂｍ−１のビット数ｍは、下記の数４によって生成できる。
【数４】
0005636489.tif 000005
【００３９】
ここで、演算記号＜ｘ＞は、ｘより大きいか等しい最小の整数を表す演算記号である。
【００４０】
一方、［０，ｒ−１］の範囲に設定される整数区間において、ｒ−１は、下記の数５のように表される。
【数５】
0005636489.tif 000006
【００４１】
また、２進乱数列生成部１２０は、整数乱数出力部１６０の要請に応じて、ランダムな追加２進乱数列としてｄ＋１のビット数を有する２進乱数列ｂｍｂｍ＋１…ｂｍ＋ｄを生成し、２進乱数列ｂ０ｂ１…ｂｍ−１のビットと追加的に生成した２進乱数列ｂｍｂｍ＋１…ｂｍ＋ｄのビットに基づいて２進乱数列ｂｄ＋１ｂｄ＋２…ｂｍ＋ｄを算出し、算出されたｂｄ＋１ｂｄ＋２…ｂｍ＋ｄに２進乱数列ｂ０ｂ１…ｂｍ−１を更新する。より具体的には、２進乱数列生成部１２０は、整数乱数出力部１６０からｄ＋１のビット数を有するランダムな追加２進乱数列を生成させる要請がある場合、ｄ＋１のビット数を有する追加２進乱数列ｂｍｂｍ＋１…ｂｍ＋ｄを生成し、追加２進乱数列ｂｍｂｍ＋１…ｂｍ＋ｄと既存の２進乱数列ｂ０ｂ１…ｂｍ−１とを組み合わせて算出したｂｄ＋１ｂｄ＋２…ｂｍ＋ｄに既存の２進乱数列ｂ０ｂ１…ｂｍ−１を更新する。これによって、２進乱数列生成部１２０から整数変換部１４０に伝達される２進乱数列は、順次に各ビット値がｂｄ＋１ｂｄ＋２…ｂｍ＋ｄの各ビット値に切り替えられた２進乱数列ｂ０ｂ１…ｂｍ−１に相当する。
【００４２】
整数変換部１４０は、２進乱数列生成部１２０から受信した２進乱数列を整数に変換し、変換された整数を整数乱数出力部１６０に伝達する。この時、整数変換部１４０は、２進乱数列生成部１２０からｍのビット数を有する２進乱数列ｂ０ｂ１…ｂｍ−１を受信し、下記の数６に基づいて受信された２進乱数列ｂ０ｂ１…ｂｍ−１を整数ｔに変換する。
【数６】
0005636489.tif 000007
【００４３】
ここで、ｔは、２進乱数列ｂ０ｂ１…ｂｍ−１から変換される整数であり、ｂｉは、前記２進乱数列ｂ０ｂ１…ｂｍ−１におけるｉ番目ビット値を意味する。
【００４４】
整数変換部１４０が２進乱数列生成部１２０から受信する２進乱数列ｂ０ｂ１…ｂｍ−１は、２進乱数列生成部１２０によって初期に生成されたり、追加２進乱数列ｂｍｂｍ＋１…ｂｍ＋ｄに基づいて更新された２進乱数列ｂ０ｂ１…ｂｍ−１に相当する。
【００４５】
整数乱数出力部１６０は、２進乱数列から変換された整数を整数変換部１４０から受信し、２進乱数列から変換された整数が予め設定された整数区間に相応するか否かを判断して、前記変換された整数が予め設定された整数区間に相応する場合には、当該整数を整数乱数として出力する。より具体的には、整数乱数出力部１６０は、２進乱数列生成部１２０によって生成または更新された２進乱数列ｂ０ｂ１…ｂｍ−１から変換された整数ｔを整数変換部１４０から受信し、受信された整数ｔが整数区間［０，ｒ−１］内に含まれるか否かを確認する。仮に、受信された整数ｔが整数区間［０，ｒ−１］内に含まれる場合（０≦ｔ≦ｒ−１の場合）には、整数乱数出力部１６０は、整数ｔを整数乱数として出力する。この時、整数乱数出力部１６０は、整数区間［０，ｒ−１］内に含まれる整数ｔにαを加えて出力することができる。
【００４６】
反面、受信された整数ｔが整数区間［０，ｒ−１］内に含まれない場合（ｔ＞ｒ−１の場合）には、整数乱数出力部１６０は、ｂｉ＞ｒｉとなるｉの最小値に相当するｄを算出する。この時、整数乱数出力部１６０は、下記の数７を満足するｄを算出する。
【数７】
0005636489.tif 000008
【００４７】
ここで、ＴとＲはそれぞれ、整数ｔとｒ−１を同じビット数を有する２進数で表現した値を意味し、
【数８】
0005636489.tif 000009
【００４８】
は、ＸＯＲ（ｅＸｃｌｕｓｉｖｅ  ＯＲ）演算記号を意味する。
【００４９】
整数乱数出力部１６０は、受信された整数ｔが整数区間［０，ｒ−１］内に含まれずにｄを算出した場合、２進乱数列生成部１２０にｄ＋１のビット数を有するランダムな追加２進乱数列ｂｍｂｍ＋１…ｂｍ＋ｄを生成し、２進乱数列ｂ０ｂ１…ｂｍ−１を更新するように要請する。
【００５０】
本発明の単純部分廃棄手法によって２進乱数列を整数乱数に変換する装置１００は、整数変換部１４０から出力される整数ｔが整数区間［０，ｒ−１］内に含まれるまで、２進乱数列ｂ０ｂ１…ｂｍ−１を更新する動作と、更新された２進乱数列ｂ０ｂ１…ｂｍ−１を整数に変換する動作とを繰り返し行う。
【００５１】
図２は、ランダム２進乱数列を複数の整数乱数からなる整数乱数列に変換する複合部分廃棄手法（ＣＰＤＭ）によって整数乱数列を出力する、本発明の他の実施形態にかかる２進乱数列を整数乱数列に変換する装置の構成を説明するためのブロック図である。
【００５２】
図２を参照すれば、本発明の複合部分廃棄手法によって２進乱数列を整数乱数列に変換する装置２００は、２進乱数列生成部２２０と、整数変換部２４０と、整数乱数列出力部２６０とを含む。
【００５３】
２進乱数列生成部２２０は、ランダムな２進乱数列を生成し、生成された初期２進乱数列を整数変換部２４０に伝達する。ここで、整数乱数列出力部２６０が整数区間［０，ｒ−１］内に含まれるｎ個の整数乱数からなる整数乱数列を出力するようにするために、２進乱数列生成部２２０は、ｒｎ−１を２進数で表現するのに必要な最小限のビット数ｋをビット数として有するランダムな２進乱数列ｂ０ｂ１…ｂｋ−１を生成し、ランダムな２進乱数列ｂ０ｂ１…ｂｋ−１を整数変換部２４０に伝達する。２進乱数列生成部２２０によって生成される２進ビット列ｂ０ｂ１…ｂｋ−１のビット数ｋは、下記の数９によって生成できる。
【数９】
0005636489.tif 000010
【００５４】
一方、［０，ｒｎ−１］の範囲に設定される整数区間において、ｒｎ−１は、下記の数１０のように表される。
【数１０】
0005636489.tif 000011
【００５５】
また、２進乱数列生成部２２０は、整数乱数列出力部２６０の要請に応じて、ランダムな追加２進乱数列としてｄ＋１のビット数を有する２進乱数列ｂｋｂｋ＋１…ｂｋ＋ｄを生成し、２進乱数列ｂ０ｂ１…ｂｋ−１のビットと追加的に生成した２進乱数列ｂｋｂｋ＋１…ｂｋ＋ｄのビットに基づいて２進乱数列ｂｄ＋１ｂｄ＋２…ｂｋ＋ｄを算出し、算出されたｂｄ＋１ｂｄ＋２…ｂｋ＋ｄに２進乱数列ｂ０ｂ１…ｂｋ−１を更新する。より具体的には、２進乱数列生成部２２０は、整数乱数列出力部２６０からｄ＋１のビット数を有するランダムな追加２進乱数列を生成させる要請がある場合、ｄ＋１のビット数を有する追加２進乱数列ｂｋｂｋ＋１…ｂｋ＋ｄを生成し、追加２進乱数列ｂｋｂｋ＋１…ｂｋ＋ｄと既存の２進乱数列ｂ０ｂ１…ｂｋ−１とを組み合わせて算出したｂｄ＋１ｂｄ＋２…ｂｋ＋ｄに既存の２進乱数列ｂ０ｂ１…ｂｋ−１を更新する。これによって、２進乱数列生成部２２０から整数変換部２４０に伝達される２進乱数列は、順次に各ビット値がｂｄ＋１ｂｄ＋２…ｂｋ＋ｄの各ビット値に切り替えられた２進乱数列ｂ０ｂ１…ｂｋ−１に相当する。
【００５６】
整数変換部２４０は、２進乱数列生成部２２０から受信した２進乱数列を整数に変換し、変換された整数を整数乱数列出力部２６０に伝達する。この時、整数変換部２４０は、２進乱数列生成部２２０からｋのビット数を有する２進乱数列ｂ０ｂ１…ｂｋ−１を受信し、下記の数１１に基づいて受信された２進乱数列ｂ０ｂ１…ｂｋ−１を整数ａに変換する。
【数１１】
0005636489.tif 000012
【００５７】
ここで、ａは、２進乱数列ｂ０ｂ１…ｂｋ−１から変換される整数であり、ｂｉは、前記２進乱数列ｂ０ｂ１…ｂｋ−１におけるｉ番目ビット値を意味する。
【００５８】
整数変換部２４０が２進乱数列生成部２２０から受信する２進乱数列ｂ０ｂ１…ｂｋ−１は、２進乱数列生成部２２０によって初期に生成されたり、追加２進乱数列ｂｋｂｋ＋１…ｂｋ＋ｄに基づいて更新された２進乱数列ｂ０ｂ１…ｂｋ−１に相当する。
【００５９】
整数乱数列出力部２６０は、２進乱数列から変換された整数を整数変換部２４０から受信し、２進乱数列から変換された整数が予め設定された整数区間に相応するか否かを判断して、前記変換された整数が予め設定された整数区間に相応する場合には、当該整数に基づいて算出した整数からなる整数列を整数乱数列として出力する。より具体的には、整数乱数列出力部２６０は、２進乱数列生成部２２０によって生成または更新された２進乱数列ｂ０ｂ１…ｂｋ−１から変換された整数ａを整数変換部２４０から受信し、受信された整数ａが整数区間［０，ｒｎ−１］内に含まれるか否かを確認する。仮に、受信された整数ａが整数区間［０，ｒｎ−１］内に含まれる場合（０≦ａ≦ｒｎ−１の場合）には、整数乱数列出力部２６０は、整数ａに対して、下記の数１２に基づいてｎ個の整数ａ０，…，ａｎ−１を算出する。
【数１２】
0005636489.tif 000013
【００６０】
そして、整数乱数列出力部２６０は、整数ａから算出したｎ個の整数ａ０，…，ａｎ−１からなる整数列ａ０ａ１…ａｎ−１を整数乱数列として出力する。この時、整数乱数列出力部２６０は、整数乱数列ａ０ａ１…ａｎ−１の各整数にαを加えて出力することができる。
【００６１】
反面、受信された整数ａが整数区間［０，ｒｎ−１］内に含まれない場合（ａ＞ｒｎ−１の場合）には、整数乱数列出力部２６０は、ｂｉ＞ｒｉとなるｉの最小値に相当するｄを算出する。この時、整数乱数列出力部２６０は、下記の数１３を満足するｄを算出する。
【数１３】
0005636489.tif 000014
【００６２】
ここで、ＡとＲ’はそれぞれ、整数ａとｒｎ−１を同じビット数を有する２進数で表現した値を意味する。
【００６３】
整数乱数列出力部２６０は、受信された整数ａが整数区間［０，ｒｎ−１］内に含まれずにｄを算出した場合、２進乱数列生成部２２０にｄ＋１のビット数を有するランダムな追加２進乱数列ｂｋｂｋ＋１…ｂｋ＋ｄを生成し、２進乱数列ｂ０ｂ１…ｂｋ−１を更新するように要請する。
【００６４】
本発明の複合部分廃棄手法によって２進乱数列を整数乱数列に変換する装置２００は、整数変換部２４０から出力される整数ａが整数区間［０，ｒｎ−１］内に含まれるまで、２進乱数列ｂ０ｂ１…ｂｋ−１を更新する動作と、更新された２進乱数列ｂ０ｂ１…ｂｋ−１を整数に変換する動作とを繰り返し行う。
【００６５】
以下では、図３ないし図５を参照して、本発明にかかる２進乱数列を整数乱数に変換する方法について説明する。これに先立ち、図１を参照して説明した単純部分廃棄手法（ＳＰＤＭ）による２進乱数列を整数乱数に変換する装置、および図２を参照して説明した複合部分廃棄手法（ＣＰＤＭ）による２進乱数列を整数乱数列に変換する装置の動作と一部重複する部分は省略して説明する。
【００６６】
図３は、本発明にかかる２進乱数列を整数乱数に変換する方法を説明するためのフローチャートである。
【００６７】
図３を参照すれば、本発明にかかる２進乱数列を整数乱数に変換する方法は、まず、２進乱数列生成部１２０、２２０がランダムな２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１を生成する（Ｓ３００）。乱数列生成部１２０、２２０は、生成された２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１を整数変換部１４０、２４０に伝達する。
【００６８】
そして、整数変換部１４０、２４０が２進乱数列生成部１２０、２２０によって生成された初期２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１を整数ｔ、ａに変換する（Ｓ３１０）。整数変換部１４０、２４０は、初期２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１から変換された整数ｔ、ａを整数乱数出力部１６０または整数乱数列出力部２６０に出力する。
【００６９】
次に、整数乱数出力部１６０または整数乱数列出力部２６０は、初期２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１から変換された整数ｔ、ａが予め設定された整数区間［０，ｒ−１］、［０，ｒｎ−１］に属するか否かを判断する（Ｓ３２０）。
【００７０】
前記Ｓ３２０ステップでの判断結果、初期２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１から変換された整数ｔ、ａが予め設定された整数区間［０，ｒ−１］、［０，ｒｎ−１］に属する場合には、整数乱数出力部１６０は、初期２進乱数列ｂ０ｂ１…ｂｍ−１から変換された整数ｔを整数乱数として出力し、整数乱数列出力部２６０は、初期２進乱数列ｂ０ｂ１…ｂｋ−１から変換された整数ａに対して、数１２に基づいて算出したｎ個の整数ａ０，…，ａｎ−１からなる整数列ａ０ａ１…ａｎ−１を整数乱数列として出力する（Ｓ３３０）。
【００７１】
反面、前記Ｓ３２０ステップでの判断結果、初期２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１から変換された整数ｔ、ａが予め設定された整数区間［０，ｒ−１］、［０，ｒｎ−１］に属しない場合には、整数乱数出力部１６０または整数乱数列出力部２６０の要請に応じて、２進乱数列生成部１２０、２２０がランダムな追加２進乱数列ｂｍｂｍ＋１…ｂｍ＋ｄ、ｂｋｂｋ＋１…ｂｋ＋ｄを生成し、２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１を更新する（Ｓ３４０）。前記Ｓ３４０ステップでは、２進乱数列生成部１２０、２２０が既存の２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１と追加２進乱数列ｂｍｂｍ＋１…ｂｍ＋ｄ、ｂｋｂｋ＋１…ｂｋ＋ｄとを組み合わせて算出した２進乱数列ｂｄ＋１ｂｄ＋２…ｂｍ＋ｄ、ｂｄ＋１ｂｄ＋２…ｂｋ＋ｄに２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１を更新する。そして、２進乱数列生成部１２０、２２０は、更新された２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１を整数変換部１４０、２４０に出力し、整数変換部１４０、２４０が更新された２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１を整数ｔ、ａに変換するＳ３１０ステップが再実行される。
【００７２】
本発明にかかる２進乱数列を整数乱数に変換する方法は、Ｓ３２０ステップで２進乱数列ｂ０ｂ１…ｂｍ−１、ｂ０ｂ１…ｂｋ−１から変換された整数ｔ、ａが予め設定された整数区間［０，ｒ−１］、［０，ｒｎ−１］に属すると判断されるまで、Ｓ３１０ステップ、Ｓ３２０ステップおよびＳ３４０ステップが繰り返し行われる。
【００７３】
図４は、本発明にかかる２進乱数列を整数乱数に変換する方法において、ランダム２進乱数列を１つの整数乱数に変換する単純部分廃棄手法（ＳＰＤＭ）によって整数乱数を出力する方法をより具体的に説明するためのフローチャートである。
【００７４】
図４を参照すれば、本発明の単純部分廃棄手法によって２進乱数列を整数乱数に変換する方法は、まず、乱数列生成部１２０が整数区間［０，ｒ−１］に対して、ｒ−１を２進数で表現可能な最小のビット数ｍをビット数として有するランダムな２進乱数列ｂ０ｂ１…ｂｍ−１を生成する（Ｓ４００）。そして、２進乱数列生成部１２０は、生成された２進乱数列ｂ０ｂ１…ｂｍ−１を整数変換部１４０に出力する。
【００７５】
次に、整数変換部１４０は、２進乱数列生成部１２０から受信した２進乱数列ｂ０ｂ１…ｂｍ−１を、数６に基づいて整数ｔに変換する（Ｓ４１０）。そして、整数変換部１４０は、２進乱数列ｂ０ｂ１…ｂｍ−１から変換された整数ｔを整数乱数出力部１６０に出力する。
【００７６】
次に、整数乱数出力部１６０は、整数変換部１４０から受信した整数ｔが整数区間［０，ｒ−１］に含まれるか否かを判断する（Ｓ４２０）。
【００７７】
前記Ｓ４２０ステップでの判断結果、整数変換部１４０から受信した整数ｔが整数区間［０，ｒ−１］に含まれる場合（０≦ｔ≦ｒ−１の場合）には、整数ｔを整数乱数として出力する（Ｓ４３０）。
【００７８】
反面、前記Ｓ４２０ステップでの判断結果、整数変換部１４０から受信した整数ｔが整数区間［０，ｒ−１］に含まれない場合（ｔ＞ｒ−１の場合）には、ｂｉ＞ｒｉとなるｉの最小値に相当するｄを算出する（Ｓ４４０）。この時、整数乱数出力部１６０は、数７を満足するｄを算出する。
【００７９】
次に、整数乱数出力部１６０は、２進乱数列生成部１２０に２進乱数列ｂ０ｂ１…ｂｍ−１を更新するように要請し、２進乱数列生成部１２０は、整数乱数出力部１６０からの更新要請に応じて、ｄ＋１のビット数を有するランダムな追加２進乱数列ｂｍｂｍ＋１…ｂｍ＋ｄを生成する（Ｓ４５０）。
【００８０】
そして、２進乱数列生成部１２０は、２進乱数列ｂ０ｂ１…ｂｍ−１と追加２進乱数列ｂｍｂｍ＋１…ｂｍ＋ｄに基づいて算出した２進乱数列ｂｄ＋１ｂｄ＋２…ｂｍ＋ｄに２進乱数列ｂ０ｂ１…ｂｍ−１を更新する（Ｓ４６０）。この時、２進乱数列生成部１２０は、更新された２進乱数列ｂ０ｂ１…ｂｍ−１を整数変換部１４０に出力し、整数変換部１４０は、更新された２進乱数列ｂ０ｂ１…ｂｍ−１を整数ｔに変換する動作を再実行する（Ｓ４１０）。
【００８１】
一方、更新された２進乱数列ｂ０ｂ１…ｂｍ−１から変換された整数ｔが前記Ｓ４２０ステップで整数区間［０，ｒ−１］に含まれると判断されるまで、Ｓ４１０ステップ、Ｓ４２０ステップおよびＳ４４０ステップないしＳ４６０ステップが繰り返し行われる。
【００８２】
図５は、本発明にかかる２進乱数列を整数乱数に変換する方法において、ランダム２進乱数列を複数の整数乱数からなる整数乱数列に変換する複合部分廃棄手法（ＣＰＤＭ）によって整数乱数列を出力する方法をより具体的に説明するためのフローチャートである。
【００８３】
図５を参照すれば、本発明の複合部分廃棄手法によって２進乱数列を整数乱数列に変換する方法は、まず、乱数列生成部２２０が整数区間［０，ｒｎ−１］に対して、ｒｎ−１を２進数で表現可能な最小のビット数ｋをビット数として有するランダムな２進乱数列ｂ０ｂ１…ｂｋ−１を生成する（Ｓ５００）。そして、２進乱数列生成部２２０は、生成された２進乱数列ｂ０ｂ１…ｂｋ−１を整数変換部２４０に出力する。
【００８４】
次に、整数変換部２４０は、２進乱数列生成部２２０から受信した２進乱数列ｂ０ｂ１…ｂｋ−１を、数１１に基づいて整数ａに変換する（Ｓ５１０）。そして、整数変換部２４０は、２進乱数列ｂ０ｂ１…ｂｋ−１から変換された整数ａを整数乱数列出力部２６０に出力する。
【００８５】
次に、整数乱数列出力部２６０は、整数変換部２４０から受信した整数ａが整数区間［０，ｒｎ−１］に含まれるか否かを判断する（Ｓ５２０）。
【００８６】
前記Ｓ５２０ステップでの判断結果、整数変換部２４０から受信した整数ａが整数区間［０，ｒｎ−１］に含まれる場合（０≦ａ≦ｒｎ−１の場合）には、整数乱数列出力部２６０は、数１２に基づいて整数ａからｎ個の整数乱数ａ０，…，ａｎ−１を算出する（Ｓ５３０）。そして、整数乱数列出力部２６０は、ｎ個の整数ａ０，…，ａｎ−１を順次に結合した整数列ａ０ａ１…ａｎ−１を整数乱数列として出力する（Ｓ５４０）。
【００８７】
反面、前記Ｓ４２０ステップでの判断結果、整数変換部２４０から受信した整数ａが整数区間［０，ｒｎ−１］に含まれない場合（ａ＞ｒｎ−１の場合）には、ｂｉ＞ｒｉとなるｉの最小値に相当するｄを算出する（Ｓ５５０）。この時、整数乱数列出力部２６０は、数１３を満足するｄを算出する。
【００８８】
次に、整数乱数列出力部２６０は、２進乱数列生成部２２０に２進乱数列ｂ０ｂ１…ｂｋ−１を更新するように要請し、２進乱数列生成部２２０は、整数乱数列出力部２６０からの更新要請に応じて、ｄ＋１のビット数を有するランダムな追加２進乱数列ｂｋｂｋ＋１…ｂｋ＋ｄを生成する（Ｓ５６０）。
【００８９】
そして、２進乱数列生成部２２０は、２進乱数列ｂ０ｂ１…ｂｋ−１と追加２進乱数列ｂｋｂｋ＋１…ｂｋ＋ｄに基づいて算出した２進乱数列ｂｄ＋１ｂｄ＋２…ｂｋ＋ｄに２進乱数列ｂ０ｂ１…ｂｋ−１を更新する（Ｓ５７０）。この時、２進乱数列生成部２２０は、更新された２進乱数列ｂ０ｂ１…ｂｋ−１を整数変換部２４０に出力し、整数変換部２４０は、更新された２進乱数列ｂ０ｂ１…ｂｋ−１を整数ａに変換する動作を再実行する（Ｓ５１０）。
【００９０】
一方、更新された２進乱数列ｂ０ｂ１…ｂｋ−１から変換された整数ａが前記Ｓ５２０ステップで整数区間［０，ｒｎ−１］に含まれると判断されるまで、Ｓ５１０ステップ、Ｓ５２０ステップおよびＳ５５０ステップないしＳ５７０ステップが繰り返し行われる。
【００９１】
本発明の単純部分廃棄手法（ＳＰＤＭ）または複合部分廃棄手法（ＣＰＤＭ）によって２進乱数列を整数乱数に変換する方法が行われる各ステップは、コンピュータ読み取り可能な記録媒体にコンピュータ読み取り可能なコードとして実現することが可能である。コンピュータ読み取り可能な記録媒体は、コンピュータシステムによって読み取り可能なデータが格納されるすべての種類の記録装置を含む。コンピュータ読み取り可能な記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、ＣＤ−ＲＷ、磁気テープ、フロッピー（登録商標）ディスク、ＨＤＤ、光ディスク、光磁気記憶装置などがあり得、また、キャリアウェーブ（例えば、インターネットを介した伝送）の形態で実現されるものも含む。また、コンピュータ読み取り可能な記録媒体は、ネットワークで接続されたコンピュータシステムに分散して、分散方式でコンピュータ読み取り可能なコードとして格納されて実行可能である。
【００９２】
以上、図面と明細書で最適な実施形態が開示された。ここで、特定の用語が使われたが、これは単に本発明を説明するための目的で使われたもので、意味の限定や特許請求の範囲に記載された本発明の範囲を制限するために使われたものではない。そのため、本技術分野における通常の知識を有する者であれば、これから多様な変形および均等な他の実施形態が可能である点を理解することができる。したがって、本発明の真の技術的保護範囲は、添付した特許請求の範囲の技術的思想によって定められなければならない。
【符号の説明】
【００９３】
１２０、２２０：２進乱数列生成部
１４０、２４０：整数変換部
１６０：整数乱数出力部
２６０：整数乱数列出力部
【図１】
0005636489.tif 000017
【図２】
0005636489.tif 000018
【図３】
0005636489.tif 000019
【図４】
0005636489.tif 000020
【図５】
0005636489.tif 000021