整数系列の周期判定方法、周期判定装置及び周期判定プログラム
【課題】任意の大きさの自然数の集合による全単射関数を用いて作成した整数系列の周期を判定する。
【解決手段】順列作成部4は、全単射関数(写像)の入力に対する出力データ(原像に対する像)の並びである順列A(i)を作成する。順列記憶部5は、任意の大きさm(mは2以上の自然数)の全ての全単射関数の入力に対する出力の状態を示す順列S(i,j)を記憶する。周期計算部6は、任意の全単射関数の入力に対する出力データ系列を更に入力とする手順を繰り返し行って、作成する整数系列の周期を計算する。周期記憶部10は、順列数設定部11が指定した周期計算部6の周期計算結果を記憶する。順列数設定部11は、任意のデータ数mの全ての全単射関数の存在数を記憶する。
【解決手段】順列作成部4は、全単射関数(写像)の入力に対する出力データ(原像に対する像)の並びである順列A(i)を作成する。順列記憶部5は、任意の大きさm(mは2以上の自然数)の全ての全単射関数の入力に対する出力の状態を示す順列S(i,j)を記憶する。周期計算部6は、任意の全単射関数の入力に対する出力データ系列を更に入力とする手順を繰り返し行って、作成する整数系列の周期を計算する。周期記憶部10は、順列数設定部11が指定した周期計算部6の周期計算結果を記憶する。順列数設定部11は、任意のデータ数mの全ての全単射関数の存在数を記憶する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は整数系列の周期判定方法、周期判定装置及び周期判定プログラムに係り、特に擬似乱数等に用いられる整数系列の周期判定方法、周期判定装置及び周期判定プログラムに関する。
【背景技術】
【0002】
近年、暗号やモンテカルロ法等に用いられる擬似乱数系列は、暗号解析の困難性を高めるために、周期の長い系列が要求される。また、これまで系列長が保証された擬似乱数系列として、M系列等が使用されることが多かったが、それ以外の手段として、カオスや帰還関数等を用いた生成方法を利用することが考えられる(例えば、非特許文献1、非特許文献2参照)。非特許文献1には、シフトレジスタを用いて周期の長い擬似乱数系列を発生することが開示されている。また、非特許文献2には擬似乱数系列を発生させる暗号理論一般について開示されている。
【0003】
また、暗号解析の困難性を高め、安全性の高い擬似乱数系列を生成するために、複数の異なるSボックスを利用した処理を行う構成の暗号処理装置(例えば、特許文献1参照)や、線形フィードバックシフトレジスタを利用したM系列の出力に非線形関数をフィルタとして用いることで、出力擬似乱数系列を推定困難にする構成の擬似乱数系列生成装置が知られている(例えば、特許文献2参照)。
【0004】
更に、擬似乱数系列の利用可能性に基づいて、システム内の乱数生成器の系列反復周期を拡張するために、複数の互いに素となる数を法としてRNS(Residue Number System)剰余値を求め、それを組み合わせて出力系列とすることで系列長を拡張する方法も知られている(例えば、特許文献3参照)。
【先行技術文献】
【非特許文献】
【0005】
【非特許文献1】Solomon Wolf Golomb,“Shift Register Sequences”,San Francisco,Holden-Day,1967.
【非特許文献2】Bruce Schneier,“Applied Cryptography”,Second Edition,John Wiley & Sons,Inc.1996.
【特許文献】
【0006】
【特許文献1】特開2008−58828号公報
【特許文献2】特開平8−202535号公報
【特許文献3】特開2009−3925号公報
【発明の概要】
【発明が解決しようとする課題】
【0007】
しかしながら、カオスや帰還関数等を用いた生成方法を利用して擬似乱数系列を生成する場合は、生成した擬似乱数系列長が明らかでない場合があり、また生成された擬似乱数系列が短周期等の理由より使用目的によっては適さない擬似乱数系列を使用せざるを得ない場合もある。
【0008】
また、特許文献1及び2各記載の装置では、生成した擬似乱数系列の周期を判定して、その周期の長さや周期の個数を求める機能は有しておらず、周期に使用した値を使用済みとして区別する機能を有していない。更に、特許文献3記載の方法も、擬似乱数系列の周期を判定して、その周期の長さや個数を求める機能や、剰余を利用することなく完全擬似乱数を求めることについては全く開示されていない。
【0009】
このように、従来は擬似乱数系列の周期を判定することは知られておらず、このことから系列長の保証された完全擬似乱数を得ることは容易でなかった。
【0010】
本発明は以上の点に鑑みなされたもので、擬似乱数系列の生成のために、任意の大きさの自然数の集合による全単射関数を用いて生成された整数系列の周期を判定し得る整数系列の周期判定方法、周期判定装置及び周期判定プログラムを提供することを目的とする。
【0011】
また、本発明の他の目的は、自然数を入出力とする全単射関数及び変換表もしくはSボックス等の出力フィードバックにおいて、周期長の合計を求める演算を行い、各周期長が幾つ存在するかの結果や、最大長の周期を保有するかどうかの判定が可能である整数系列の周期判定方法、周期判定装置及び周期判定プログラムを提供することにある。
【課題を解決するための手段】
【0012】
上記の目的を達成するため、第1の発明の整数系列の周期判定方法は、制御部が、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!(m!はmの階乗。即ち1×2×・・・×(m−1)×mを表す。)個の全単射関数(写像)についての前記m種類の入力に対する出力の状態を全て順列として生成して第1の記憶部に記憶する第1のステップと、制御部が、第1の記憶部に記憶されたm!個の全単射関数についての順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、周期がmより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての入力値及び全ての未出現の入力値に対して順次行う第2のステップと、制御部が、第2のステップで求められたm!個の全単射関数の最小周期から最大周期までの周期を第2の記憶部に記憶する第3のステップとを含むことを特徴とする。
【0013】
また、上記の目的を達成するため、第2の発明の整数系列の周期判定方法は、制御部が、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数(写像)のうち、所望の1個の前記全単射関数の前記m個の整数からなる整数系列の入力に対する出力の状態を順列として第1の記憶部に記憶する第1のステップと、制御部が、前記m個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第2の記憶部に記憶することを、前記m個の入力のすべてについて行う第2のステップと、制御部が、前記第2の記憶部に記憶された周期が前記mであるか否かを判定し、前記周期が前記mであるとき、その周期を前記所望の1個の前記全単射関数の最大周期であると決定する第3のステップとを含むことを特徴とする。
【0014】
また、上記の目的を達成するため、第3の発明の整数系列の周期判定装置は、第1及び第2の記憶部と、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数(写像)についての前記m種類の入力に対する出力の状態を全て順列として生成して前記第1の記憶部に記憶する順列生成及び記憶手段と、第1の記憶部に記憶されたm!個の全単射関数についての順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、周期がmより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての入力値及び全ての未出現の入力値に対して順次行う周期計算及び累計手段と、前記周期計算及び累計手段で得られた前記m!個の全単射関数の最小周期から最大周期までの周期を第2の記憶部に記憶する記憶手段とを有することを特徴とする。
【0015】
また、上記の目的を達成するため、第4の発明の整数系列の周期判定装置は、第1及び第2の記憶部と、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数(写像)のうち、所望の1個の前記全単射関数の前記m個の整数からなる整数系列の入力に対する出力の状態を順列として第1の記憶部に記憶する順列記憶手段と、m個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第2の記憶部に記憶することを、前記m個の入力のすべてについて行う周期計算及び累計手段と、第2の記憶部に記憶された周期が前記mであるか否かを判定し、前記周期が前記mであるとき、その周期を前記所望の1個の前記全単射関数の最大周期であると決定する最大周期判定手段とを有することを特徴とする。
【0016】
また、上記の目的を達成するため、第5の発明の整数系列の周期判定プログラムは、コンピュータに、第1の発明の整数系列の周期判定方法の第1乃至第3のステップを実行させることを特徴とする。
【0017】
更に、上記の目的を達成するため、第6の発明の整数系列の周期判定プログラムは、コンピュータに、第2の発明の整数系列の周期判定方法の第1乃至第3のステップを実行させることを特徴とする。
【発明の効果】
【0018】
本発明によれば、任意の大きさの自然数の集合を入力(原像)と出力(像)とした全単射関数(写像)を用いて出力を入力に帰還することで生成された整数系列の帰還周期の判定が行え、また、その整数系列の最大周期を判定することができる。
【図面の簡単な説明】
【0019】
【図1】本発明の整数系列の周期判定装置の第1の実施形態のブロック図である。
【図2】全単射関数の一例の説明図である。
【図3】本発明による擬似乱数作成の概要の説明図である。
【図4】本発明の第1の実施形態の概要説明用フローチャートである。
【図5】本発明の第1の実施形態の全単射関数の入出力データの順列作成の概要説明用フローチャートである。
【図6】本発明の第1の実施形態の作成した各々の順列データから各周期を判定する概要説明用フローチャートである。
【図7】本発明の第1の実施形態の動作を説明するフローチャート(その1)である。
【図8】本発明の第1の実施形態の動作を説明するフローチャート(その2)である。
【図9】図7中のステップS1の詳細動作を説明するフローチャートである。
【図10】本発明による周期の判定動作のための関数帰還を説明する図である。
【図11】本発明の整数系列の周期判定装置の第2、第3の実施形態のブロック図である。
【図12】本発明の第2の実施形態の動作を説明するフローチャート(その1)である。
【図13】本発明の第2の実施形態の動作を説明するフローチャート(その2)である。
【図14】本発明の第3の実施形態の動作を説明するフローチャートである。
【発明を実施するための形態】
【0020】
次に、本発明の各実施形態について、図面と共に詳細に説明する。
【0021】
(第1の実施形態)
図1は、本発明になる整数系列の周期判定装置の第1の実施形態のブロック図を示す。同図に示すように、本実施形態の整数系列の周期判定装置1Aは、装置1A全体を統括的に制御する制御部2A、データ数記憶部3、順列作成部4、順列記憶部5、周期計算部6、入力指定部7、出力記憶部8、周期累計部9、周期記憶部10、順列数設定部11、検索位置指定部12から構成されている。
【0022】
制御部2A、順列作成部4、周期計算部6、順列数設定部11及び検索位置指定部12は、例えば中央処理装置(CPU)により構成される。また、データ数記憶部3、出力記憶部8、周期累計部9及び周期記憶部10は記憶装置により構成され、入力指定部7は所定の入力装置により構成される。
【0023】
データ数記憶部3は、単射で、かつ、全射でもある関数である全単射関数の有する連続した自然数の入出力データ(原像及び像)の数Mを記憶する。順列作成部4は、全単射関数の入力に対する出力データ(原像に対する像)の並びである順列A(i)を作成する。この場合、順列A(i)は、出力データの値は重複せず、全ての値が出現するように作成される。
【0024】
順列記憶部5は、後述するようにして作成された任意の大きさ(データ数M)m(mは2以上の自然数)の全ての全単射関数(写像)の入力に対する出力(原像に対する像)の状態を示す順列S(i,j)を記憶する第1の記憶部である。周期計算部6は、後述するように任意の全単射関数の入力に対する出力データ(原像に対する像)を更に入力とする手順を繰り返し行って、作成する整数系列の周期Pを計算する。
【0025】
入力指定部7は、入力位置(原像の位置)INPを指定する。出力記憶部8は、入力指定部7で指定された入力位置の周期計算部6の出力データ(像)の値OUTPを記憶する。周期累計部9は、周期計算部6で計算した周期Pの累計結果PSを記憶する。
【0026】
周期記憶部10は、順列数設定部11が指定した周期計算部6の周期計算結果PR(PM,M)を記憶する第2の記憶部である。本実施形態では、周期記憶部10は、任意の大きさ(データ数M)mの全ての全単射関数の各々の周期について存在数を記憶する。順列数設定部11は、任意のデータ数mの全ての全単射関数の存在数PMを記憶する。検索位置指定部12は、順列作成部4において作成される任意の順列の値A(i)の既に作成された、それまでの順列の検索位置POSを指定する。
【0027】
上記の構成のうち、制御部2A、データ数記憶部3、順列作成部4、入力指定部7、順列数設定部11、及び検索位置指定部12は、m!個の全単射関数についてのm種類の入出力に対する出力の状態をすべて順列として生成して第1の記憶部である順列記憶部5に記憶する順列生成及び記憶手段を構成する。また、制御部2A、データ数記憶部3、周期計算部6、入力指定部7、出力記憶部8、周期累計部9、及び順列数設定部11は、周期計算及び累計手段と、第2の記憶部である周期記憶部10に判定した周期を記憶する記憶手段とを構成する。
【0028】
ところで、図2に示すように、m個の自然数x(例えば、データの集合X={x|x=natural number,0≦x≦(m-1)})を入力(原像)と出力(像)とする、全ての全単射関数(写像)fの数は、m!存在することが知られている。本発明は、入力データと出力データとが一対一で対応する全単射関数を用いた変換による擬似乱数系列の生成において、図3に示すように、m個の自然数をその関数による変換の写像の原像である入力データ(0〜mー1)と、像となる出力データ(0〜mー1)とし、出力データを更に入力データとして帰還するような帰還系列(擬似乱数系列)について、すべての周期を判定するものである。
【0029】
本発明では、m!個の全単射関数についてのm種類の入力に対する出力の状態を、全て順列として列記することで得る。これは、0〜(m−1)を最初の全単射関数の出力の順列とし、それ以降の全単射関数の出力の並びは、1つ前の順列において、その最後の出力の位置からバックトラックとインクリメンタルサーチの手法を用いて行うことで、次の順列を求めることができる。
【0030】
次に、本発明では、上記の方法で求めた順列(関数)について、最初の入力値(例えば0)から、その入力と同じ出力値(例えば0)となるまで変換を行い、その変換回数を周期として求める。更に、ここで出力値として出現しないものの入力値についても順に同様な変換を行い、その最初の入力値に戻るまでの変換回数を周期として求める。すべての入力値が出現した場合には、全ての周期とその周期の出現回数が求まる。また、任意の一つの全単射関数について上記と同様の手順により全ての周期とその出現回数を求めることが可能である。
【0031】
本発明における上記の全単射関数は、m個の自然数による任意の並びの単なる順列の表、ラテン方陣のような変換表(換字表)、Sボックス、ブロック暗号、帰還型ストリーム暗号に相当し、本発明で周期が判定される整数系列は、ブロック暗号のOFB(Output Feed Back)モードや帰還型ストリーム暗号の出力系列に相当する。
【0032】
ここで、大きさ2(m=2)の全ての全単射関数の入出力データの関係は、下記に示される。
【0033】
f1=[0 1]:0→0,1→1
f2=[1 0]:0→1→0
上記の→の左側の値は入力値、右側の値は出力値を示す(後述する他の例も同様)。従って、1番目の入出力データの関係f1では、0が入力されると0が出力される場合と、1が入力されると1が出力される場合を示しており、周期1が2個である。また、2番目の入出力データの関係f2では、0が入力されると1が出力され、1が入力されると0が出力される場合を示しており、周期2が1個であることを示す。従って、m=2の整数系列の全ての全単射関数は、周期1が2個と周期2(最大周期)が1個を有すると結論することができる。この例は次のような表で表すこともできる。
【0034】
【表1】
同様に、大きさ3(m=3)の全ての全単射関数の入出力データの関係は、下記に示される。
【0035】
f1=[0 1 2]:0→0,1→1,2→2(ゆえに、周期1が3個)
f2=[0 2 1]:0→0,1→2→1(ゆえに、周期1が1個と周期2が1個)
f3=[1 0 2]:0→1→0,2→2(ゆえに周期1が1個と周期2が1個)
f4=[1 2 0]:0→1→2→0(ゆえに周期3が1個)
f5=[2 0 1]:0→2→1→0(ゆえに周期3が1個)
f6=[2 1 0]:0→2→0,1→1(ゆえに周期1が1個と周期2が1個)
よって、m=3の場合では、全ての全単射関数は、周期1が6個と周期2が3個と周期3(最大周期)が2個を有すると結論できる。この例は次のような表で表すこともできる。
【0036】
【表2】
同様に、m個の自然数(整数)からなる整数系列の全ての全単射関数の入出力データの関係は、下記の表3で表すことができる。
【0037】
【表3】
図1に示す第1の実施形態の整数系列の周期判定装置1Aは、入出力データの大きさが任意のmの場合の全ての全単射関数の全ての整数系列の作成とその系列の全周期を判定する装置の例である。まず、本実施形態の動作の概要について説明する。
【0038】
図4は、本実施形態の概要のフローチャートを示す。同図に示すように、整数系列の周期判定装置1Aは、まず1つの全単射関数の出力の順列データを作成する(ステップS151)。続いて、整数系列の周期判定装置1Aは、ステップS151で作成した順列データから、全単射関数の出力から入力への帰還を繰り返すことによる帰還系列の周期について部分周期最大周期の全ての周期(長)を判定する(ステップS152)。
【0039】
図5は、図4のステップS151の順列データ作成動作の詳細を示す。図5に示すように、順列データ作成処理では、最初の関数の順列データを作成し(ステップS201)、続いて、二番目の関数の順列データを最初のデータから作成する(ステップS202)。以下、同様にして、m!番目の関数の順列データをm!−1番目の順列データから作成する(ステップS203)。
【0040】
図6は、図4のステップS152の作成した順列データから周期を判定する動作の詳細を示す。図6に示すように、周期判定処理では、最初の関数の順列データの各周期を累計し、周期記憶部10に加算する(ステップS301)。続いて、二番目の関数の順列データの各周期を累計し、周期記憶部10に加算する(ステップS302)。以下、同様にして、m!番目の関数の順列データの各周期を累計し周期記憶部10に加算する(ステップS303)。
【0041】
次に、本実施形態の整数系列の周期判定装置1Aによる動作について、更に詳細に説明する。図7及び図8は、図4で説明した本実施形態の概要動作を更に詳細に説明するフローチャートを示す。図9は、図7中のステップS1で作成する順列(整数系列データ)の作成方法の詳細動作説明用フローチャートを示す。図7のステップS1は、図5のフローチャートで概要動作を説明した処理ステップであり、図7のステップS2以降と図8の各ステップは、図6のフローチャートで概要動作を説明した処理の詳細動作を説明するものである。
【0042】
まず、図1の制御部2Aは、順列作成部4にて作成したm!(ここでは、m=2)個の順列A(0)〜A(m-1)を順列記憶部5に設定する(図7のステップS1)。このステップS1による順列の作成は、出力データの最初の位置として順列作成部4のA(0)から最後の位置A(m-1)に未設定の昇順の自然数(0〜m-1)を重複が発生しないように順に設定してゆく図9のバックトラック技法とインクリメンタルサーチ技法により作成可能である。
【0043】
周期を判定すべき関数の出力データの順列が完成したら、順列作成部4の順列A(0)〜A(m-1)のデータをm!番目の順列記憶部5の順列S(m!,0)〜S(m!,m-1)に設定する。更に、m!個のうちの残りのm!-1個の全ての系列S(m!-1,0)〜S(m!-1,m-1)、・・・、S(1,0)〜S(1,m-1)についても、一つ前の系列データS(m!,0)〜S(m!,m-1)のセットを用いて、その最後の位置m-1のデータからバックトラックすることで新たな次のm!-1番目の系列S(m!-1,0)〜S(m!-1,m-1)を求めることが可能であり、これを順次行うことでm個の系列のデータを各々有する全てのm!組の関数の系列データS(m!,0)〜S(m!,m-1)、・・・、S(1,0)〜S(1,m-1)を作成することが可能である。
【0044】
なお、この順列記憶部5に設定した判定用の順列は事前にm!-1個全てを作成し準備しておくものとしているが、他の方法として一つの周期判定の前に各々順に同様の手法で作成することにより系列データの記憶場所である順列記憶部5に1つだけ事前に設定することで使用する記憶場所として順列記憶部を一つ分のみ重複して使用し記憶部の使用量をm!−1個削減することも可能である。
【0045】
ここでは全単射関数の入出力データの大きさ(サイズ)mが2の場合についての例を説明する。
【0046】
このステップS1による順列(整数系列データ)の作成方法について、図9のフローチャートと共に説明する。まず、制御部2Aは、順列数設定部11に全単射関数の系列の数(順列数)m!(ここでは、m!=2)を設定する(ステップS101)。続いて、制御部2Aは、データ数記憶部3にデータ数m(ここではm=2)を設定し(ステップS102)、更に入力指定部7の値INPをデータの先頭の位置を示すものとして0に初期化した後(ステップS103)、入力指定部7が示す位置の順列作成部4の順列データの値A(INP)を0に設定する(ステップS104)。これにより、最初の設定位置の順列データはA(INP)=A(0)=0となる。
【0047】
次に、制御部2Aは、入力指定部7の値INPがデータの先頭の設定位置である0かどうかを判断し(ステップS105)、先頭の設定位置0であればステップS106へ進み、先頭の位置0でなければデータの重複有無のチェックのためステップS108へ進む。ここでは、入力指定部7の値INPがステップS103により先頭の設定位置0とされているので、ステップS106に進み、入力指定部7の値INPが最後の設定位置m−1(=1)かどうかを判断する。ここでは、入力指定部7の値INPが先頭の設定位置0であり最後の設定位置m−1(=1)ではないので、入力指定部7の値INPを次のデータの設定位置として1だけ加算した後(ステップS107)、順列作成部4の値A(INP)(ここでは、A(1))に設定データとして0を設定する(ステップS104)。これにより、A(INP)=A(1)=0となる。
【0048】
次に、制御部2Aは、入力指定部7の値INPが先頭のデータの位置として0かどうかを判断する(ステップS105)。ここでは、INPはステップS107により1とされており、先頭の位置0ではないのでステップS108へ進み、検索位置指定部12が示す検索位置POSを0に初期化する。続いて、制御部2Aは、入力指定部7が示す順列作成部4の値A(INP)が、検索位置指定部12が示す順列作成部4の値A(POS)と等しいかどうかを判定する(ステップS109)。ここでは、設定されているデータの値A(INP)がA(1)=0であり、検索位置のデータA(POS)がA(0)であり、A(0)は最初のステップS104の処理で0とされているため、両者は等しく、重複していると判定される(ステップS109のYes)。
【0049】
制御部2Aは、これにより、入力指定部7が示す順列作成部4の値A(INP)がデータの最大の設定値m−1と等しいかどうか判定する(ステップS115)。この時点では、A(INP)=A(1)=0であり、1(=mー1)と等しくないため、入力指定部7が示す順列作成部4の値A(INP)を1だけ加算して(ステップS119)、ステップS105に戻る。これにより、A(1)=1となる。
【0050】
続いて、制御部2Aは、入力指定部7の値INPが先頭の設定位置0であるかどうかを判定し(ステップS105)、ここでは先頭の設定位置0ではないので、ステップS108に進んで検索位置指定部12が示す検索位置POSを先頭の設定位置0に初期化した後、再び入力指定部7が示す順列作成部4の値A(INP)が、検索位置指定部12が示す順列作成部4の値A(POS)と等しいかどうかを判定する(ステップS109)。この時点では、A(INP)がA(1)=1であり、A(POS)がA(0)=0であるため、両者は等しくないと判定される(ステップS109のNo)。
【0051】
これにより、制御部2Aは、検索位置指定部12の検索位置の値POSを1だけ加算した後(ステップS110)、検索位置指定部12の値POSと入力指定部7の値INPとが等しいかどうかを判定する(ステップS111)。ステップS111の判定の結果、上記のPOSとINPとが等しいときには、全てのデータに重複が無いということになり、ステップS106に進み、等しくないときにはステップS109に進む。この時点では、上記のPOSとINPとは共に1であるので、両者は等しいと判定される。これにより、制御部2AはステップS106に進み、入力指定部7の値INPがデータの最後の設定位置1(=m−1)かどうかを判定する。
【0052】
ステップS106では、等しいと判定されるため、一つの関数のデータの作成が完了したことになり、続いて制御部2Aは順列数設定部11のPM(これはステップS101で設定されたm!=2である)の示す順列記憶部5の順列S(PM,0)〜S(PM,m-1)、すなわちS(2,0)、S(2,1)に、作成済みの関数のデータが設定された順列作成部4の値A(0)〜A(m-1)、すなわち、1番目の関数データの順列の値としてA(0)=0、A(1)=1を設定する(ステップS112)。
【0053】
続いて、制御部2Aは、順列数設定部11の示す値PMが最後の関数の数列の設定数の1かどうかを判定するが、1であれば全ての関数のデータm!−1個を作成済みとなり、もし1で無ければさらに残りの関数のデータの作成を行う(ステップS113)。この時点では、順列数設定部11の示す値PMは2であり、最後の関数データの値1ではないので、順列数設定部11の示す値PMを1だけ減算し次の関数データの設定位置を示すようにした後(ステップS114)、入力指定部7が示す順列作成部4の値A(INP)がデータの最大の設定値m−1であるかどうかを判定する(ステップS115)。
【0054】
この時点では、入力指定部7が示す順列作成部4の値A(INP)がA(1)=1であり、最大の値m−1に等しいので、続いて入力指定部7の値INPを1だけ減算し順列作成部の設定位置を戻した後(ステップS116)、入力指定部7の値INPはデータの先頭の設定位置0かどうか判定する(ステップS117)。この時点では入力指定部7の値INPは0で先頭であるので、制御部2Aは続いて入力指定部7の示す順列作成部4の値A(INP)、すなわちA(0)が最大の値m−1であるかどうかを判定する(ステップS118)。この時点では、A(0)は0であり、最大の値m−1(=1)に等しくないので、制御部2Aは入力指定部7の示す順列作成部4の値である関数の設定データA(INP)を次の順序の値として1だけ加算して(ステップS119)、ステップS105に戻る。これにより、関数データの設定値A(0)は1とされる。
【0055】
制御部2Aは、ステップS105において、入力指定部7の値INPが先頭のデータの設定位置0であると判定し、続いてステップS106において入力指定部7の値INPがデータの最大の設定値1(=m−1)と等しくないと判定し、ステップS107において入力指定部7のデータの設定位置の値INPを1だけ加算して次の設定データの位置の値として1とした後、ステップS104に戻り、入力指定部7の示す順列作成部4の関数データの設定値A(INP)を0に設定する。これにより、2番目の設定データA(INT)=A(1)=0となる。
【0056】
続いて、制御部2Aは、入力指定部7のデータの設定位置の値INPが先頭の位置0かどうかを判定し(ステップS105)、この時点ではINPは1であり、先頭の位置の値0ではないので、検索位置指定部12の検索位置の値POSを0に設定し(ステップS108)、入力指定部7が示す順列作成部4の値A(INP)が、検索位置指定部12が示す順列作成部4の値A(POS)と等しいかどうかを判定する(ステップS109)。ここでは、設定されたデータA(INP)がA(1)=0であり、検索位置のデータはA(POS)=A(0)=1であり、両者は等しくないため、ステップS110へ進んで検索位置指定部12の検索位置の値POSを次の値1にした後、ステップS111において検索位置の値POSが入力指定部7の値INPと等しいかどうかを判定する。この時点では、POS=INP=1であるので、ステップS106に進んで入力指定部7のデータ設定位置の値INPが1(=m−1)と等しいかどうかを判定する。この時点では、データの設定位置INP=1で最後の位置であるので、ステップS112に進んで順列記憶部5の順列S(PM,0)〜S(PM,m-1)、すなわち2番目の関数データの順列の値としてS(1,0)、S(1,1)に、順列作成部4の設定データの値A(0)=1、A(1)=0を設定する。
【0057】
そして、制御部2Aは順列数設定部11の値PMが最後の関数の数列の設定数の1であるかどうかを判定する(ステップS113)。この時点では順列数設定部11の値PMが最後の関数の設定数1であるので、制御部2Aは全数列を作成したことになるので、処理を終了する。
【0058】
このようにして、順列記憶部5の順列S(PM,0)〜S(PM,m-1)、すなわちS(2,0)、S(2,1)、S(1,0)、S(1,1)に、順列作成部4の値(順列)が記憶される。
【0059】
再び図7及び図8に戻って説明する。上記のステップS1の処理後、制御部2Aは、順列数設定部11に任意のデータ数mの全ての全単射関数の存在数(出力系列の数)PMとしてm!(=2)を設定した後(図7のステップS2)、データ数記憶部3に入出力データ(原像及び像)の数M(=m=2)を設定する(図7のステップS3)。
【0060】
続いて、制御部2Aは、周期記憶部10の各周期の個数を設定するPR(1,1)〜PR(m!,m)に各系列(1からm!)の各周期(1からm)の初期値として0を設定した後(図7のステップS4)、順列記憶部5に記憶され、順列数設定部11が示す全単射関数の1番目(PM=2)の系列データである順列S(2,0)〜S(2,m-1)の値(S(2,0)=0、S(2,1)=1)を周期計算部6にm個(m=2)の周期の計算用データP(0)〜P(m-1)として各々設定する(P(0)=0、P(1)=1)(図7のステップS5)。
【0061】
続いて、制御部2Aは、周期累計部9の値PSを0に設定した後(図7のステップS6)、最初の入力データに相当する先頭の位置(先頭のデータとして0)を入力指定部7の値INPに設定する(INP=0)(図7のステップS7)。次に、制御部2Aは、入力指定部7の値INPが示す、周期計算部6の周期の配列P(1)〜P(m)の位置の入力データ(データは0)に対応する出力データP(INP)(データは0)を出力記憶部8の値OUTPとして設定する(図7のステップS8)。
【0062】
続いて、制御部2Aは、出力記憶部8の出力データの値OUTPが既に系列に使用済みかどうかを判定する(図7のステップS9)。使用済みの場合は、使用済みのマークとして−1の値となっている。使用済みであれば図7のステップS10に進み、使用済みでなければ図8のステップS15に進む。この時点では、OUTPは0であり、−1(使用済み)ではないので、制御部2AはステップS15に進み、入力指定部7が示す値INP(ここでは0)の位置の周期計算部6の値P(INP)を、使用済みのマークとして−1に更新し、系列に使用済みであることを示す。
【0063】
続いて、制御部2Aは、出力記憶部8の出力データの値OUTP(ここでは0)を入力指定部7の値INPに設定する(図8のステップS16)。続いて、制御部2Aは、周期累計部9の値PSに1を加算して周期数を1に更新した後(図8のステップS17)、入力指定部7の値INP(ここでは0)が示す周期計算部6の位置の入力データに対応する出力データの値P(INP)(ここでは−1)を出力記憶部8の値OUTPに設定する(図8のステップS18)。
【0064】
次に、制御部2Aは、出力記憶部8の値OUTPが、既に系列に使用済みであることを示す−1であるかどうかを判定し(図8のステップS19)、使用済み(ー1)であればステップS23に進み、使用済みでなければステップS20に進む。ここでは、使用済みであるので、ステップS23に進み、順列数設定部11の値PMが示す周期記憶部10のm個の値PR(PM,1)〜PR(PM,m)のうち、周期累計部9の値PSに相当する位置PR(PM,PS)の周期の値に1を加算し(ここでは、周期1の位置に1を加算するPR(2,1)=PR(2,1)+1)、周期数を更新した後、次の周期の計算のために図7のステップS6に進む。
【0065】
ステップS6において、制御部2Aは、周期累計部9の値PSを0にクリアする。その後、制御部2Aは、最初の入力データに相当する先頭の位置(先頭のデータとして0)を入力指定部7の値INPに設定する(図7のステップS5)。続いて、制御部2Aは、入力指定部7の値INP(ここでは0)が示す周期計算部6の位置の入力データに対応する出力データの値P(INP)(ここでは−1)を出力記憶部8の値OUTPに設定する(図7のステップS8)。
【0066】
次に、制御部2Aは、出力記憶部8の値OUTPが、既に系列に使用済みであることを示す−1であるかどうかを判定し(図7のステップS9)、使用済み(ー1)であれば図7のステップS10に進み、使用済みでなければ図8のステップS15に進む。この時点では、使用済みであるので、制御部2AはステップS10に進み、入力指定部7の値INPが系列の最後の位置を示す値(m-1)かどうかを判定する。この時点では、上記の値INPは0であり、最後の位置1(=m-1)ではないので、値INPを1に更新した後(図7のステップS11)、ステップS8に戻り、再び入力指定部7の値INP(ここでは1)が示す周期計算部6の位置の入力データに対応する出力データの値P(INP)(ここでは1)を出力記憶部8の値OUTPに設定する。
【0067】
続いて、制御部2Aは、ステップS9において、出力記憶部8の値OUTPが、既に系列に使用済みであるかどうかを判定する。ここでは、出力記憶部8の値OUTPは1であり、−1ではないので、制御部2Aは図8のステップS15に進み、出力記憶部8の値OUTPが示す位置(ここでは1)の周期計算部6のデータの値P(INP)を使用済みのマークとして−1に更新し、系列に使用済みであることを記す。続いて、制御部2Aは、出力記憶部8の値OUTP(ここでは1)を入力指定部7の値INPに設定した後(ステップS16)、周期累計部9の値PSに1を加算して周期数を更新する(ステップS17)。これにより、周期数は1となる。続いて、制御部2Aは、入力指定部7の値INP(ここでは1)が示す周期計算部6の位置の入力データに対応する出力データの値P(INP)(ここでは−1)を出力記憶部8の値OUTPに設定する(ステップS18)。
【0068】
続いて、制御部2Aは、出力記憶部8の値OUTPが−1かどうかを判定する(ステップS19)。この時点では、上記のステップS18により上記の値OUTPは−1とされているので、制御部2AはステップS19において−1である(使用済みである)と判定し、続いてステップS23において順列数設定部11の値PMが示す周期記憶部10のm個の値PR(PM,1)〜PR(PM,m)のうち、周期累計部9の値PSに相当する位置PR(PM,PS)の周期の値に1を加算し(ここでは、周期1の位置に1を加算し周期1が2個となるPR(2,1)=PR(2,1)+1)、周期数を更新し図7のステップS6に進む。
【0069】
続いて、制御部2Aは、ステップS6で周期累計部9の値PSを0にクリアし、ステップS7で先頭の位置(先頭のデータとして0)を入力指定部7の値INPに設定し、ステップS8で入力指定部7の値INPが示す、周期計算部6の位置の入力データに対応する出力データP(INP)(ここでは−1)を出力記憶部8の値OUTPとして設定する。
【0070】
続いて、制御部2Aは、ステップS9において、出力記憶部8の値OUTPは−1であるかどうかを判定する。この時点では、値OUTPは−1であるので、制御部2AはステップS9において−1である(使用済みである)と判定し、次にステップS10に進んで入力指定部7の値INPが系列の最終の位置を示す値1(=m-1)であるかどうかを判定する。この時点では、入力指定部7の値INPは先頭の位置0であり、最後の位置1ではないので、制御部2Aは次にステップS11に進んで入力指定部7の値INPに1を加算して次の位置としステップS8に進む。これにより、上記の値INPは1となる。
【0071】
続いて、制御部2Aは、ステップS8において入力指定部7の値INPが示す、周期計算部6の位置の入力データに対応する出力データP(INP)(ここでは−1)を出力記憶部8の値OUTPとして設定した後、ステップS9において、出力記憶部8の値OUTPは−1であるかどうかを判定する。この時点では、値OUTPは−1であるので、制御部2AはステップS9において−1である(使用済みである)と判定し、次にステップS10に進んで入力指定部7の値INPが系列の最後の位置を示す値1(=m-1)であるかどうかを判定する。
【0072】
この時点では、入力指定部7の値INPは1であり、系列の最後の位置を示す値1と等しいので一つの関数に存在する全ての周期が求められたこととなり、制御部2Aは次にステップS12に進んで順列数設定部11の値PMが最後の関数に相当する値1であるかどうかを判定する。この時点では、順列数設定部11の値PMはステップS2で設定された2(=m!)であり、1ではないので、制御部2Aは順列数設定部11の値PMを1減算して1とした後(図7のステップS13)、ステップS5に戻り、再び順列数設定部11の値PMの示す順列記憶部5に記憶されている全単射関数の全ての系列データである順列S(PM,0)〜S(PM,m-1)に設定されたm個のデータ(ここでは、PM=1であるので、前述したように2番目の関数の2個のデータS(1,0)=1,S(1,1)=0)を、周期計算部6の周期の計算用データP(0)〜P(m-1)、すなわちP(0)=1、P(1)=0として各々設定する。
【0073】
制御部2Aは続いてステップS6で周期累計部9の値PSを0にクリアし、ステップS7で先頭の位置(先頭のデータとして0)を入力指定部7の値INPに設定した後、ステップS8へ進み、ここで入力指定部7の値INPが示す周期計算部6の位置の入力データに対応する出力データP(INP)(ここでは1)を出力記憶部8の値OUTPに設定する。続いて、制御部2AはステップS9に進んで値OUTPが−1(使用済み)ではないと判定した後、図8のステップS15へ進んで入力指定部7が示す値INPの位置の周期計算部6の値P(INP)を、使用済みのマークとして−1に更新し、系列に使用済みであることを示す。
【0074】
続いて、制御部2Aは、ステップS16で出力記憶部8の出力データの値OUTP(ここでは1)を入力指定部7の値INPに設定し、次のステップS17で周期累計部9の値PSに1を加算して周期数を1に更新し(周期数は1となる)、次のステップS18で入力指定部7の値INP(ここでは1)が示す、周期計算部6の位置の入力データに対応する出力データP(INP)(ここでは0)を出力記憶部8の値OUTPに設定する。
【0075】
次に、制御部2Aは、出力記憶部8の値OUTPが、既に系列に使用済みであることを示す−1であるかどうかを判定し、使用済み(ー1)であればステップS23に進み、使用済みでなければステップS20に進む。ここでは、OUTPは0であり−1ではない(使用済みでない)ので、ステップS20に進み、入力指定部7の値INP(ここでは1)が示す位置の周期計算部6の出力データの値P(INP)である0を入力指定部7の値INPに設定する。
【0076】
続いて、制御部2Aは、入力指定部7の値INP(ここでは0)が示す位置の周期計算部6の出力データの値P(0)を、−1に更新して系列に使用済みであることを記した後(図8のステップS21)、周期累計部9の値PSを1加算し周期数を更新し、ステップS18に進む。これにより、周期の値PSは2となる。
【0077】
ステップS18では入力指定部7の値INPが示す、周期計算部6の位置P(INP)の入力データに対応する出力データの値(INP=0でP(INP)は−1)を出力記憶部8の値OUTPに設定する。続いて、制御部2Aは、ステップS19において出力記憶部8の値OUTPが−1であるかどうかを判定する。ここでは、出力記憶部8の値OUTPが−1であるので、ステップS23に進み、順列数設定部11の値PMが示す周期記憶部10のm個の周期の値PR(PM,1)〜PR(PM,m)のうち、周期累計部9の値PSに相当する値PR(PM,PS)に1を加算し(ここでは、周期2の位置に1を加算しPR(1,2)=1となり、周期2が1個となる)、周期数を更新した後、図7のステップS5に進む。
【0078】
続いて、制御部2Aは、再び前述したステップS6、S7を経てステップS8へ進み、ここで入力指定部7の値INPが示す周期計算部6の値P(INP)の位置の入力データ(ここでは0)に対応する出力データ(ここでは−1)を出力記憶部8の値OUTPに設定する。続いて、制御部2AはステップS9に進んで出力記憶部8の値OUTPが−1であり、使用済みであると判定した後、ステップS10に進んで入力指定部7の値INPが0であり、系列の最終の位置1(=m−1)ではないと判定するので、ステップS11に進んで入力指定部7の値INPを1加算してINPを1とする。
【0079】
続いて、制御部2Aは、ステップS8において入力指定部7の値INP(ここでは1)が示す周期計算部6の値P(INP)の位置の入力データ(ここでは1)に対応する出力データ(ここでは−1)を出力記憶部8の値OUTPに設定した後、ステップS9に進んで出力記憶部8の値OUTPが−1であり、使用済みであると判定した後、ステップS10に進んで入力指定部7の値INPが1であり、系列の最後の位置1(=m−1)であると判定する。
【0080】
これにより、制御部2Aは、順列数設定部11が示す値PMがデータの最後の位置の1かどうかを判定する(図8のステップS12)。この時点では、前述したステップS13の処理によりPMは1となっているので、ステップS12でPMが1であると判定され、全ての系列の処理が行われたと判断して処理を終了する(図8のステップS14)。全ての処理を終了した場合には、周期記憶部10には、この全単射関数の各々の系列の各周期長の全ての存在数が求まっている。ここでは、m=2であり、周期記憶部10には、周期1が2個、周期2が1個を示す値が記憶されている。
【0081】
このように、本実施形態によれば、図10に示すような関数の帰還により周期を求めることができる。図10において、m!個の全単射関数の作成した順列データのそれぞれについて、各全単射関数の0からm−1までのm個の入力データのうちの最小のものである0の値を最初の入力データとし、その出力データを更に入力データとして帰還し、入力データが最初の入力データである0に戻るまでの帰還回数を求めて系列周期とする。このとき出現した出力データには出現済みと判断できるように−1等の出力データに存在しない値を周期計算部6に設定することで、未出現の出力データと区別する。
【0082】
もし、m個の全てのデータが系列に出現した場合には最大周期となり、完全擬似乱数の系列が作成されたことになる。しかし、未出現の出力データが残存する場合には、周期は部分的な系列のものであり、未出現の残りのデータに更に部分的な別の周期が存在することになる。未出現の出力データが残存する場合には、更に未出現の出力データのうちの入力データの最小のものを新たな周期の最初の入力データとし、その入力データに戻るまでの新たな系列周期を求め、全ての出力データが系列に出現し尽すまでこの手順を繰り返す。そして、m!個の全ての順列データ(関数)について、この手順でそれぞれの周期数とその各周期の存在数を求める。
【0083】
このようにして、本実施形態によれば、全ての全単射関数の全ての整数系列の全周期を判定することができる。そして、任意の周期の全単射関数を用いた擬似乱数系列や変換表などを作成することができる。
【0084】
(第2の実施形態)
図11は、本発明になる整数系列の周期判定装置の第2の実施形態のブロック図を示す。同図に示すように、本実施形態の整数系列の周期判定装置1Bは、装置1B全体を統括的に制御する制御部2B、データ数記憶部3、順列作成部4、順列記憶部5、周期計算部6、入力指定部7、出力記憶部8、周期累計部9、周期記憶部10から構成されており、第1の実施形態の整数系列の周期判定装置1Aと比較すると、順列数設定部11と検索位置指定部12を有しない。
【0085】
制御部2B、順列作成部4及び周期計算部6は、例えば中央処理装置(CPU)により構成される。また、データ数記憶部3、出力記憶部8、周期累計部9及び周期記憶部10は記憶装置により構成され、入力指定部7は所定の入力装置により構成される。
【0086】
データ数記憶部3は、単射で、かつ、全射でもある関数である全単射関数の有する連続した自然数の入出力データ(原像及び像)の数Mを記憶する。順列作成部4は、周期を判定するために予め事前に用意されたデータである、全単射関数の入力に対する出力データ(原像に対する像)の並びである順列A(i)を設定する。この場合、順列A(i)は、出力データの値に重複せず、全ての値が出現するように作成されたものとする。順列記憶部5は、任意のデータ数mの全単射関数の入力に対する出力データ(原像に対する像)の並びである順列S(j)を予め記憶している第1の記憶部である。周期計算部6は、後述するように任意の全単射関数の入力に対する出力データ(原像に対する像)を更に入力とする手順を繰り返し行って、判定する整数系列の周期Pを計算する。
【0087】
入力指定部7は、入力位置(原像の位置)INPを指定する。出力記憶部8は、入力指定部7で指定された入力位置の周期計算部6の出力データ(像)の値OUTPを記憶する。周期累計部9は、周期計算部6で計算した周期Pの累積結果PSを記憶する。周期記憶部10は、周期計算部6の周期計算結果PR(PM,M)を記憶する第2の記憶部である。本実施形態では、周期記憶部10は、任意のデータ数m(ここでは、m=3とする)の全単射関数の部分周期を含めた全ての周期について存在数を記憶する。
【0088】
上記の構成のうち、制御部2B、データ数記憶部3、順列作成部4、周期計算部6、入力指定部7、及び周期累計部9は、m!個の全単射関数のうち、所望の1個の全単射関数のm個の整数からなる整数系列の入力に対する出力の状態を順列として生成して第1の記憶部である順列記憶部5に記憶する順列記憶手段を構成する。また、制御部2B、周期計算部6、入力指定部7、出力記憶部8及び周期累計部9は、順列記憶部5に記憶された順列の周期を計算して第2の記憶部である周期記憶部10に記憶する周期計算及び累計手段を構成する。
【0089】
次に、本実施形態の動作について、図12及び図13のフローチャートを併せ参照して説明する。
【0090】
図11において、制御部2Bは、まず、データ数記憶部3にデータ数m(ここでは、m=3)を設定する(図12のステップS31)。続いて、制御部2Bは、周期記憶部10に記憶されている周期PR(0)〜PR(m-1)の各値を0に設定した後(図12のステップS32)、順列作成部4に全単射関数の入出力データとして、入力データ(0からm−1までの自然数)に対応する出力系列データA(0)〜A(m-1)を設定する(図12のステップS33)。具体的には、この出力系列データA(0)〜A(m-1)は、0からm−1までの重複しない自然数の任意の組み合わせのデータで、ここではm=3であるので、例えば、A(0)=2,A(1)=0,A(2)=1の3個のデータである。
【0091】
続いて、制御部2Bは、順列作成部4に設定した上記の3個の出力系列データA(0)〜A(2)を順列記憶部5の順列S(0)〜S(m-1)にそれぞれ格納する(図12のステップS34)。ここでは、上記の順列記憶部5には、S(0)=2,S(1)=0,S(2)=1の3個の順列が格納されることになる。
【0092】
続いて、制御部2Bは、順列記憶部5に格納された順列S(0)〜S(m-1)を、周期計算部6に計算用のデータP(0)〜P(m-1)としてそれぞれ関数の出力データを設定する(図12のステップS35)。ここでは、上記の周期計算部6には、P(0)=2,P(1)=0,P(2)=1の3個が設定されることになる。
【0093】
続いて、制御部2Bは、周期累計部6の周期の値PSを0に設定(クリア)した後(図12のステップS36)、最初の入力データに相当する先頭のデータの位置(例えば0)を入力指定部7の値INPとして設定する(図12のステップS37)。次に、制御部2Bは、入力指定部7の値INPが示す周期計算部6の入力データに対応する出力データの値P(INP)を出力記憶部8の値OUTPに設定する(図12のステップS38)。ここでは、INPは0であるので、入力データはP(0)であり、それに対応する出力データは前述したように2であるから、OUTPは2に設定される。
【0094】
続いて、制御部2Bは、出力記憶部8の値OUTPが既に系列に使用済みかどうかを比較する(図12のステップS39)。使用済みなら使用済みのマークとして−1の値となっている。ここでは、OUTPは2であり、−1ではないので、制御部2Bは使用済みでないと判定し、図13のステップS43に進んで、入力指定部7の値INPが示す周期計算部6の入力データに対応する出力データの値P(INP)を−1に設定し、系列に使用済みであることを示す。これにより、P(0)=−1となる。
【0095】
次に、制御部2Bは、出力記憶部8の値OUTP(ここでは2)を入力指定部7の値INPに設定する(図13のステップS44)。続いて、制御部2Bは、周期累計部9の値PSに1を加算し周期数を更新する(図13のステップS45)。これにより、周期数PSは1となる。続いて、制御部2Bは、入力指定部7の値INP(ここでは2)が示す、周期計算部6の入力データに対応する出力データの値P(INP)を出力記憶部8の値OUTPに設定する(図13のステップS46)。ここでは、INPは2であるから、P(2)に対応する出力データは前述したように1であるから、OUTPは1に設定される。
【0096】
次に、制御部2Bは、出力記憶部8の値OUTPが使用済みであることを示す−1であるかどうかを判定する(図13のステップS47)。ここでは、上記のようにOUTPは1であり、−1ではないので、制御部2Bは、入力指定部7の値INP(ここでは2)が示す、周期計算部6の位置の入力データの値P(INP)に対応する出力データ(ここでは1)を入力指定部7の値INPに設定する(図13のステップS48)。続いて、制御部2Bは、入力指定部7の値INP(ここでは1)が示す、周期計算部6の入力データに対応する出力データの値P(INP)を−1に設定し、系列に使用済みであることを示す(図13のステップS49)。これにより、P(1)=−1となる。
【0097】
次に、制御部2Bは、周期累計部9の周期の値PSに1を加算して2とし、周期数を更新した後(図13のステップS50)、ステップS46に戻り、入力指定部7の値INP(ここでは1)が示す、周期計算部6の位置の入力データに対応する出力データの値P(INP)を出力記憶部8の値OUTPに設定する。ここでは、INPは1であるから、P(1)に対応する出力データは−1であるから、OUTPは−1に設定される。
【0098】
次に、制御部2Bは、出力記憶部8の値OUTPが使用済みであることを示す−1であるかどうかを判定する(図13のステップS47)。ここでは、上記のようにOUTPは−1であるから、制御部2Bは使用済みと判断し、周期累計部9の示す値PS(ここでは2)に相当する、周期記憶部10の位置の周期の値PR(PS)に1を加算して、周期数を更新した後(図13のステップS51)、図12のステップS36に進む。これにより、PR(2)は1になる。つまり、周期2の周期数が1個と判定される。
【0099】
続いて、制御部2BはステップS36において、周期累計部6の値PSを0に設定(クリア)した後、最初の入力データに相当する先頭の位置(例えば0)を入力指定部7の値INPとして設定し(ステップS37)、更に、入力指定部7の値INPが示す周期計算部6の位置の入力データに対応する出力データP(INP)を出力記憶部8の値OUTPに設定する(ステップS38)。ここでは、INPは0であるので、入力データはP(0)であり、それに対応する出力データは前述したように−1であるから、OUTPは−1に設定される。
【0100】
続いて、制御部2Bは、ステップS39において、出力記憶部8の値OUTPが−1であり、既に系列に使用済みであると判定してステップS40に進む。ステップS40では、制御部2Bは、入力指定部7の値INPが系列の最後の位置(m-1)を示す2であるかどうかを判定する。ここでは、INPは0であり2ではないので、制御部2Bは入力指定部7の値INPを1加算して1とした後(図12のステップS42)、ステップS38に進み入力指定部7の値INPが示す周期計算部6の位置の入力データに対応する出力データP(INP)を出力記憶部8の値OUTPに設定する。ここでは、INPは1であるので、入力データはP(1)であり、それに対応する出力データは前述したように1であるので、OUTPは1に設定される。
【0101】
続いて、制御部2Bは出力記憶部8の値OUTPが使用済みであることを示す−1であるかどうか判定する(ステップS39)。ここでは、OUTPは1であり、−1ではないので、制御部2Bは使用済みでないと判定し、図13のステップS43に進んで、入力指定部7の値INPが示す周期計算部6の位置の入力データの値に対応する出力データP(INP)を−1に設定し、系列に使用済みであることを示す。これにより、P(1)=−1となる。
【0102】
以後、制御部2Bは、前述したステップS44、S45、S46の各処理を行った後、ステップS47で出力記憶部8の値OUTPが使用済みであることを示す−1であると判定し、ステップS51に進んで周期累計部9の示す値PS(ここでは1)に相当する、周期記憶部10の位置の周期の値PR(PS)に1を加算して、周期数を更新する。これにより、PR(1)は1になる。つまり、周期1の周期数が1と判定される。
【0103】
その後、制御部2Bは、前述したステップS36、S37、S38の各処理を行った後、ステップS39で出力記憶部8の値OUTPが使用済みであることを示す−1であると判定し、ステップS40に進んで入力指定部7の値INPが系列の最後の位置(m-1)を示す2であるかどうかを判定する。ここでは、INPは0であり2ではないので、制御部2Bは入力指定部7の値INPを1加算して1とした後(ステップS42)、ステップS38に進み入力指定部7の値INPが示す周期計算部6の位置の入力データP(INP)に対応する出力データを出力記憶部8の値OUTPに設定する。ここでは、INPは1であるので、入力データはP(1)であり、それに対応する出力データは前述したように−1であるので、OUTPは−1に設定される。
【0104】
続いて、制御部2Bは、ステップS39において、出力記憶部8の値OUTPが−1であり、既に系列に使用済みであると判定してステップS40に進む。ステップS40では、制御部2Bは、入力指定部7の値INPが系列の最後の位置(m-1)を示す2であるかどうかを判定する。ここでは、INPは1であり2ではないので、制御部2Bは入力指定部7の値INPを1加算して2とした後(ステップS42)、ステップS38に進み入力指定部7の値INPが示す周期計算部6の位置の入力データに対応する出力データP(INP)を出力記憶部8の値OUTPに設定する。ここでは、INPは2であるので、入力データはP(2)であり、それに対応する出力データは前述したように−1であるので、OUTPは−1に設定される。
【0105】
続いて、制御部2Bは、ステップS39において、出力記憶部8の値OUTPが−1であり、既に系列に使用済みであると判定してステップS40に進む。ステップS40では、制御部2Bは、入力指定部7の値INPが系列の最後の位置(m-1)を示す2であるかどうかを判定する。ここでは、INPは2であるので、制御部2Bは入力指定部7の値INPが系列の最後の位置に達し、全ての入出力データの処理を行ったと判断して、全ての処理を終了する(図12のステップS41)。このようにして、周期記憶部10に格納されている周期PR(1)〜PR(3)には、この関数の各周期長の全ての存在数が設定された状態となる。本実施形態では、m=3の場合であり、上記のようにこの全単射関数の有する各周期数として周期数1を示すPR(1)が1個と、周期数2を示すPR(2)が1個と求まる。
【0106】
このようにして、本実施形態によれば、任意の入出力データ数の全単射関数の任意のデータ系列についての部分周期を含めた全ての周期を求めることができる。
【0107】
(第3の実施形態)
次に、本発明になる整数系列の周期判定装置の第3の実施形態について説明する。本実施形態の周期判定装置のハードウェア構成は、図11に示した整数系列の周期判定装置1Bと同じ構成であるが、制御部2Bによるソフトウェア動作が以下説明するように第2の実施形態と異なる。
【0108】
本実施形態は、大きさ3(m=3)の自然数からなる全単射関数が与えられた場合、その全単射関数が最大周期3(=m)を有するかの確認方法として、或る初期値(例えば0)を入力値として全単射関数に与えて、その出力(例えば0)が初期値に戻るまで全単射関数の変換を繰り返し、その繰り返しの回数である周期が3(=m)となった場合には、全ての入出力値を網羅し、最大周期であると判定し、変換の繰り返し回数が3(=m)より小さかった場合には最大周期ではないと判断する。
【0109】
次に、本実施形態のハードウェア資源を利用したソフトウェア動作について、図14のフローチャートと共に説明する。前述したように、m=3の場合の最大周期は3である。本実施形態は、例えば、前記f5のように入力0のとき出力2、入力1のとき出力0、入力2のとき出力1のデータが最大周期3となるかどうかの判定を行う。
【0110】
図11において、制御部2Bは、まず、データ数記憶部3にデータ数m(ここでは、m=3)を設定する(図14のステップS61)。続いて、制御部2Bは、周期累計部9の値PSを0に設定(クリア)した後(ステップS62)、順列作成部4に全単射関数の入出力データとして、入力データ(0からm−1までの自然数)に対応する出力系列データA(0)〜A(m-1)を設定する(ステップS63)。具体的には、この出力系列データA(0)〜A(m-1)は、0からm−1までの重複しない自然数の任意の組み合わせのデータで、ここではm=3であるので、例えば、A(0)=2,A(1)=0,A(2)=1の3個のデータである。ここで、A(0)=2は、入力0のとき出力2、A(1)=0は入力1のとき出力0、A(2)=1は入力2のとき出力1を示す。
【0111】
続いて、制御部2Bは、順列作成部4に設定した上記の3個の出力系列データA(0)〜A(2)を順列記憶部5の順列S(0)〜S(m-1)にそれぞれ格納する(ステップS64)。ここでは、上記の順列記憶部5には、S(0)=2,S(1)=0,S(2)=1の3個の順列が格納されることになる。これら3個の順列は、所望の1個の全単射関数の3つの入力値に対する出力の状態を記述したものである。
【0112】
続いて、制御部2Bは、順列記憶部5に格納された順列S(0)〜S(m-1)を、周期計算部6に周期P(0)〜P(m-1)としてそれぞれ設定する(ステップS65)。ここでは、上記の周期計算部6には、P(0)=2,P(1)=0,P(2)=1の3個の周期が設定されることになる。ここで、P(0)=2は、入力0のとき出力2の周期、P(1)=0は入力1のとき出力0の周期、P(2)=1は入力2のとき出力1の周期を示す。
【0113】
続いて、制御部2Bは、最初の入力データに相当する先頭の位置(この場合、入力位置0)を示す値を入力指定部7の値INPに設定する(ステップS66)。これにより、INPは0となる。続いて、制御部2Bは、入力指定部7の値INP(ここでは0)が示す、周期計算部6の位置の入力データに対応する、出力データP(INP)を出力記憶部8の値OUTPに設定する(ステップS67)。ここでは、INPは0であるので、入力データは0であり、それに対応する出力データP(0)は前述したように2であるから、OUTPは2に設定される。
【0114】
続いて、制御部2Bは、出力記憶部8の値OUTP(ここでは2)を入力指定部7の値INPに設定した後(ステップS68)、周期累計部9の周期の値PSに1を加算して周期数を更新する(ステップS69)。これにより、INPは2、PSは1となる。
【0115】
次に、制御部2Bは、出力記憶部8の値OUTP(ここでは2)が最初の入力データの値0であるかどうかを判定する(ステップS70)。OUTPの値が最初の入力データの値と等しければステップS71に進み、等しくなければステップS67に戻る。この時点では、OUTPは2であり、0ではないので制御部2BはステップS67に戻り、入力指定部7の値INP(ここでは2)が示す、周期計算部6の位置の入力データに対応する、出力データP(INP)を出力記憶部8の値OUTPに設定する。ここでは、入力データINPは2であるので、それに対応する出力データは前述したように1であるから、OUTPは1に設定される。
【0116】
続いて、制御部2Bは、出力記憶部8の値OUTP(ここでは1)を入力指定部7の値INPに設定した後(ステップS68)、周期累計部9の値PSに1を加算して周期数を更新する(ステップS69)。これにより、INPは1、PSは2となる。
【0117】
次に、制御部2Bは、出力記憶部8の値OUTP(ここでは1)が最初の入力データの値0であるかどうかを再び判定する(ステップS70)。この時点では、OUTPは1であり、0ではないので制御部2BはステップS67に戻り、再び入力指定部7の値INP(ここでは1)が示す、周期計算部6の位置の入力データINPに対応する、出力データP(INP)を出力記憶部8の値OUTPに設定する。ここでは、INPは1であるので、入力データに対応する出力データP(1)は前述したように0であるから、OUTPは0に設定される。
【0118】
続いて、制御部2Bは、出力記憶部8の値OUTP(ここでは0)を入力指定部7の値INPに設定した後(ステップS68)、周期累計部9の値PSに1を加算して周期数を更新する(ステップS69)。これにより、INPは0、PSは3となる。
【0119】
次に、制御部2Bは、出力記憶部8の値OUTP(ここでは0)が最初の入力データの値0であるかどうかを再び判定する(ステップS70)。この時点でOUTPが0であり、最初の入力値であると判定される。続いて、制御部2Bは周期累計部9の周期の値PSは系列長mであるかどうかを判定する(ステップS71)。この時点では、累計計算部9の値PSは系列長m(=3)に等しいので、制御部2Bは最大長(最大周期)であると判定する(ステップS72)。すなわち、m=3の場合、入力0のとき出力2、入力1のとき出力0、入力2のとき出力1のデータが最大周期であると判定され、その周期長PSは3と求められる。
【0120】
なお、ステップS71において、周期累計部9の値PSが系列長mでないと判定されたときは、そのときの入力データは最大長ではないと判定される(ステップS73)。
【0121】
このようにして、本実施形態によれば、任意の入出力データの大きさの全単射関数の最大周期長を判定することができる。そして、最大周期となる全単射関数を用いて、擬似乱数系列や変換表などを作成することができる。
【0122】
ところで、以上の実施形態では、データ数(系列長)mが2又は3の場合について説明したが、mが9までの周期長の個数は表4に示される。
【0123】
【表4】
この表4から分るように、入出力データ数(系列長)mを有する全単射関数の平均周期長はm/2となる。これにより、mが2128の場合では、全単射関数の数は2128!個となり、周期長は1が2128!個で、2が2128!/2個、3が2128!/3個で、最大周期となる周期長2128は2128!/2128個存在する。ここで、平均周期長は2128/2となる。
【0124】
また、128ビットブロック暗号の場合について考えると、128ビット鍵の数は2128個であることから、128ビットブロック暗号はm=2128の全単射関数全ての関数2128!個のうちの2128個を鍵で選択して用いているといえる。そして、m=2128の全単射関数の最大周期2128は2128!/2128個存在することから、128ビットブロック暗号の鍵の総数から考慮して、全ての鍵から最大周期となるものは、
2128!/2128×2128/2128!=1
と記述できることから全ての鍵のうちで最大周期となるものの確率は、高々1個である。
【0125】
ただし、ここで述べている最大周期とは128ビットの出力データの組み合わせが各々1回出現することであり、その出力データの任意の1ビットをそれぞれ抽出した場合に、その系列としてM系列のような最大長のビット系列が必ず得られるものではなく、そのためには最大周期となる系列から更に選択が必要である。
【0126】
なお、以上の実施形態で判定した最大周期を持つ全単射関数の整数系列を2種類以上組み合わせて用いることで、更に長い周期の擬似乱数系列を生成することもできる。例えば、m1とm2の2つの周期の異なる最大長系列において、1以外の約数を持たない互いに素となる周期の組み合わせとなるものを組み合わせれば、最大周期はm1×m2となる。
【0127】
なお、本発明は以上の実施形態に限定されるものではなく、例えば、図7、図8、図9と共に説明した第1の実施形態の各ステップの処理や、図12及び図13と共に説明した第2の実施形態の各ステップの処理や、図14と共に説明した第3の実施形態の各ステップの処理をコンピュータによるソフトウェア処理により実行させる整数系列の周期判定プログラムも本発明は包含するものである。この整数系列の周期判定プログラムは、図1の制御部2Aや図11の制御部2Bにより実行される。
【符号の説明】
【0128】
1A、1B 整数系列の周期判定装置
2A、2B 制御部
3 データ数記憶部
4 順列作成部
5 順列記憶部
6 周期計算部
7 入力指定部
8 出力記憶部
9 周期累計部
10 周期記憶部
11 順列数設定部
12 検索位置指定部
【技術分野】
【0001】
本発明は整数系列の周期判定方法、周期判定装置及び周期判定プログラムに係り、特に擬似乱数等に用いられる整数系列の周期判定方法、周期判定装置及び周期判定プログラムに関する。
【背景技術】
【0002】
近年、暗号やモンテカルロ法等に用いられる擬似乱数系列は、暗号解析の困難性を高めるために、周期の長い系列が要求される。また、これまで系列長が保証された擬似乱数系列として、M系列等が使用されることが多かったが、それ以外の手段として、カオスや帰還関数等を用いた生成方法を利用することが考えられる(例えば、非特許文献1、非特許文献2参照)。非特許文献1には、シフトレジスタを用いて周期の長い擬似乱数系列を発生することが開示されている。また、非特許文献2には擬似乱数系列を発生させる暗号理論一般について開示されている。
【0003】
また、暗号解析の困難性を高め、安全性の高い擬似乱数系列を生成するために、複数の異なるSボックスを利用した処理を行う構成の暗号処理装置(例えば、特許文献1参照)や、線形フィードバックシフトレジスタを利用したM系列の出力に非線形関数をフィルタとして用いることで、出力擬似乱数系列を推定困難にする構成の擬似乱数系列生成装置が知られている(例えば、特許文献2参照)。
【0004】
更に、擬似乱数系列の利用可能性に基づいて、システム内の乱数生成器の系列反復周期を拡張するために、複数の互いに素となる数を法としてRNS(Residue Number System)剰余値を求め、それを組み合わせて出力系列とすることで系列長を拡張する方法も知られている(例えば、特許文献3参照)。
【先行技術文献】
【非特許文献】
【0005】
【非特許文献1】Solomon Wolf Golomb,“Shift Register Sequences”,San Francisco,Holden-Day,1967.
【非特許文献2】Bruce Schneier,“Applied Cryptography”,Second Edition,John Wiley & Sons,Inc.1996.
【特許文献】
【0006】
【特許文献1】特開2008−58828号公報
【特許文献2】特開平8−202535号公報
【特許文献3】特開2009−3925号公報
【発明の概要】
【発明が解決しようとする課題】
【0007】
しかしながら、カオスや帰還関数等を用いた生成方法を利用して擬似乱数系列を生成する場合は、生成した擬似乱数系列長が明らかでない場合があり、また生成された擬似乱数系列が短周期等の理由より使用目的によっては適さない擬似乱数系列を使用せざるを得ない場合もある。
【0008】
また、特許文献1及び2各記載の装置では、生成した擬似乱数系列の周期を判定して、その周期の長さや周期の個数を求める機能は有しておらず、周期に使用した値を使用済みとして区別する機能を有していない。更に、特許文献3記載の方法も、擬似乱数系列の周期を判定して、その周期の長さや個数を求める機能や、剰余を利用することなく完全擬似乱数を求めることについては全く開示されていない。
【0009】
このように、従来は擬似乱数系列の周期を判定することは知られておらず、このことから系列長の保証された完全擬似乱数を得ることは容易でなかった。
【0010】
本発明は以上の点に鑑みなされたもので、擬似乱数系列の生成のために、任意の大きさの自然数の集合による全単射関数を用いて生成された整数系列の周期を判定し得る整数系列の周期判定方法、周期判定装置及び周期判定プログラムを提供することを目的とする。
【0011】
また、本発明の他の目的は、自然数を入出力とする全単射関数及び変換表もしくはSボックス等の出力フィードバックにおいて、周期長の合計を求める演算を行い、各周期長が幾つ存在するかの結果や、最大長の周期を保有するかどうかの判定が可能である整数系列の周期判定方法、周期判定装置及び周期判定プログラムを提供することにある。
【課題を解決するための手段】
【0012】
上記の目的を達成するため、第1の発明の整数系列の周期判定方法は、制御部が、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!(m!はmの階乗。即ち1×2×・・・×(m−1)×mを表す。)個の全単射関数(写像)についての前記m種類の入力に対する出力の状態を全て順列として生成して第1の記憶部に記憶する第1のステップと、制御部が、第1の記憶部に記憶されたm!個の全単射関数についての順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、周期がmより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての入力値及び全ての未出現の入力値に対して順次行う第2のステップと、制御部が、第2のステップで求められたm!個の全単射関数の最小周期から最大周期までの周期を第2の記憶部に記憶する第3のステップとを含むことを特徴とする。
【0013】
また、上記の目的を達成するため、第2の発明の整数系列の周期判定方法は、制御部が、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数(写像)のうち、所望の1個の前記全単射関数の前記m個の整数からなる整数系列の入力に対する出力の状態を順列として第1の記憶部に記憶する第1のステップと、制御部が、前記m個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第2の記憶部に記憶することを、前記m個の入力のすべてについて行う第2のステップと、制御部が、前記第2の記憶部に記憶された周期が前記mであるか否かを判定し、前記周期が前記mであるとき、その周期を前記所望の1個の前記全単射関数の最大周期であると決定する第3のステップとを含むことを特徴とする。
【0014】
また、上記の目的を達成するため、第3の発明の整数系列の周期判定装置は、第1及び第2の記憶部と、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数(写像)についての前記m種類の入力に対する出力の状態を全て順列として生成して前記第1の記憶部に記憶する順列生成及び記憶手段と、第1の記憶部に記憶されたm!個の全単射関数についての順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、周期がmより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての入力値及び全ての未出現の入力値に対して順次行う周期計算及び累計手段と、前記周期計算及び累計手段で得られた前記m!個の全単射関数の最小周期から最大周期までの周期を第2の記憶部に記憶する記憶手段とを有することを特徴とする。
【0015】
また、上記の目的を達成するため、第4の発明の整数系列の周期判定装置は、第1及び第2の記憶部と、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数(写像)のうち、所望の1個の前記全単射関数の前記m個の整数からなる整数系列の入力に対する出力の状態を順列として第1の記憶部に記憶する順列記憶手段と、m個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第2の記憶部に記憶することを、前記m個の入力のすべてについて行う周期計算及び累計手段と、第2の記憶部に記憶された周期が前記mであるか否かを判定し、前記周期が前記mであるとき、その周期を前記所望の1個の前記全単射関数の最大周期であると決定する最大周期判定手段とを有することを特徴とする。
【0016】
また、上記の目的を達成するため、第5の発明の整数系列の周期判定プログラムは、コンピュータに、第1の発明の整数系列の周期判定方法の第1乃至第3のステップを実行させることを特徴とする。
【0017】
更に、上記の目的を達成するため、第6の発明の整数系列の周期判定プログラムは、コンピュータに、第2の発明の整数系列の周期判定方法の第1乃至第3のステップを実行させることを特徴とする。
【発明の効果】
【0018】
本発明によれば、任意の大きさの自然数の集合を入力(原像)と出力(像)とした全単射関数(写像)を用いて出力を入力に帰還することで生成された整数系列の帰還周期の判定が行え、また、その整数系列の最大周期を判定することができる。
【図面の簡単な説明】
【0019】
【図1】本発明の整数系列の周期判定装置の第1の実施形態のブロック図である。
【図2】全単射関数の一例の説明図である。
【図3】本発明による擬似乱数作成の概要の説明図である。
【図4】本発明の第1の実施形態の概要説明用フローチャートである。
【図5】本発明の第1の実施形態の全単射関数の入出力データの順列作成の概要説明用フローチャートである。
【図6】本発明の第1の実施形態の作成した各々の順列データから各周期を判定する概要説明用フローチャートである。
【図7】本発明の第1の実施形態の動作を説明するフローチャート(その1)である。
【図8】本発明の第1の実施形態の動作を説明するフローチャート(その2)である。
【図9】図7中のステップS1の詳細動作を説明するフローチャートである。
【図10】本発明による周期の判定動作のための関数帰還を説明する図である。
【図11】本発明の整数系列の周期判定装置の第2、第3の実施形態のブロック図である。
【図12】本発明の第2の実施形態の動作を説明するフローチャート(その1)である。
【図13】本発明の第2の実施形態の動作を説明するフローチャート(その2)である。
【図14】本発明の第3の実施形態の動作を説明するフローチャートである。
【発明を実施するための形態】
【0020】
次に、本発明の各実施形態について、図面と共に詳細に説明する。
【0021】
(第1の実施形態)
図1は、本発明になる整数系列の周期判定装置の第1の実施形態のブロック図を示す。同図に示すように、本実施形態の整数系列の周期判定装置1Aは、装置1A全体を統括的に制御する制御部2A、データ数記憶部3、順列作成部4、順列記憶部5、周期計算部6、入力指定部7、出力記憶部8、周期累計部9、周期記憶部10、順列数設定部11、検索位置指定部12から構成されている。
【0022】
制御部2A、順列作成部4、周期計算部6、順列数設定部11及び検索位置指定部12は、例えば中央処理装置(CPU)により構成される。また、データ数記憶部3、出力記憶部8、周期累計部9及び周期記憶部10は記憶装置により構成され、入力指定部7は所定の入力装置により構成される。
【0023】
データ数記憶部3は、単射で、かつ、全射でもある関数である全単射関数の有する連続した自然数の入出力データ(原像及び像)の数Mを記憶する。順列作成部4は、全単射関数の入力に対する出力データ(原像に対する像)の並びである順列A(i)を作成する。この場合、順列A(i)は、出力データの値は重複せず、全ての値が出現するように作成される。
【0024】
順列記憶部5は、後述するようにして作成された任意の大きさ(データ数M)m(mは2以上の自然数)の全ての全単射関数(写像)の入力に対する出力(原像に対する像)の状態を示す順列S(i,j)を記憶する第1の記憶部である。周期計算部6は、後述するように任意の全単射関数の入力に対する出力データ(原像に対する像)を更に入力とする手順を繰り返し行って、作成する整数系列の周期Pを計算する。
【0025】
入力指定部7は、入力位置(原像の位置)INPを指定する。出力記憶部8は、入力指定部7で指定された入力位置の周期計算部6の出力データ(像)の値OUTPを記憶する。周期累計部9は、周期計算部6で計算した周期Pの累計結果PSを記憶する。
【0026】
周期記憶部10は、順列数設定部11が指定した周期計算部6の周期計算結果PR(PM,M)を記憶する第2の記憶部である。本実施形態では、周期記憶部10は、任意の大きさ(データ数M)mの全ての全単射関数の各々の周期について存在数を記憶する。順列数設定部11は、任意のデータ数mの全ての全単射関数の存在数PMを記憶する。検索位置指定部12は、順列作成部4において作成される任意の順列の値A(i)の既に作成された、それまでの順列の検索位置POSを指定する。
【0027】
上記の構成のうち、制御部2A、データ数記憶部3、順列作成部4、入力指定部7、順列数設定部11、及び検索位置指定部12は、m!個の全単射関数についてのm種類の入出力に対する出力の状態をすべて順列として生成して第1の記憶部である順列記憶部5に記憶する順列生成及び記憶手段を構成する。また、制御部2A、データ数記憶部3、周期計算部6、入力指定部7、出力記憶部8、周期累計部9、及び順列数設定部11は、周期計算及び累計手段と、第2の記憶部である周期記憶部10に判定した周期を記憶する記憶手段とを構成する。
【0028】
ところで、図2に示すように、m個の自然数x(例えば、データの集合X={x|x=natural number,0≦x≦(m-1)})を入力(原像)と出力(像)とする、全ての全単射関数(写像)fの数は、m!存在することが知られている。本発明は、入力データと出力データとが一対一で対応する全単射関数を用いた変換による擬似乱数系列の生成において、図3に示すように、m個の自然数をその関数による変換の写像の原像である入力データ(0〜mー1)と、像となる出力データ(0〜mー1)とし、出力データを更に入力データとして帰還するような帰還系列(擬似乱数系列)について、すべての周期を判定するものである。
【0029】
本発明では、m!個の全単射関数についてのm種類の入力に対する出力の状態を、全て順列として列記することで得る。これは、0〜(m−1)を最初の全単射関数の出力の順列とし、それ以降の全単射関数の出力の並びは、1つ前の順列において、その最後の出力の位置からバックトラックとインクリメンタルサーチの手法を用いて行うことで、次の順列を求めることができる。
【0030】
次に、本発明では、上記の方法で求めた順列(関数)について、最初の入力値(例えば0)から、その入力と同じ出力値(例えば0)となるまで変換を行い、その変換回数を周期として求める。更に、ここで出力値として出現しないものの入力値についても順に同様な変換を行い、その最初の入力値に戻るまでの変換回数を周期として求める。すべての入力値が出現した場合には、全ての周期とその周期の出現回数が求まる。また、任意の一つの全単射関数について上記と同様の手順により全ての周期とその出現回数を求めることが可能である。
【0031】
本発明における上記の全単射関数は、m個の自然数による任意の並びの単なる順列の表、ラテン方陣のような変換表(換字表)、Sボックス、ブロック暗号、帰還型ストリーム暗号に相当し、本発明で周期が判定される整数系列は、ブロック暗号のOFB(Output Feed Back)モードや帰還型ストリーム暗号の出力系列に相当する。
【0032】
ここで、大きさ2(m=2)の全ての全単射関数の入出力データの関係は、下記に示される。
【0033】
f1=[0 1]:0→0,1→1
f2=[1 0]:0→1→0
上記の→の左側の値は入力値、右側の値は出力値を示す(後述する他の例も同様)。従って、1番目の入出力データの関係f1では、0が入力されると0が出力される場合と、1が入力されると1が出力される場合を示しており、周期1が2個である。また、2番目の入出力データの関係f2では、0が入力されると1が出力され、1が入力されると0が出力される場合を示しており、周期2が1個であることを示す。従って、m=2の整数系列の全ての全単射関数は、周期1が2個と周期2(最大周期)が1個を有すると結論することができる。この例は次のような表で表すこともできる。
【0034】
【表1】
同様に、大きさ3(m=3)の全ての全単射関数の入出力データの関係は、下記に示される。
【0035】
f1=[0 1 2]:0→0,1→1,2→2(ゆえに、周期1が3個)
f2=[0 2 1]:0→0,1→2→1(ゆえに、周期1が1個と周期2が1個)
f3=[1 0 2]:0→1→0,2→2(ゆえに周期1が1個と周期2が1個)
f4=[1 2 0]:0→1→2→0(ゆえに周期3が1個)
f5=[2 0 1]:0→2→1→0(ゆえに周期3が1個)
f6=[2 1 0]:0→2→0,1→1(ゆえに周期1が1個と周期2が1個)
よって、m=3の場合では、全ての全単射関数は、周期1が6個と周期2が3個と周期3(最大周期)が2個を有すると結論できる。この例は次のような表で表すこともできる。
【0036】
【表2】
同様に、m個の自然数(整数)からなる整数系列の全ての全単射関数の入出力データの関係は、下記の表3で表すことができる。
【0037】
【表3】
図1に示す第1の実施形態の整数系列の周期判定装置1Aは、入出力データの大きさが任意のmの場合の全ての全単射関数の全ての整数系列の作成とその系列の全周期を判定する装置の例である。まず、本実施形態の動作の概要について説明する。
【0038】
図4は、本実施形態の概要のフローチャートを示す。同図に示すように、整数系列の周期判定装置1Aは、まず1つの全単射関数の出力の順列データを作成する(ステップS151)。続いて、整数系列の周期判定装置1Aは、ステップS151で作成した順列データから、全単射関数の出力から入力への帰還を繰り返すことによる帰還系列の周期について部分周期最大周期の全ての周期(長)を判定する(ステップS152)。
【0039】
図5は、図4のステップS151の順列データ作成動作の詳細を示す。図5に示すように、順列データ作成処理では、最初の関数の順列データを作成し(ステップS201)、続いて、二番目の関数の順列データを最初のデータから作成する(ステップS202)。以下、同様にして、m!番目の関数の順列データをm!−1番目の順列データから作成する(ステップS203)。
【0040】
図6は、図4のステップS152の作成した順列データから周期を判定する動作の詳細を示す。図6に示すように、周期判定処理では、最初の関数の順列データの各周期を累計し、周期記憶部10に加算する(ステップS301)。続いて、二番目の関数の順列データの各周期を累計し、周期記憶部10に加算する(ステップS302)。以下、同様にして、m!番目の関数の順列データの各周期を累計し周期記憶部10に加算する(ステップS303)。
【0041】
次に、本実施形態の整数系列の周期判定装置1Aによる動作について、更に詳細に説明する。図7及び図8は、図4で説明した本実施形態の概要動作を更に詳細に説明するフローチャートを示す。図9は、図7中のステップS1で作成する順列(整数系列データ)の作成方法の詳細動作説明用フローチャートを示す。図7のステップS1は、図5のフローチャートで概要動作を説明した処理ステップであり、図7のステップS2以降と図8の各ステップは、図6のフローチャートで概要動作を説明した処理の詳細動作を説明するものである。
【0042】
まず、図1の制御部2Aは、順列作成部4にて作成したm!(ここでは、m=2)個の順列A(0)〜A(m-1)を順列記憶部5に設定する(図7のステップS1)。このステップS1による順列の作成は、出力データの最初の位置として順列作成部4のA(0)から最後の位置A(m-1)に未設定の昇順の自然数(0〜m-1)を重複が発生しないように順に設定してゆく図9のバックトラック技法とインクリメンタルサーチ技法により作成可能である。
【0043】
周期を判定すべき関数の出力データの順列が完成したら、順列作成部4の順列A(0)〜A(m-1)のデータをm!番目の順列記憶部5の順列S(m!,0)〜S(m!,m-1)に設定する。更に、m!個のうちの残りのm!-1個の全ての系列S(m!-1,0)〜S(m!-1,m-1)、・・・、S(1,0)〜S(1,m-1)についても、一つ前の系列データS(m!,0)〜S(m!,m-1)のセットを用いて、その最後の位置m-1のデータからバックトラックすることで新たな次のm!-1番目の系列S(m!-1,0)〜S(m!-1,m-1)を求めることが可能であり、これを順次行うことでm個の系列のデータを各々有する全てのm!組の関数の系列データS(m!,0)〜S(m!,m-1)、・・・、S(1,0)〜S(1,m-1)を作成することが可能である。
【0044】
なお、この順列記憶部5に設定した判定用の順列は事前にm!-1個全てを作成し準備しておくものとしているが、他の方法として一つの周期判定の前に各々順に同様の手法で作成することにより系列データの記憶場所である順列記憶部5に1つだけ事前に設定することで使用する記憶場所として順列記憶部を一つ分のみ重複して使用し記憶部の使用量をm!−1個削減することも可能である。
【0045】
ここでは全単射関数の入出力データの大きさ(サイズ)mが2の場合についての例を説明する。
【0046】
このステップS1による順列(整数系列データ)の作成方法について、図9のフローチャートと共に説明する。まず、制御部2Aは、順列数設定部11に全単射関数の系列の数(順列数)m!(ここでは、m!=2)を設定する(ステップS101)。続いて、制御部2Aは、データ数記憶部3にデータ数m(ここではm=2)を設定し(ステップS102)、更に入力指定部7の値INPをデータの先頭の位置を示すものとして0に初期化した後(ステップS103)、入力指定部7が示す位置の順列作成部4の順列データの値A(INP)を0に設定する(ステップS104)。これにより、最初の設定位置の順列データはA(INP)=A(0)=0となる。
【0047】
次に、制御部2Aは、入力指定部7の値INPがデータの先頭の設定位置である0かどうかを判断し(ステップS105)、先頭の設定位置0であればステップS106へ進み、先頭の位置0でなければデータの重複有無のチェックのためステップS108へ進む。ここでは、入力指定部7の値INPがステップS103により先頭の設定位置0とされているので、ステップS106に進み、入力指定部7の値INPが最後の設定位置m−1(=1)かどうかを判断する。ここでは、入力指定部7の値INPが先頭の設定位置0であり最後の設定位置m−1(=1)ではないので、入力指定部7の値INPを次のデータの設定位置として1だけ加算した後(ステップS107)、順列作成部4の値A(INP)(ここでは、A(1))に設定データとして0を設定する(ステップS104)。これにより、A(INP)=A(1)=0となる。
【0048】
次に、制御部2Aは、入力指定部7の値INPが先頭のデータの位置として0かどうかを判断する(ステップS105)。ここでは、INPはステップS107により1とされており、先頭の位置0ではないのでステップS108へ進み、検索位置指定部12が示す検索位置POSを0に初期化する。続いて、制御部2Aは、入力指定部7が示す順列作成部4の値A(INP)が、検索位置指定部12が示す順列作成部4の値A(POS)と等しいかどうかを判定する(ステップS109)。ここでは、設定されているデータの値A(INP)がA(1)=0であり、検索位置のデータA(POS)がA(0)であり、A(0)は最初のステップS104の処理で0とされているため、両者は等しく、重複していると判定される(ステップS109のYes)。
【0049】
制御部2Aは、これにより、入力指定部7が示す順列作成部4の値A(INP)がデータの最大の設定値m−1と等しいかどうか判定する(ステップS115)。この時点では、A(INP)=A(1)=0であり、1(=mー1)と等しくないため、入力指定部7が示す順列作成部4の値A(INP)を1だけ加算して(ステップS119)、ステップS105に戻る。これにより、A(1)=1となる。
【0050】
続いて、制御部2Aは、入力指定部7の値INPが先頭の設定位置0であるかどうかを判定し(ステップS105)、ここでは先頭の設定位置0ではないので、ステップS108に進んで検索位置指定部12が示す検索位置POSを先頭の設定位置0に初期化した後、再び入力指定部7が示す順列作成部4の値A(INP)が、検索位置指定部12が示す順列作成部4の値A(POS)と等しいかどうかを判定する(ステップS109)。この時点では、A(INP)がA(1)=1であり、A(POS)がA(0)=0であるため、両者は等しくないと判定される(ステップS109のNo)。
【0051】
これにより、制御部2Aは、検索位置指定部12の検索位置の値POSを1だけ加算した後(ステップS110)、検索位置指定部12の値POSと入力指定部7の値INPとが等しいかどうかを判定する(ステップS111)。ステップS111の判定の結果、上記のPOSとINPとが等しいときには、全てのデータに重複が無いということになり、ステップS106に進み、等しくないときにはステップS109に進む。この時点では、上記のPOSとINPとは共に1であるので、両者は等しいと判定される。これにより、制御部2AはステップS106に進み、入力指定部7の値INPがデータの最後の設定位置1(=m−1)かどうかを判定する。
【0052】
ステップS106では、等しいと判定されるため、一つの関数のデータの作成が完了したことになり、続いて制御部2Aは順列数設定部11のPM(これはステップS101で設定されたm!=2である)の示す順列記憶部5の順列S(PM,0)〜S(PM,m-1)、すなわちS(2,0)、S(2,1)に、作成済みの関数のデータが設定された順列作成部4の値A(0)〜A(m-1)、すなわち、1番目の関数データの順列の値としてA(0)=0、A(1)=1を設定する(ステップS112)。
【0053】
続いて、制御部2Aは、順列数設定部11の示す値PMが最後の関数の数列の設定数の1かどうかを判定するが、1であれば全ての関数のデータm!−1個を作成済みとなり、もし1で無ければさらに残りの関数のデータの作成を行う(ステップS113)。この時点では、順列数設定部11の示す値PMは2であり、最後の関数データの値1ではないので、順列数設定部11の示す値PMを1だけ減算し次の関数データの設定位置を示すようにした後(ステップS114)、入力指定部7が示す順列作成部4の値A(INP)がデータの最大の設定値m−1であるかどうかを判定する(ステップS115)。
【0054】
この時点では、入力指定部7が示す順列作成部4の値A(INP)がA(1)=1であり、最大の値m−1に等しいので、続いて入力指定部7の値INPを1だけ減算し順列作成部の設定位置を戻した後(ステップS116)、入力指定部7の値INPはデータの先頭の設定位置0かどうか判定する(ステップS117)。この時点では入力指定部7の値INPは0で先頭であるので、制御部2Aは続いて入力指定部7の示す順列作成部4の値A(INP)、すなわちA(0)が最大の値m−1であるかどうかを判定する(ステップS118)。この時点では、A(0)は0であり、最大の値m−1(=1)に等しくないので、制御部2Aは入力指定部7の示す順列作成部4の値である関数の設定データA(INP)を次の順序の値として1だけ加算して(ステップS119)、ステップS105に戻る。これにより、関数データの設定値A(0)は1とされる。
【0055】
制御部2Aは、ステップS105において、入力指定部7の値INPが先頭のデータの設定位置0であると判定し、続いてステップS106において入力指定部7の値INPがデータの最大の設定値1(=m−1)と等しくないと判定し、ステップS107において入力指定部7のデータの設定位置の値INPを1だけ加算して次の設定データの位置の値として1とした後、ステップS104に戻り、入力指定部7の示す順列作成部4の関数データの設定値A(INP)を0に設定する。これにより、2番目の設定データA(INT)=A(1)=0となる。
【0056】
続いて、制御部2Aは、入力指定部7のデータの設定位置の値INPが先頭の位置0かどうかを判定し(ステップS105)、この時点ではINPは1であり、先頭の位置の値0ではないので、検索位置指定部12の検索位置の値POSを0に設定し(ステップS108)、入力指定部7が示す順列作成部4の値A(INP)が、検索位置指定部12が示す順列作成部4の値A(POS)と等しいかどうかを判定する(ステップS109)。ここでは、設定されたデータA(INP)がA(1)=0であり、検索位置のデータはA(POS)=A(0)=1であり、両者は等しくないため、ステップS110へ進んで検索位置指定部12の検索位置の値POSを次の値1にした後、ステップS111において検索位置の値POSが入力指定部7の値INPと等しいかどうかを判定する。この時点では、POS=INP=1であるので、ステップS106に進んで入力指定部7のデータ設定位置の値INPが1(=m−1)と等しいかどうかを判定する。この時点では、データの設定位置INP=1で最後の位置であるので、ステップS112に進んで順列記憶部5の順列S(PM,0)〜S(PM,m-1)、すなわち2番目の関数データの順列の値としてS(1,0)、S(1,1)に、順列作成部4の設定データの値A(0)=1、A(1)=0を設定する。
【0057】
そして、制御部2Aは順列数設定部11の値PMが最後の関数の数列の設定数の1であるかどうかを判定する(ステップS113)。この時点では順列数設定部11の値PMが最後の関数の設定数1であるので、制御部2Aは全数列を作成したことになるので、処理を終了する。
【0058】
このようにして、順列記憶部5の順列S(PM,0)〜S(PM,m-1)、すなわちS(2,0)、S(2,1)、S(1,0)、S(1,1)に、順列作成部4の値(順列)が記憶される。
【0059】
再び図7及び図8に戻って説明する。上記のステップS1の処理後、制御部2Aは、順列数設定部11に任意のデータ数mの全ての全単射関数の存在数(出力系列の数)PMとしてm!(=2)を設定した後(図7のステップS2)、データ数記憶部3に入出力データ(原像及び像)の数M(=m=2)を設定する(図7のステップS3)。
【0060】
続いて、制御部2Aは、周期記憶部10の各周期の個数を設定するPR(1,1)〜PR(m!,m)に各系列(1からm!)の各周期(1からm)の初期値として0を設定した後(図7のステップS4)、順列記憶部5に記憶され、順列数設定部11が示す全単射関数の1番目(PM=2)の系列データである順列S(2,0)〜S(2,m-1)の値(S(2,0)=0、S(2,1)=1)を周期計算部6にm個(m=2)の周期の計算用データP(0)〜P(m-1)として各々設定する(P(0)=0、P(1)=1)(図7のステップS5)。
【0061】
続いて、制御部2Aは、周期累計部9の値PSを0に設定した後(図7のステップS6)、最初の入力データに相当する先頭の位置(先頭のデータとして0)を入力指定部7の値INPに設定する(INP=0)(図7のステップS7)。次に、制御部2Aは、入力指定部7の値INPが示す、周期計算部6の周期の配列P(1)〜P(m)の位置の入力データ(データは0)に対応する出力データP(INP)(データは0)を出力記憶部8の値OUTPとして設定する(図7のステップS8)。
【0062】
続いて、制御部2Aは、出力記憶部8の出力データの値OUTPが既に系列に使用済みかどうかを判定する(図7のステップS9)。使用済みの場合は、使用済みのマークとして−1の値となっている。使用済みであれば図7のステップS10に進み、使用済みでなければ図8のステップS15に進む。この時点では、OUTPは0であり、−1(使用済み)ではないので、制御部2AはステップS15に進み、入力指定部7が示す値INP(ここでは0)の位置の周期計算部6の値P(INP)を、使用済みのマークとして−1に更新し、系列に使用済みであることを示す。
【0063】
続いて、制御部2Aは、出力記憶部8の出力データの値OUTP(ここでは0)を入力指定部7の値INPに設定する(図8のステップS16)。続いて、制御部2Aは、周期累計部9の値PSに1を加算して周期数を1に更新した後(図8のステップS17)、入力指定部7の値INP(ここでは0)が示す周期計算部6の位置の入力データに対応する出力データの値P(INP)(ここでは−1)を出力記憶部8の値OUTPに設定する(図8のステップS18)。
【0064】
次に、制御部2Aは、出力記憶部8の値OUTPが、既に系列に使用済みであることを示す−1であるかどうかを判定し(図8のステップS19)、使用済み(ー1)であればステップS23に進み、使用済みでなければステップS20に進む。ここでは、使用済みであるので、ステップS23に進み、順列数設定部11の値PMが示す周期記憶部10のm個の値PR(PM,1)〜PR(PM,m)のうち、周期累計部9の値PSに相当する位置PR(PM,PS)の周期の値に1を加算し(ここでは、周期1の位置に1を加算するPR(2,1)=PR(2,1)+1)、周期数を更新した後、次の周期の計算のために図7のステップS6に進む。
【0065】
ステップS6において、制御部2Aは、周期累計部9の値PSを0にクリアする。その後、制御部2Aは、最初の入力データに相当する先頭の位置(先頭のデータとして0)を入力指定部7の値INPに設定する(図7のステップS5)。続いて、制御部2Aは、入力指定部7の値INP(ここでは0)が示す周期計算部6の位置の入力データに対応する出力データの値P(INP)(ここでは−1)を出力記憶部8の値OUTPに設定する(図7のステップS8)。
【0066】
次に、制御部2Aは、出力記憶部8の値OUTPが、既に系列に使用済みであることを示す−1であるかどうかを判定し(図7のステップS9)、使用済み(ー1)であれば図7のステップS10に進み、使用済みでなければ図8のステップS15に進む。この時点では、使用済みであるので、制御部2AはステップS10に進み、入力指定部7の値INPが系列の最後の位置を示す値(m-1)かどうかを判定する。この時点では、上記の値INPは0であり、最後の位置1(=m-1)ではないので、値INPを1に更新した後(図7のステップS11)、ステップS8に戻り、再び入力指定部7の値INP(ここでは1)が示す周期計算部6の位置の入力データに対応する出力データの値P(INP)(ここでは1)を出力記憶部8の値OUTPに設定する。
【0067】
続いて、制御部2Aは、ステップS9において、出力記憶部8の値OUTPが、既に系列に使用済みであるかどうかを判定する。ここでは、出力記憶部8の値OUTPは1であり、−1ではないので、制御部2Aは図8のステップS15に進み、出力記憶部8の値OUTPが示す位置(ここでは1)の周期計算部6のデータの値P(INP)を使用済みのマークとして−1に更新し、系列に使用済みであることを記す。続いて、制御部2Aは、出力記憶部8の値OUTP(ここでは1)を入力指定部7の値INPに設定した後(ステップS16)、周期累計部9の値PSに1を加算して周期数を更新する(ステップS17)。これにより、周期数は1となる。続いて、制御部2Aは、入力指定部7の値INP(ここでは1)が示す周期計算部6の位置の入力データに対応する出力データの値P(INP)(ここでは−1)を出力記憶部8の値OUTPに設定する(ステップS18)。
【0068】
続いて、制御部2Aは、出力記憶部8の値OUTPが−1かどうかを判定する(ステップS19)。この時点では、上記のステップS18により上記の値OUTPは−1とされているので、制御部2AはステップS19において−1である(使用済みである)と判定し、続いてステップS23において順列数設定部11の値PMが示す周期記憶部10のm個の値PR(PM,1)〜PR(PM,m)のうち、周期累計部9の値PSに相当する位置PR(PM,PS)の周期の値に1を加算し(ここでは、周期1の位置に1を加算し周期1が2個となるPR(2,1)=PR(2,1)+1)、周期数を更新し図7のステップS6に進む。
【0069】
続いて、制御部2Aは、ステップS6で周期累計部9の値PSを0にクリアし、ステップS7で先頭の位置(先頭のデータとして0)を入力指定部7の値INPに設定し、ステップS8で入力指定部7の値INPが示す、周期計算部6の位置の入力データに対応する出力データP(INP)(ここでは−1)を出力記憶部8の値OUTPとして設定する。
【0070】
続いて、制御部2Aは、ステップS9において、出力記憶部8の値OUTPは−1であるかどうかを判定する。この時点では、値OUTPは−1であるので、制御部2AはステップS9において−1である(使用済みである)と判定し、次にステップS10に進んで入力指定部7の値INPが系列の最終の位置を示す値1(=m-1)であるかどうかを判定する。この時点では、入力指定部7の値INPは先頭の位置0であり、最後の位置1ではないので、制御部2Aは次にステップS11に進んで入力指定部7の値INPに1を加算して次の位置としステップS8に進む。これにより、上記の値INPは1となる。
【0071】
続いて、制御部2Aは、ステップS8において入力指定部7の値INPが示す、周期計算部6の位置の入力データに対応する出力データP(INP)(ここでは−1)を出力記憶部8の値OUTPとして設定した後、ステップS9において、出力記憶部8の値OUTPは−1であるかどうかを判定する。この時点では、値OUTPは−1であるので、制御部2AはステップS9において−1である(使用済みである)と判定し、次にステップS10に進んで入力指定部7の値INPが系列の最後の位置を示す値1(=m-1)であるかどうかを判定する。
【0072】
この時点では、入力指定部7の値INPは1であり、系列の最後の位置を示す値1と等しいので一つの関数に存在する全ての周期が求められたこととなり、制御部2Aは次にステップS12に進んで順列数設定部11の値PMが最後の関数に相当する値1であるかどうかを判定する。この時点では、順列数設定部11の値PMはステップS2で設定された2(=m!)であり、1ではないので、制御部2Aは順列数設定部11の値PMを1減算して1とした後(図7のステップS13)、ステップS5に戻り、再び順列数設定部11の値PMの示す順列記憶部5に記憶されている全単射関数の全ての系列データである順列S(PM,0)〜S(PM,m-1)に設定されたm個のデータ(ここでは、PM=1であるので、前述したように2番目の関数の2個のデータS(1,0)=1,S(1,1)=0)を、周期計算部6の周期の計算用データP(0)〜P(m-1)、すなわちP(0)=1、P(1)=0として各々設定する。
【0073】
制御部2Aは続いてステップS6で周期累計部9の値PSを0にクリアし、ステップS7で先頭の位置(先頭のデータとして0)を入力指定部7の値INPに設定した後、ステップS8へ進み、ここで入力指定部7の値INPが示す周期計算部6の位置の入力データに対応する出力データP(INP)(ここでは1)を出力記憶部8の値OUTPに設定する。続いて、制御部2AはステップS9に進んで値OUTPが−1(使用済み)ではないと判定した後、図8のステップS15へ進んで入力指定部7が示す値INPの位置の周期計算部6の値P(INP)を、使用済みのマークとして−1に更新し、系列に使用済みであることを示す。
【0074】
続いて、制御部2Aは、ステップS16で出力記憶部8の出力データの値OUTP(ここでは1)を入力指定部7の値INPに設定し、次のステップS17で周期累計部9の値PSに1を加算して周期数を1に更新し(周期数は1となる)、次のステップS18で入力指定部7の値INP(ここでは1)が示す、周期計算部6の位置の入力データに対応する出力データP(INP)(ここでは0)を出力記憶部8の値OUTPに設定する。
【0075】
次に、制御部2Aは、出力記憶部8の値OUTPが、既に系列に使用済みであることを示す−1であるかどうかを判定し、使用済み(ー1)であればステップS23に進み、使用済みでなければステップS20に進む。ここでは、OUTPは0であり−1ではない(使用済みでない)ので、ステップS20に進み、入力指定部7の値INP(ここでは1)が示す位置の周期計算部6の出力データの値P(INP)である0を入力指定部7の値INPに設定する。
【0076】
続いて、制御部2Aは、入力指定部7の値INP(ここでは0)が示す位置の周期計算部6の出力データの値P(0)を、−1に更新して系列に使用済みであることを記した後(図8のステップS21)、周期累計部9の値PSを1加算し周期数を更新し、ステップS18に進む。これにより、周期の値PSは2となる。
【0077】
ステップS18では入力指定部7の値INPが示す、周期計算部6の位置P(INP)の入力データに対応する出力データの値(INP=0でP(INP)は−1)を出力記憶部8の値OUTPに設定する。続いて、制御部2Aは、ステップS19において出力記憶部8の値OUTPが−1であるかどうかを判定する。ここでは、出力記憶部8の値OUTPが−1であるので、ステップS23に進み、順列数設定部11の値PMが示す周期記憶部10のm個の周期の値PR(PM,1)〜PR(PM,m)のうち、周期累計部9の値PSに相当する値PR(PM,PS)に1を加算し(ここでは、周期2の位置に1を加算しPR(1,2)=1となり、周期2が1個となる)、周期数を更新した後、図7のステップS5に進む。
【0078】
続いて、制御部2Aは、再び前述したステップS6、S7を経てステップS8へ進み、ここで入力指定部7の値INPが示す周期計算部6の値P(INP)の位置の入力データ(ここでは0)に対応する出力データ(ここでは−1)を出力記憶部8の値OUTPに設定する。続いて、制御部2AはステップS9に進んで出力記憶部8の値OUTPが−1であり、使用済みであると判定した後、ステップS10に進んで入力指定部7の値INPが0であり、系列の最終の位置1(=m−1)ではないと判定するので、ステップS11に進んで入力指定部7の値INPを1加算してINPを1とする。
【0079】
続いて、制御部2Aは、ステップS8において入力指定部7の値INP(ここでは1)が示す周期計算部6の値P(INP)の位置の入力データ(ここでは1)に対応する出力データ(ここでは−1)を出力記憶部8の値OUTPに設定した後、ステップS9に進んで出力記憶部8の値OUTPが−1であり、使用済みであると判定した後、ステップS10に進んで入力指定部7の値INPが1であり、系列の最後の位置1(=m−1)であると判定する。
【0080】
これにより、制御部2Aは、順列数設定部11が示す値PMがデータの最後の位置の1かどうかを判定する(図8のステップS12)。この時点では、前述したステップS13の処理によりPMは1となっているので、ステップS12でPMが1であると判定され、全ての系列の処理が行われたと判断して処理を終了する(図8のステップS14)。全ての処理を終了した場合には、周期記憶部10には、この全単射関数の各々の系列の各周期長の全ての存在数が求まっている。ここでは、m=2であり、周期記憶部10には、周期1が2個、周期2が1個を示す値が記憶されている。
【0081】
このように、本実施形態によれば、図10に示すような関数の帰還により周期を求めることができる。図10において、m!個の全単射関数の作成した順列データのそれぞれについて、各全単射関数の0からm−1までのm個の入力データのうちの最小のものである0の値を最初の入力データとし、その出力データを更に入力データとして帰還し、入力データが最初の入力データである0に戻るまでの帰還回数を求めて系列周期とする。このとき出現した出力データには出現済みと判断できるように−1等の出力データに存在しない値を周期計算部6に設定することで、未出現の出力データと区別する。
【0082】
もし、m個の全てのデータが系列に出現した場合には最大周期となり、完全擬似乱数の系列が作成されたことになる。しかし、未出現の出力データが残存する場合には、周期は部分的な系列のものであり、未出現の残りのデータに更に部分的な別の周期が存在することになる。未出現の出力データが残存する場合には、更に未出現の出力データのうちの入力データの最小のものを新たな周期の最初の入力データとし、その入力データに戻るまでの新たな系列周期を求め、全ての出力データが系列に出現し尽すまでこの手順を繰り返す。そして、m!個の全ての順列データ(関数)について、この手順でそれぞれの周期数とその各周期の存在数を求める。
【0083】
このようにして、本実施形態によれば、全ての全単射関数の全ての整数系列の全周期を判定することができる。そして、任意の周期の全単射関数を用いた擬似乱数系列や変換表などを作成することができる。
【0084】
(第2の実施形態)
図11は、本発明になる整数系列の周期判定装置の第2の実施形態のブロック図を示す。同図に示すように、本実施形態の整数系列の周期判定装置1Bは、装置1B全体を統括的に制御する制御部2B、データ数記憶部3、順列作成部4、順列記憶部5、周期計算部6、入力指定部7、出力記憶部8、周期累計部9、周期記憶部10から構成されており、第1の実施形態の整数系列の周期判定装置1Aと比較すると、順列数設定部11と検索位置指定部12を有しない。
【0085】
制御部2B、順列作成部4及び周期計算部6は、例えば中央処理装置(CPU)により構成される。また、データ数記憶部3、出力記憶部8、周期累計部9及び周期記憶部10は記憶装置により構成され、入力指定部7は所定の入力装置により構成される。
【0086】
データ数記憶部3は、単射で、かつ、全射でもある関数である全単射関数の有する連続した自然数の入出力データ(原像及び像)の数Mを記憶する。順列作成部4は、周期を判定するために予め事前に用意されたデータである、全単射関数の入力に対する出力データ(原像に対する像)の並びである順列A(i)を設定する。この場合、順列A(i)は、出力データの値に重複せず、全ての値が出現するように作成されたものとする。順列記憶部5は、任意のデータ数mの全単射関数の入力に対する出力データ(原像に対する像)の並びである順列S(j)を予め記憶している第1の記憶部である。周期計算部6は、後述するように任意の全単射関数の入力に対する出力データ(原像に対する像)を更に入力とする手順を繰り返し行って、判定する整数系列の周期Pを計算する。
【0087】
入力指定部7は、入力位置(原像の位置)INPを指定する。出力記憶部8は、入力指定部7で指定された入力位置の周期計算部6の出力データ(像)の値OUTPを記憶する。周期累計部9は、周期計算部6で計算した周期Pの累積結果PSを記憶する。周期記憶部10は、周期計算部6の周期計算結果PR(PM,M)を記憶する第2の記憶部である。本実施形態では、周期記憶部10は、任意のデータ数m(ここでは、m=3とする)の全単射関数の部分周期を含めた全ての周期について存在数を記憶する。
【0088】
上記の構成のうち、制御部2B、データ数記憶部3、順列作成部4、周期計算部6、入力指定部7、及び周期累計部9は、m!個の全単射関数のうち、所望の1個の全単射関数のm個の整数からなる整数系列の入力に対する出力の状態を順列として生成して第1の記憶部である順列記憶部5に記憶する順列記憶手段を構成する。また、制御部2B、周期計算部6、入力指定部7、出力記憶部8及び周期累計部9は、順列記憶部5に記憶された順列の周期を計算して第2の記憶部である周期記憶部10に記憶する周期計算及び累計手段を構成する。
【0089】
次に、本実施形態の動作について、図12及び図13のフローチャートを併せ参照して説明する。
【0090】
図11において、制御部2Bは、まず、データ数記憶部3にデータ数m(ここでは、m=3)を設定する(図12のステップS31)。続いて、制御部2Bは、周期記憶部10に記憶されている周期PR(0)〜PR(m-1)の各値を0に設定した後(図12のステップS32)、順列作成部4に全単射関数の入出力データとして、入力データ(0からm−1までの自然数)に対応する出力系列データA(0)〜A(m-1)を設定する(図12のステップS33)。具体的には、この出力系列データA(0)〜A(m-1)は、0からm−1までの重複しない自然数の任意の組み合わせのデータで、ここではm=3であるので、例えば、A(0)=2,A(1)=0,A(2)=1の3個のデータである。
【0091】
続いて、制御部2Bは、順列作成部4に設定した上記の3個の出力系列データA(0)〜A(2)を順列記憶部5の順列S(0)〜S(m-1)にそれぞれ格納する(図12のステップS34)。ここでは、上記の順列記憶部5には、S(0)=2,S(1)=0,S(2)=1の3個の順列が格納されることになる。
【0092】
続いて、制御部2Bは、順列記憶部5に格納された順列S(0)〜S(m-1)を、周期計算部6に計算用のデータP(0)〜P(m-1)としてそれぞれ関数の出力データを設定する(図12のステップS35)。ここでは、上記の周期計算部6には、P(0)=2,P(1)=0,P(2)=1の3個が設定されることになる。
【0093】
続いて、制御部2Bは、周期累計部6の周期の値PSを0に設定(クリア)した後(図12のステップS36)、最初の入力データに相当する先頭のデータの位置(例えば0)を入力指定部7の値INPとして設定する(図12のステップS37)。次に、制御部2Bは、入力指定部7の値INPが示す周期計算部6の入力データに対応する出力データの値P(INP)を出力記憶部8の値OUTPに設定する(図12のステップS38)。ここでは、INPは0であるので、入力データはP(0)であり、それに対応する出力データは前述したように2であるから、OUTPは2に設定される。
【0094】
続いて、制御部2Bは、出力記憶部8の値OUTPが既に系列に使用済みかどうかを比較する(図12のステップS39)。使用済みなら使用済みのマークとして−1の値となっている。ここでは、OUTPは2であり、−1ではないので、制御部2Bは使用済みでないと判定し、図13のステップS43に進んで、入力指定部7の値INPが示す周期計算部6の入力データに対応する出力データの値P(INP)を−1に設定し、系列に使用済みであることを示す。これにより、P(0)=−1となる。
【0095】
次に、制御部2Bは、出力記憶部8の値OUTP(ここでは2)を入力指定部7の値INPに設定する(図13のステップS44)。続いて、制御部2Bは、周期累計部9の値PSに1を加算し周期数を更新する(図13のステップS45)。これにより、周期数PSは1となる。続いて、制御部2Bは、入力指定部7の値INP(ここでは2)が示す、周期計算部6の入力データに対応する出力データの値P(INP)を出力記憶部8の値OUTPに設定する(図13のステップS46)。ここでは、INPは2であるから、P(2)に対応する出力データは前述したように1であるから、OUTPは1に設定される。
【0096】
次に、制御部2Bは、出力記憶部8の値OUTPが使用済みであることを示す−1であるかどうかを判定する(図13のステップS47)。ここでは、上記のようにOUTPは1であり、−1ではないので、制御部2Bは、入力指定部7の値INP(ここでは2)が示す、周期計算部6の位置の入力データの値P(INP)に対応する出力データ(ここでは1)を入力指定部7の値INPに設定する(図13のステップS48)。続いて、制御部2Bは、入力指定部7の値INP(ここでは1)が示す、周期計算部6の入力データに対応する出力データの値P(INP)を−1に設定し、系列に使用済みであることを示す(図13のステップS49)。これにより、P(1)=−1となる。
【0097】
次に、制御部2Bは、周期累計部9の周期の値PSに1を加算して2とし、周期数を更新した後(図13のステップS50)、ステップS46に戻り、入力指定部7の値INP(ここでは1)が示す、周期計算部6の位置の入力データに対応する出力データの値P(INP)を出力記憶部8の値OUTPに設定する。ここでは、INPは1であるから、P(1)に対応する出力データは−1であるから、OUTPは−1に設定される。
【0098】
次に、制御部2Bは、出力記憶部8の値OUTPが使用済みであることを示す−1であるかどうかを判定する(図13のステップS47)。ここでは、上記のようにOUTPは−1であるから、制御部2Bは使用済みと判断し、周期累計部9の示す値PS(ここでは2)に相当する、周期記憶部10の位置の周期の値PR(PS)に1を加算して、周期数を更新した後(図13のステップS51)、図12のステップS36に進む。これにより、PR(2)は1になる。つまり、周期2の周期数が1個と判定される。
【0099】
続いて、制御部2BはステップS36において、周期累計部6の値PSを0に設定(クリア)した後、最初の入力データに相当する先頭の位置(例えば0)を入力指定部7の値INPとして設定し(ステップS37)、更に、入力指定部7の値INPが示す周期計算部6の位置の入力データに対応する出力データP(INP)を出力記憶部8の値OUTPに設定する(ステップS38)。ここでは、INPは0であるので、入力データはP(0)であり、それに対応する出力データは前述したように−1であるから、OUTPは−1に設定される。
【0100】
続いて、制御部2Bは、ステップS39において、出力記憶部8の値OUTPが−1であり、既に系列に使用済みであると判定してステップS40に進む。ステップS40では、制御部2Bは、入力指定部7の値INPが系列の最後の位置(m-1)を示す2であるかどうかを判定する。ここでは、INPは0であり2ではないので、制御部2Bは入力指定部7の値INPを1加算して1とした後(図12のステップS42)、ステップS38に進み入力指定部7の値INPが示す周期計算部6の位置の入力データに対応する出力データP(INP)を出力記憶部8の値OUTPに設定する。ここでは、INPは1であるので、入力データはP(1)であり、それに対応する出力データは前述したように1であるので、OUTPは1に設定される。
【0101】
続いて、制御部2Bは出力記憶部8の値OUTPが使用済みであることを示す−1であるかどうか判定する(ステップS39)。ここでは、OUTPは1であり、−1ではないので、制御部2Bは使用済みでないと判定し、図13のステップS43に進んで、入力指定部7の値INPが示す周期計算部6の位置の入力データの値に対応する出力データP(INP)を−1に設定し、系列に使用済みであることを示す。これにより、P(1)=−1となる。
【0102】
以後、制御部2Bは、前述したステップS44、S45、S46の各処理を行った後、ステップS47で出力記憶部8の値OUTPが使用済みであることを示す−1であると判定し、ステップS51に進んで周期累計部9の示す値PS(ここでは1)に相当する、周期記憶部10の位置の周期の値PR(PS)に1を加算して、周期数を更新する。これにより、PR(1)は1になる。つまり、周期1の周期数が1と判定される。
【0103】
その後、制御部2Bは、前述したステップS36、S37、S38の各処理を行った後、ステップS39で出力記憶部8の値OUTPが使用済みであることを示す−1であると判定し、ステップS40に進んで入力指定部7の値INPが系列の最後の位置(m-1)を示す2であるかどうかを判定する。ここでは、INPは0であり2ではないので、制御部2Bは入力指定部7の値INPを1加算して1とした後(ステップS42)、ステップS38に進み入力指定部7の値INPが示す周期計算部6の位置の入力データP(INP)に対応する出力データを出力記憶部8の値OUTPに設定する。ここでは、INPは1であるので、入力データはP(1)であり、それに対応する出力データは前述したように−1であるので、OUTPは−1に設定される。
【0104】
続いて、制御部2Bは、ステップS39において、出力記憶部8の値OUTPが−1であり、既に系列に使用済みであると判定してステップS40に進む。ステップS40では、制御部2Bは、入力指定部7の値INPが系列の最後の位置(m-1)を示す2であるかどうかを判定する。ここでは、INPは1であり2ではないので、制御部2Bは入力指定部7の値INPを1加算して2とした後(ステップS42)、ステップS38に進み入力指定部7の値INPが示す周期計算部6の位置の入力データに対応する出力データP(INP)を出力記憶部8の値OUTPに設定する。ここでは、INPは2であるので、入力データはP(2)であり、それに対応する出力データは前述したように−1であるので、OUTPは−1に設定される。
【0105】
続いて、制御部2Bは、ステップS39において、出力記憶部8の値OUTPが−1であり、既に系列に使用済みであると判定してステップS40に進む。ステップS40では、制御部2Bは、入力指定部7の値INPが系列の最後の位置(m-1)を示す2であるかどうかを判定する。ここでは、INPは2であるので、制御部2Bは入力指定部7の値INPが系列の最後の位置に達し、全ての入出力データの処理を行ったと判断して、全ての処理を終了する(図12のステップS41)。このようにして、周期記憶部10に格納されている周期PR(1)〜PR(3)には、この関数の各周期長の全ての存在数が設定された状態となる。本実施形態では、m=3の場合であり、上記のようにこの全単射関数の有する各周期数として周期数1を示すPR(1)が1個と、周期数2を示すPR(2)が1個と求まる。
【0106】
このようにして、本実施形態によれば、任意の入出力データ数の全単射関数の任意のデータ系列についての部分周期を含めた全ての周期を求めることができる。
【0107】
(第3の実施形態)
次に、本発明になる整数系列の周期判定装置の第3の実施形態について説明する。本実施形態の周期判定装置のハードウェア構成は、図11に示した整数系列の周期判定装置1Bと同じ構成であるが、制御部2Bによるソフトウェア動作が以下説明するように第2の実施形態と異なる。
【0108】
本実施形態は、大きさ3(m=3)の自然数からなる全単射関数が与えられた場合、その全単射関数が最大周期3(=m)を有するかの確認方法として、或る初期値(例えば0)を入力値として全単射関数に与えて、その出力(例えば0)が初期値に戻るまで全単射関数の変換を繰り返し、その繰り返しの回数である周期が3(=m)となった場合には、全ての入出力値を網羅し、最大周期であると判定し、変換の繰り返し回数が3(=m)より小さかった場合には最大周期ではないと判断する。
【0109】
次に、本実施形態のハードウェア資源を利用したソフトウェア動作について、図14のフローチャートと共に説明する。前述したように、m=3の場合の最大周期は3である。本実施形態は、例えば、前記f5のように入力0のとき出力2、入力1のとき出力0、入力2のとき出力1のデータが最大周期3となるかどうかの判定を行う。
【0110】
図11において、制御部2Bは、まず、データ数記憶部3にデータ数m(ここでは、m=3)を設定する(図14のステップS61)。続いて、制御部2Bは、周期累計部9の値PSを0に設定(クリア)した後(ステップS62)、順列作成部4に全単射関数の入出力データとして、入力データ(0からm−1までの自然数)に対応する出力系列データA(0)〜A(m-1)を設定する(ステップS63)。具体的には、この出力系列データA(0)〜A(m-1)は、0からm−1までの重複しない自然数の任意の組み合わせのデータで、ここではm=3であるので、例えば、A(0)=2,A(1)=0,A(2)=1の3個のデータである。ここで、A(0)=2は、入力0のとき出力2、A(1)=0は入力1のとき出力0、A(2)=1は入力2のとき出力1を示す。
【0111】
続いて、制御部2Bは、順列作成部4に設定した上記の3個の出力系列データA(0)〜A(2)を順列記憶部5の順列S(0)〜S(m-1)にそれぞれ格納する(ステップS64)。ここでは、上記の順列記憶部5には、S(0)=2,S(1)=0,S(2)=1の3個の順列が格納されることになる。これら3個の順列は、所望の1個の全単射関数の3つの入力値に対する出力の状態を記述したものである。
【0112】
続いて、制御部2Bは、順列記憶部5に格納された順列S(0)〜S(m-1)を、周期計算部6に周期P(0)〜P(m-1)としてそれぞれ設定する(ステップS65)。ここでは、上記の周期計算部6には、P(0)=2,P(1)=0,P(2)=1の3個の周期が設定されることになる。ここで、P(0)=2は、入力0のとき出力2の周期、P(1)=0は入力1のとき出力0の周期、P(2)=1は入力2のとき出力1の周期を示す。
【0113】
続いて、制御部2Bは、最初の入力データに相当する先頭の位置(この場合、入力位置0)を示す値を入力指定部7の値INPに設定する(ステップS66)。これにより、INPは0となる。続いて、制御部2Bは、入力指定部7の値INP(ここでは0)が示す、周期計算部6の位置の入力データに対応する、出力データP(INP)を出力記憶部8の値OUTPに設定する(ステップS67)。ここでは、INPは0であるので、入力データは0であり、それに対応する出力データP(0)は前述したように2であるから、OUTPは2に設定される。
【0114】
続いて、制御部2Bは、出力記憶部8の値OUTP(ここでは2)を入力指定部7の値INPに設定した後(ステップS68)、周期累計部9の周期の値PSに1を加算して周期数を更新する(ステップS69)。これにより、INPは2、PSは1となる。
【0115】
次に、制御部2Bは、出力記憶部8の値OUTP(ここでは2)が最初の入力データの値0であるかどうかを判定する(ステップS70)。OUTPの値が最初の入力データの値と等しければステップS71に進み、等しくなければステップS67に戻る。この時点では、OUTPは2であり、0ではないので制御部2BはステップS67に戻り、入力指定部7の値INP(ここでは2)が示す、周期計算部6の位置の入力データに対応する、出力データP(INP)を出力記憶部8の値OUTPに設定する。ここでは、入力データINPは2であるので、それに対応する出力データは前述したように1であるから、OUTPは1に設定される。
【0116】
続いて、制御部2Bは、出力記憶部8の値OUTP(ここでは1)を入力指定部7の値INPに設定した後(ステップS68)、周期累計部9の値PSに1を加算して周期数を更新する(ステップS69)。これにより、INPは1、PSは2となる。
【0117】
次に、制御部2Bは、出力記憶部8の値OUTP(ここでは1)が最初の入力データの値0であるかどうかを再び判定する(ステップS70)。この時点では、OUTPは1であり、0ではないので制御部2BはステップS67に戻り、再び入力指定部7の値INP(ここでは1)が示す、周期計算部6の位置の入力データINPに対応する、出力データP(INP)を出力記憶部8の値OUTPに設定する。ここでは、INPは1であるので、入力データに対応する出力データP(1)は前述したように0であるから、OUTPは0に設定される。
【0118】
続いて、制御部2Bは、出力記憶部8の値OUTP(ここでは0)を入力指定部7の値INPに設定した後(ステップS68)、周期累計部9の値PSに1を加算して周期数を更新する(ステップS69)。これにより、INPは0、PSは3となる。
【0119】
次に、制御部2Bは、出力記憶部8の値OUTP(ここでは0)が最初の入力データの値0であるかどうかを再び判定する(ステップS70)。この時点でOUTPが0であり、最初の入力値であると判定される。続いて、制御部2Bは周期累計部9の周期の値PSは系列長mであるかどうかを判定する(ステップS71)。この時点では、累計計算部9の値PSは系列長m(=3)に等しいので、制御部2Bは最大長(最大周期)であると判定する(ステップS72)。すなわち、m=3の場合、入力0のとき出力2、入力1のとき出力0、入力2のとき出力1のデータが最大周期であると判定され、その周期長PSは3と求められる。
【0120】
なお、ステップS71において、周期累計部9の値PSが系列長mでないと判定されたときは、そのときの入力データは最大長ではないと判定される(ステップS73)。
【0121】
このようにして、本実施形態によれば、任意の入出力データの大きさの全単射関数の最大周期長を判定することができる。そして、最大周期となる全単射関数を用いて、擬似乱数系列や変換表などを作成することができる。
【0122】
ところで、以上の実施形態では、データ数(系列長)mが2又は3の場合について説明したが、mが9までの周期長の個数は表4に示される。
【0123】
【表4】
この表4から分るように、入出力データ数(系列長)mを有する全単射関数の平均周期長はm/2となる。これにより、mが2128の場合では、全単射関数の数は2128!個となり、周期長は1が2128!個で、2が2128!/2個、3が2128!/3個で、最大周期となる周期長2128は2128!/2128個存在する。ここで、平均周期長は2128/2となる。
【0124】
また、128ビットブロック暗号の場合について考えると、128ビット鍵の数は2128個であることから、128ビットブロック暗号はm=2128の全単射関数全ての関数2128!個のうちの2128個を鍵で選択して用いているといえる。そして、m=2128の全単射関数の最大周期2128は2128!/2128個存在することから、128ビットブロック暗号の鍵の総数から考慮して、全ての鍵から最大周期となるものは、
2128!/2128×2128/2128!=1
と記述できることから全ての鍵のうちで最大周期となるものの確率は、高々1個である。
【0125】
ただし、ここで述べている最大周期とは128ビットの出力データの組み合わせが各々1回出現することであり、その出力データの任意の1ビットをそれぞれ抽出した場合に、その系列としてM系列のような最大長のビット系列が必ず得られるものではなく、そのためには最大周期となる系列から更に選択が必要である。
【0126】
なお、以上の実施形態で判定した最大周期を持つ全単射関数の整数系列を2種類以上組み合わせて用いることで、更に長い周期の擬似乱数系列を生成することもできる。例えば、m1とm2の2つの周期の異なる最大長系列において、1以外の約数を持たない互いに素となる周期の組み合わせとなるものを組み合わせれば、最大周期はm1×m2となる。
【0127】
なお、本発明は以上の実施形態に限定されるものではなく、例えば、図7、図8、図9と共に説明した第1の実施形態の各ステップの処理や、図12及び図13と共に説明した第2の実施形態の各ステップの処理や、図14と共に説明した第3の実施形態の各ステップの処理をコンピュータによるソフトウェア処理により実行させる整数系列の周期判定プログラムも本発明は包含するものである。この整数系列の周期判定プログラムは、図1の制御部2Aや図11の制御部2Bにより実行される。
【符号の説明】
【0128】
1A、1B 整数系列の周期判定装置
2A、2B 制御部
3 データ数記憶部
4 順列作成部
5 順列記憶部
6 周期計算部
7 入力指定部
8 出力記憶部
9 周期累計部
10 周期記憶部
11 順列数設定部
12 検索位置指定部
【特許請求の範囲】
【請求項1】
制御部が、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数(写像)についての前記m種類の入力に対する出力の状態のデータを全て順列として作成して第1の記憶部に記憶する第1のステップと、
前記制御部が、前記第1の記憶部に記憶された前記m!個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、前記周期が前記mより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての前記入力値及び全ての前記未出現の入力値に対して順次行う第2のステップと、
前記制御部が、前記第2のステップで求められた前記m!個の全単射関数の最小周期から最大周期までの前記周期を第2の記憶部に記憶する第3のステップと
を含むことを特徴とする整数系列の周期判定方法。
【請求項2】
前記第1のステップは、
前記m!個の全単射関数(写像)のうち、最初の全単射関数の順列データのデータを作成した後、2番目からm!番目までの全単射関数の順列データは、それぞれその1つ前の順番の全単射関数の順列データから作成することを特徴とする請求項1記載の整数系列の周期判定方法。
【請求項3】
制御部が、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数(写像)のうち、所望の1個の前記全単射関数の前記m個の整数からなる整数系列の入力に対する出力の状態を順列として第1の記憶部に記憶する第1のステップと、
前記制御部が、前記m個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第2の記憶部に記憶することを、前記の周期に未出現の入力値の全てに行う第2のステップと、
前記制御部が、前記第2の記憶部に記憶された周期が前記mであるか否かを判定し、前記周期が前記mであるとき、その周期を前記所望の1個の前記全単射関数の最大周期であると決定する第3のステップと
を含むことを特徴とする整数系列の周期判定方法。
【請求項4】
第1及び第2の記憶部と、
0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数についての前記m種類の入出力に対する出力の状態を全て順列として生成して前記第1の記憶部に記憶する順列生成及び記憶手段と、
前記第1の記憶部に記憶された前記m!個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、前記周期が前記mより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての前記入力値及び全ての前記未出現の入力値に対して順次行う周期計算及び累計手段と、
前記第2のステップで求められた前記m!個の全単射関数の最小周期から最大周期までの前記周期を第2の記憶部に記憶する記憶手段と
を有することを特徴とする整数系列の周期判定装置。
【請求項5】
前記順列生成及び記憶手段は、
前記m!個の全単射関数(写像)のうち、最初の全単射関数の順列データのデータを作成した後、2番目からm!番目までの全単射関数の順列データは、それぞれその1つ前の順番の全単射関数の順列データから作成し、作成した順列データを前記第1の記憶部に記憶することを特徴とする請求項4記載の整数系列の周期判定装置。
【請求項6】
第1及び第2の記憶部と、
0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数のうち、所望の1個の前記全単射関数の前記m個の整数からなる整数系列の入力に対する出力の状態を順列として第1の記憶部に記憶する順列記憶手段と、
前記m個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第2の記憶部に記憶することを、前記の周期に未出現の入力値の全てに行う周期計算及び累計手段と、
前記第2の記憶部に記憶された周期が前記mであるか否かを判定し、前記周期が前記mであるとき、その周期を前記所望の1個の前記全単射関数の最大周期であると決定する最大周期判定手段と
を有することを特徴とする整数系列の周期判定装置。
【請求項7】
コンピュータに、
0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数についての前記m種類の入出力に対する出力の状態を全て順列として生成して第1の記憶部に記憶する第1のステップと、
前記第1の記憶部に記憶された前記m!個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを全ての入力値に対して順次行い、得られた周期を第2の記憶部に記憶する第2のステップと、
前記第2のステップで求めた前記周期が前記mより小さいと判定したときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを全ての未出現の入力値に対して順次行い、得られた周期を前記第2の記憶部に記憶する第3のステップと、
前記第2の記憶部に記憶された前記第2及び第3のステップで得られた周期に基づいて、前記m!個の全単射関数の最小周期から最大周期までの周期の判定を行う第4のステップと
を実行させることを特徴とする整数系列の周期判定プログラム。
【請求項8】
前記第1のステップは、
前記m!個の全単射関数(写像)のうち、最初の全単射関数の順列データのデータを作成した後、2番目からm!番目までの全単射関数の順列データは、それぞれその1つ前の順番の全単射関数の順列データから作成することを特徴とする請求項1記載の整数系列の周期判定プログラム。
【請求項9】
コンピュータに、
0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数のうち、所望の1個の前記全単射関数の前記m個の整数からなる整数系列の入力に対する出力の状態を順列として第1の記憶部に記憶する第1のステップと、
前記第1の記憶部に記憶された前記m!個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、前記周期が前記mより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、前記の周期に未出現の入力値の全てに行う第2のステップと、
前記第2のステップで求められた前記m!個の全単射関数の最小周期から最大周期までの前記周期を第2の記憶部に記憶する第3のステップと
を実行させることを特徴とする整数系列の周期判定プログラム。
【請求項1】
制御部が、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数(写像)についての前記m種類の入力に対する出力の状態のデータを全て順列として作成して第1の記憶部に記憶する第1のステップと、
前記制御部が、前記第1の記憶部に記憶された前記m!個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、前記周期が前記mより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての前記入力値及び全ての前記未出現の入力値に対して順次行う第2のステップと、
前記制御部が、前記第2のステップで求められた前記m!個の全単射関数の最小周期から最大周期までの前記周期を第2の記憶部に記憶する第3のステップと
を含むことを特徴とする整数系列の周期判定方法。
【請求項2】
前記第1のステップは、
前記m!個の全単射関数(写像)のうち、最初の全単射関数の順列データのデータを作成した後、2番目からm!番目までの全単射関数の順列データは、それぞれその1つ前の順番の全単射関数の順列データから作成することを特徴とする請求項1記載の整数系列の周期判定方法。
【請求項3】
制御部が、0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数(写像)のうち、所望の1個の前記全単射関数の前記m個の整数からなる整数系列の入力に対する出力の状態を順列として第1の記憶部に記憶する第1のステップと、
前記制御部が、前記m個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第2の記憶部に記憶することを、前記の周期に未出現の入力値の全てに行う第2のステップと、
前記制御部が、前記第2の記憶部に記憶された周期が前記mであるか否かを判定し、前記周期が前記mであるとき、その周期を前記所望の1個の前記全単射関数の最大周期であると決定する第3のステップと
を含むことを特徴とする整数系列の周期判定方法。
【請求項4】
第1及び第2の記憶部と、
0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数についての前記m種類の入出力に対する出力の状態を全て順列として生成して前記第1の記憶部に記憶する順列生成及び記憶手段と、
前記第1の記憶部に記憶された前記m!個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、前記周期が前記mより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての前記入力値及び全ての前記未出現の入力値に対して順次行う周期計算及び累計手段と、
前記第2のステップで求められた前記m!個の全単射関数の最小周期から最大周期までの前記周期を第2の記憶部に記憶する記憶手段と
を有することを特徴とする整数系列の周期判定装置。
【請求項5】
前記順列生成及び記憶手段は、
前記m!個の全単射関数(写像)のうち、最初の全単射関数の順列データのデータを作成した後、2番目からm!番目までの全単射関数の順列データは、それぞれその1つ前の順番の全単射関数の順列データから作成し、作成した順列データを前記第1の記憶部に記憶することを特徴とする請求項4記載の整数系列の周期判定装置。
【請求項6】
第1及び第2の記憶部と、
0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数のうち、所望の1個の前記全単射関数の前記m個の整数からなる整数系列の入力に対する出力の状態を順列として第1の記憶部に記憶する順列記憶手段と、
前記m個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第2の記憶部に記憶することを、前記の周期に未出現の入力値の全てに行う周期計算及び累計手段と、
前記第2の記憶部に記憶された周期が前記mであるか否かを判定し、前記周期が前記mであるとき、その周期を前記所望の1個の前記全単射関数の最大周期であると決定する最大周期判定手段と
を有することを特徴とする整数系列の周期判定装置。
【請求項7】
コンピュータに、
0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数についての前記m種類の入出力に対する出力の状態を全て順列として生成して第1の記憶部に記憶する第1のステップと、
前記第1の記憶部に記憶された前記m!個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを全ての入力値に対して順次行い、得られた周期を第2の記憶部に記憶する第2のステップと、
前記第2のステップで求めた前記周期が前記mより小さいと判定したときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを全ての未出現の入力値に対して順次行い、得られた周期を前記第2の記憶部に記憶する第3のステップと、
前記第2の記憶部に記憶された前記第2及び第3のステップで得られた周期に基づいて、前記m!個の全単射関数の最小周期から最大周期までの周期の判定を行う第4のステップと
を実行させることを特徴とする整数系列の周期判定プログラム。
【請求項8】
前記第1のステップは、
前記m!個の全単射関数(写像)のうち、最初の全単射関数の順列データのデータを作成した後、2番目からm!番目までの全単射関数の順列データは、それぞれその1つ前の順番の全単射関数の順列データから作成することを特徴とする請求項1記載の整数系列の周期判定プログラム。
【請求項9】
コンピュータに、
0からm−1(ただし、mは2以上の整数)までの値の重複しないm個の整数からなる整数系列の入力(原像)と出力(像)とを持つm!個の全単射関数のうち、所望の1個の前記全単射関数の前記m個の整数からなる整数系列の入力に対する出力の状態を順列として第1の記憶部に記憶する第1のステップと、
前記第1の記憶部に記憶された前記m!個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、前記周期が前記mより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、前記の周期に未出現の入力値の全てに行う第2のステップと、
前記第2のステップで求められた前記m!個の全単射関数の最小周期から最大周期までの前記周期を第2の記憶部に記憶する第3のステップと
を実行させることを特徴とする整数系列の周期判定プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【公開番号】特開2011−123693(P2011−123693A)
【公開日】平成23年6月23日(2011.6.23)
【国際特許分類】
【出願番号】特願2009−281167(P2009−281167)
【出願日】平成21年12月11日(2009.12.11)
【出願人】(396007982)株式会社ネットコムセック (13)
【Fターム(参考)】
【公開日】平成23年6月23日(2011.6.23)
【国際特許分類】
【出願日】平成21年12月11日(2009.12.11)
【出願人】(396007982)株式会社ネットコムセック (13)
【Fターム(参考)】
[ Back to top ]