(57)【要約】【課題】任意の大きさの自然数の集合による全単射関数を用いて作成した整数系列の周期を判定する。【解決手段】順列作成部４は、全単射関数（写像）の入力に対する出力データ（原像に対する像）の並びである順列A(i)を作成する。順列記憶部５は、任意の大きさｍ（ｍは２以上の自然数）の全ての全単射関数の入力に対する出力の状態を示す順列S(i,j)を記憶する。周期計算部６は、任意の全単射関数の入力に対する出力データ系列を更に入力とする手順を繰り返し行って、作成する整数系列の周期を計算する。周期記憶部１０は、順列数設定部１１が指定した周期計算部６の周期計算結果を記憶する。順列数設定部１１は、任意のデータ数ｍの全ての全単射関数の存在数を記憶する。【選択図】図１
2011123693.tif 000002
【特許請求の範囲】
【請求項１】
制御部が、０からｍ−１（ただし、ｍは２以上の整数）までの値の重複しないｍ個の整数からなる整数系列の入力（原像）と出力（像）とを持つｍ！個の全単射関数（写像）についての前記ｍ種類の入力に対する出力の状態のデータを全て順列として作成して第１の記憶部に記憶する第１のステップと、
前記制御部が、前記第１の記憶部に記憶された前記ｍ！個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、前記周期が前記ｍより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての前記入力値及び全ての前記未出現の入力値に対して順次行う第２のステップと、
前記制御部が、前記第２のステップで求められた前記ｍ！個の全単射関数の最小周期から最大周期までの前記周期を第２の記憶部に記憶する第３のステップと
を含むことを特徴とする整数系列の周期判定方法。
【請求項２】
前記第１のステップは、
前記ｍ！個の全単射関数（写像）のうち、最初の全単射関数の順列データのデータを作成した後、２番目からｍ！番目までの全単射関数の順列データは、それぞれその１つ前の順番の全単射関数の順列データから作成することを特徴とする請求項１記載の整数系列の周期判定方法。
【請求項３】
制御部が、０からｍ−１（ただし、ｍは２以上の整数）までの値の重複しないｍ個の整数からなる整数系列の入力（原像）と出力（像）とを持つｍ！個の全単射関数（写像）のうち、所望の１個の前記全単射関数の前記ｍ個の整数からなる整数系列の入力に対する出力の状態を順列として第１の記憶部に記憶する第１のステップと、
前記制御部が、前記ｍ個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第２の記憶部に記憶することを、前記の周期に未出現の入力値の全てに行う第２のステップと、
前記制御部が、前記第２の記憶部に記憶された周期が前記ｍであるか否かを判定し、前記周期が前記ｍであるとき、その周期を前記所望の１個の前記全単射関数の最大周期であると決定する第３のステップと
を含むことを特徴とする整数系列の周期判定方法。
【請求項４】
第１及び第２の記憶部と、
０からｍ−１（ただし、ｍは２以上の整数）までの値の重複しないｍ個の整数からなる整数系列の入力（原像）と出力（像）とを持つｍ！個の全単射関数についての前記ｍ種類の入出力に対する出力の状態を全て順列として生成して前記第１の記憶部に記憶する順列生成及び記憶手段と、
前記第１の記憶部に記憶された前記ｍ！個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、前記周期が前記ｍより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての前記入力値及び全ての前記未出現の入力値に対して順次行う周期計算及び累計手段と、
前記第２のステップで求められた前記ｍ！個の全単射関数の最小周期から最大周期までの前記周期を第２の記憶部に記憶する記憶手段と
を有することを特徴とする整数系列の周期判定装置。
【請求項５】
前記順列生成及び記憶手段は、
前記ｍ！個の全単射関数（写像）のうち、最初の全単射関数の順列データのデータを作成した後、２番目からｍ！番目までの全単射関数の順列データは、それぞれその１つ前の順番の全単射関数の順列データから作成し、作成した順列データを前記第１の記憶部に記憶することを特徴とする請求項４記載の整数系列の周期判定装置。
【請求項６】
第１及び第２の記憶部と、
０からｍ−１（ただし、ｍは２以上の整数）までの値の重複しないｍ個の整数からなる整数系列の入力（原像）と出力（像）とを持つｍ！個の全単射関数のうち、所望の１個の前記全単射関数の前記ｍ個の整数からなる整数系列の入力に対する出力の状態を順列として第１の記憶部に記憶する順列記憶手段と、
前記ｍ個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第２の記憶部に記憶することを、前記の周期に未出現の入力値の全てに行う周期計算及び累計手段と、
前記第２の記憶部に記憶された周期が前記ｍであるか否かを判定し、前記周期が前記ｍであるとき、その周期を前記所望の１個の前記全単射関数の最大周期であると決定する最大周期判定手段と
を有することを特徴とする整数系列の周期判定装置。
【請求項７】
コンピュータに、
０からｍ−１（ただし、ｍは２以上の整数）までの値の重複しないｍ個の整数からなる整数系列の入力（原像）と出力（像）とを持つｍ！個の全単射関数についての前記ｍ種類の入出力に対する出力の状態を全て順列として生成して第１の記憶部に記憶する第１のステップと、
前記第１の記憶部に記憶された前記ｍ！個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを全ての入力値に対して順次行い、得られた周期を第２の記憶部に記憶する第２のステップと、
前記第２のステップで求めた前記周期が前記ｍより小さいと判定したときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを全ての未出現の入力値に対して順次行い、得られた周期を前記第２の記憶部に記憶する第３のステップと、
前記第２の記憶部に記憶された前記第２及び第３のステップで得られた周期に基づいて、前記ｍ！個の全単射関数の最小周期から最大周期までの周期の判定を行う第４のステップと
を実行させることを特徴とする整数系列の周期判定プログラム。
【請求項８】
前記第１のステップは、
前記ｍ！個の全単射関数（写像）のうち、最初の全単射関数の順列データのデータを作成した後、２番目からｍ！番目までの全単射関数の順列データは、それぞれその１つ前の順番の全単射関数の順列データから作成することを特徴とする請求項１記載の整数系列の周期判定プログラム。
【請求項９】
コンピュータに、
０からｍ−１（ただし、ｍは２以上の整数）までの値の重複しないｍ個の整数からなる整数系列の入力（原像）と出力（像）とを持つｍ！個の全単射関数のうち、所望の１個の前記全単射関数の前記ｍ個の整数からなる整数系列の入力に対する出力の状態を順列として第１の記憶部に記憶する第１のステップと、
前記第１の記憶部に記憶された前記ｍ！個の全単射関数についての前記順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、前記周期が前記ｍより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を前記順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、前記の周期に未出現の入力値の全てに行う第２のステップと、
前記第２のステップで求められた前記ｍ！個の全単射関数の最小周期から最大周期までの前記周期を第２の記憶部に記憶する第３のステップと
を実行させることを特徴とする整数系列の周期判定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は整数系列の周期判定方法、周期判定装置及び周期判定プログラムに係り、特に擬似乱数等に用いられる整数系列の周期判定方法、周期判定装置及び周期判定プログラムに関する。
【背景技術】
【０００２】
近年、暗号やモンテカルロ法等に用いられる擬似乱数系列は、暗号解析の困難性を高めるために、周期の長い系列が要求される。また、これまで系列長が保証された擬似乱数系列として、Ｍ系列等が使用されることが多かったが、それ以外の手段として、カオスや帰還関数等を用いた生成方法を利用することが考えられる（例えば、非特許文献１、非特許文献２参照）。非特許文献１には、シフトレジスタを用いて周期の長い擬似乱数系列を発生することが開示されている。また、非特許文献２には擬似乱数系列を発生させる暗号理論一般について開示されている。
【０００３】
また、暗号解析の困難性を高め、安全性の高い擬似乱数系列を生成するために、複数の異なるＳボックスを利用した処理を行う構成の暗号処理装置（例えば、特許文献１参照）や、線形フィードバックシフトレジスタを利用したＭ系列の出力に非線形関数をフィルタとして用いることで、出力擬似乱数系列を推定困難にする構成の擬似乱数系列生成装置が知られている（例えば、特許文献２参照）。
【０００４】
更に、擬似乱数系列の利用可能性に基づいて、システム内の乱数生成器の系列反復周期を拡張するために、複数の互いに素となる数を法としてＲＮＳ(Residue Number System)剰余値を求め、それを組み合わせて出力系列とすることで系列長を拡張する方法も知られている（例えば、特許文献３参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Solomon Wolf Golomb,“Shift Register Sequences”,San Francisco,Holden-Day,1967.
【非特許文献２】Bruce Schneier,“Applied Cryptography”,Second Edition,John Wiley & Sons,Inc.1996.
【特許文献】
【０００６】
【特許文献１】特開２００８−５８８２８号公報
【特許文献２】特開平８−２０２５３５号公報
【特許文献３】特開２００９−３９２５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、カオスや帰還関数等を用いた生成方法を利用して擬似乱数系列を生成する場合は、生成した擬似乱数系列長が明らかでない場合があり、また生成された擬似乱数系列が短周期等の理由より使用目的によっては適さない擬似乱数系列を使用せざるを得ない場合もある。
【０００８】
また、特許文献１及び２各記載の装置では、生成した擬似乱数系列の周期を判定して、その周期の長さや周期の個数を求める機能は有しておらず、周期に使用した値を使用済みとして区別する機能を有していない。更に、特許文献３記載の方法も、擬似乱数系列の周期を判定して、その周期の長さや個数を求める機能や、剰余を利用することなく完全擬似乱数を求めることについては全く開示されていない。
【０００９】
このように、従来は擬似乱数系列の周期を判定することは知られておらず、このことから系列長の保証された完全擬似乱数を得ることは容易でなかった。
【００１０】
本発明は以上の点に鑑みなされたもので、擬似乱数系列の生成のために、任意の大きさの自然数の集合による全単射関数を用いて生成された整数系列の周期を判定し得る整数系列の周期判定方法、周期判定装置及び周期判定プログラムを提供することを目的とする。
【００１１】
また、本発明の他の目的は、自然数を入出力とする全単射関数及び変換表もしくはＳボックス等の出力フィードバックにおいて、周期長の合計を求める演算を行い、各周期長が幾つ存在するかの結果や、最大長の周期を保有するかどうかの判定が可能である整数系列の周期判定方法、周期判定装置及び周期判定プログラムを提供することにある。
【課題を解決するための手段】
【００１２】
上記の目的を達成するため、第１の発明の整数系列の周期判定方法は、制御部が、０からｍ−１（ただし、ｍは２以上の整数）までの値の重複しないｍ個の整数からなる整数系列の入力（原像）と出力（像）とを持つｍ！（ｍ！はｍの階乗。即ち１×２×・・・×（ｍ−１）×ｍを表す。）個の全単射関数（写像）についての前記ｍ種類の入力に対する出力の状態を全て順列として生成して第１の記憶部に記憶する第１のステップと、制御部が、第１の記憶部に記憶されたｍ！個の全単射関数についての順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、周期がｍより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての入力値及び全ての未出現の入力値に対して順次行う第２のステップと、制御部が、第２のステップで求められたｍ！個の全単射関数の最小周期から最大周期までの周期を第２の記憶部に記憶する第３のステップとを含むことを特徴とする。
【００１３】
また、上記の目的を達成するため、第２の発明の整数系列の周期判定方法は、制御部が、０からｍ−１（ただし、ｍは２以上の整数）までの値の重複しないｍ個の整数からなる整数系列の入力（原像）と出力（像）とを持つｍ！個の全単射関数（写像）のうち、所望の１個の前記全単射関数の前記ｍ個の整数からなる整数系列の入力に対する出力の状態を順列として第１の記憶部に記憶する第１のステップと、制御部が、前記ｍ個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第２の記憶部に記憶することを、前記ｍ個の入力のすべてについて行う第２のステップと、制御部が、前記第２の記憶部に記憶された周期が前記ｍであるか否かを判定し、前記周期が前記ｍであるとき、その周期を前記所望の１個の前記全単射関数の最大周期であると決定する第３のステップとを含むことを特徴とする。
【００１４】
また、上記の目的を達成するため、第３の発明の整数系列の周期判定装置は、第１及び第２の記憶部と、０からｍ−１（ただし、ｍは２以上の整数）までの値の重複しないｍ個の整数からなる整数系列の入力（原像）と出力（像）とを持つｍ！個の全単射関数（写像）についての前記ｍ種類の入力に対する出力の状態を全て順列として生成して前記第１の記憶部に記憶する順列生成及び記憶手段と、第１の記憶部に記憶されたｍ！個の全単射関数についての順列のそれぞれについて、或る入力値を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求め、周期がｍより小さいときは、未出現の入力値が存在するものと判定し、未出現の入力値を順列に与えたときの出力値を求め、更にその出力値を入力値とすることを、未出現の入力値と同じ出力値が得られるまで繰り返し変換を行い、その変換回数を周期として求めることを、全ての入力値及び全ての未出現の入力値に対して順次行う周期計算及び累計手段と、前記周期計算及び累計手段で得られた前記ｍ！個の全単射関数の最小周期から最大周期までの周期を第２の記憶部に記憶する記憶手段とを有することを特徴とする。
【００１５】
また、上記の目的を達成するため、第４の発明の整数系列の周期判定装置は、第１及び第２の記憶部と、０からｍ−１（ただし、ｍは２以上の整数）までの値の重複しないｍ個の整数からなる整数系列の入力（原像）と出力（像）とを持つｍ！個の全単射関数（写像）のうち、所望の１個の前記全単射関数の前記ｍ個の整数からなる整数系列の入力に対する出力の状態を順列として第１の記憶部に記憶する順列記憶手段と、ｍ個の入力のうち最初の入力を与えたときの出力値を求め、更にその出力値を入力値とすることを、最初の入力値と同じ出力値が得られるまで繰り返すと共に、その繰り返し回数を周期として第２の記憶部に記憶することを、前記ｍ個の入力のすべてについて行う周期計算及び累計手段と、第２の記憶部に記憶された周期が前記ｍであるか否かを判定し、前記周期が前記ｍであるとき、その周期を前記所望の１個の前記全単射関数の最大周期であると決定する最大周期判定手段とを有することを特徴とする。
【００１６】
また、上記の目的を達成するため、第５の発明の整数系列の周期判定プログラムは、コンピュータに、第１の発明の整数系列の周期判定方法の第１乃至第３のステップを実行させることを特徴とする。
【００１７】
更に、上記の目的を達成するため、第６の発明の整数系列の周期判定プログラムは、コンピュータに、第２の発明の整数系列の周期判定方法の第１乃至第３のステップを実行させることを特徴とする。
【発明の効果】
【００１８】
本発明によれば、任意の大きさの自然数の集合を入力（原像）と出力（像）とした全単射関数（写像）を用いて出力を入力に帰還することで生成された整数系列の帰還周期の判定が行え、また、その整数系列の最大周期を判定することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の整数系列の周期判定装置の第１の実施形態のブロック図である。
【図２】全単射関数の一例の説明図である。
【図３】本発明による擬似乱数作成の概要の説明図である。
【図４】本発明の第１の実施形態の概要説明用フローチャートである。
【図５】本発明の第１の実施形態の全単射関数の入出力データの順列作成の概要説明用フローチャートである。
【図６】本発明の第１の実施形態の作成した各々の順列データから各周期を判定する概要説明用フローチャートである。
【図７】本発明の第１の実施形態の動作を説明するフローチャート（その１）である。
【図８】本発明の第１の実施形態の動作を説明するフローチャート（その２）である。
【図９】図７中のステップＳ１の詳細動作を説明するフローチャートである。
【図１０】本発明による周期の判定動作のための関数帰還を説明する図である。
【図１１】本発明の整数系列の周期判定装置の第２、第３の実施形態のブロック図である。
【図１２】本発明の第２の実施形態の動作を説明するフローチャート（その１）である。
【図１３】本発明の第２の実施形態の動作を説明するフローチャート（その２）である。
【図１４】本発明の第３の実施形態の動作を説明するフローチャートである。
【発明を実施するための形態】
【００２０】
次に、本発明の各実施形態について、図面と共に詳細に説明する。
【００２１】
（第１の実施形態）
図１は、本発明になる整数系列の周期判定装置の第１の実施形態のブロック図を示す。同図に示すように、本実施形態の整数系列の周期判定装置１Ａは、装置１Ａ全体を統括的に制御する制御部２Ａ、データ数記憶部３、順列作成部４、順列記憶部５、周期計算部６、入力指定部７、出力記憶部８、周期累計部９、周期記憶部１０、順列数設定部１１、検索位置指定部１２から構成されている。
【００２２】
制御部２Ａ、順列作成部４、周期計算部６、順列数設定部１１及び検索位置指定部１２は、例えば中央処理装置（ＣＰＵ）により構成される。また、データ数記憶部３、出力記憶部８、周期累計部９及び周期記憶部１０は記憶装置により構成され、入力指定部７は所定の入力装置により構成される。
【００２３】
データ数記憶部３は、単射で、かつ、全射でもある関数である全単射関数の有する連続した自然数の入出力データ（原像及び像）の数Ｍを記憶する。順列作成部４は、全単射関数の入力に対する出力データ（原像に対する像）の並びである順列A(i)を作成する。この場合、順列A(i)は、出力データの値は重複せず、全ての値が出現するように作成される。
【００２４】
順列記憶部５は、後述するようにして作成された任意の大きさ（データ数Ｍ）ｍ（ｍは２以上の自然数）の全ての全単射関数（写像）の入力に対する出力（原像に対する像）の状態を示す順列S(i,j)を記憶する第１の記憶部である。周期計算部６は、後述するように任意の全単射関数の入力に対する出力データ（原像に対する像）を更に入力とする手順を繰り返し行って、作成する整数系列の周期Pを計算する。
【００２５】
入力指定部７は、入力位置（原像の位置）INPを指定する。出力記憶部８は、入力指定部７で指定された入力位置の周期計算部６の出力データ（像）の値OUTPを記憶する。周期累計部９は、周期計算部６で計算した周期Pの累計結果PSを記憶する。
【００２６】
周期記憶部１０は、順列数設定部１１が指定した周期計算部６の周期計算結果PR(PM,M)を記憶する第２の記憶部である。本実施形態では、周期記憶部１０は、任意の大きさ（データ数Ｍ）ｍの全ての全単射関数の各々の周期について存在数を記憶する。順列数設定部１１は、任意のデータ数ｍの全ての全単射関数の存在数PMを記憶する。検索位置指定部１２は、順列作成部４において作成される任意の順列の値A(i)の既に作成された、それまでの順列の検索位置POSを指定する。
【００２７】
上記の構成のうち、制御部２Ａ、データ数記憶部３、順列作成部４、入力指定部７、順列数設定部１１、及び検索位置指定部１２は、ｍ！個の全単射関数についてのｍ種類の入出力に対する出力の状態をすべて順列として生成して第１の記憶部である順列記憶部５に記憶する順列生成及び記憶手段を構成する。また、制御部２Ａ、データ数記憶部３、周期計算部６、入力指定部７、出力記憶部８、周期累計部９、及び順列数設定部１１は、周期計算及び累計手段と、第２の記憶部である周期記憶部１０に判定した周期を記憶する記憶手段とを構成する。
【００２８】
ところで、図２に示すように、ｍ個の自然数ｘ（例えば、データの集合Ｘ＝{ｘ|ｘ=natural number,０≦ｘ≦（ｍ-1）}）を入力（原像）と出力（像）とする、全ての全単射関数（写像）ｆの数は、ｍ！存在することが知られている。本発明は、入力データと出力データとが一対一で対応する全単射関数を用いた変換による擬似乱数系列の生成において、図３に示すように、ｍ個の自然数をその関数による変換の写像の原像である入力データ（０〜ｍー１）と、像となる出力データ（０〜ｍー１）とし、出力データを更に入力データとして帰還するような帰還系列（擬似乱数系列）について、すべての周期を判定するものである。
【００２９】
本発明では、ｍ！個の全単射関数についてのｍ種類の入力に対する出力の状態を、全て順列として列記することで得る。これは、０〜（ｍ−１）を最初の全単射関数の出力の順列とし、それ以降の全単射関数の出力の並びは、１つ前の順列において、その最後の出力の位置からバックトラックとインクリメンタルサーチの手法を用いて行うことで、次の順列を求めることができる。
【００３０】
次に、本発明では、上記の方法で求めた順列（関数）について、最初の入力値（例えば０）から、その入力と同じ出力値（例えば０）となるまで変換を行い、その変換回数を周期として求める。更に、ここで出力値として出現しないものの入力値についても順に同様な変換を行い、その最初の入力値に戻るまでの変換回数を周期として求める。すべての入力値が出現した場合には、全ての周期とその周期の出現回数が求まる。また、任意の一つの全単射関数について上記と同様の手順により全ての周期とその出現回数を求めることが可能である。
【００３１】
本発明における上記の全単射関数は、ｍ個の自然数による任意の並びの単なる順列の表、ラテン方陣のような変換表（換字表）、Ｓボックス、ブロック暗号、帰還型ストリーム暗号に相当し、本発明で周期が判定される整数系列は、ブロック暗号のＯＦＢ(Output Feed Back)モードや帰還型ストリーム暗号の出力系列に相当する。
【００３２】
ここで、大きさ２（ｍ＝２）の全ての全単射関数の入出力データの関係は、下記に示される。
【００３３】
ｆ１＝[０  １]：０→０，１→１
ｆ２＝[１  ０]：０→１→０
上記の→の左側の値は入力値、右側の値は出力値を示す（後述する他の例も同様）。従って、１番目の入出力データの関係ｆ１では、０が入力されると０が出力される場合と、１が入力されると１が出力される場合を示しており、周期１が２個である。また、２番目の入出力データの関係ｆ２では、０が入力されると１が出力され、１が入力されると０が出力される場合を示しており、周期２が１個であることを示す。従って、ｍ＝２の整数系列の全ての全単射関数は、周期１が２個と周期２（最大周期）が１個を有すると結論することができる。この例は次のような表で表すこともできる。
【００３４】
【表１】
2011123693.tif 000003
同様に、大きさ３（ｍ＝３）の全ての全単射関数の入出力データの関係は、下記に示される。
【００３５】
ｆ１＝[０  １  ２]：０→０,１→１,２→２（ゆえに、周期１が３個）
ｆ２＝[０  ２  １]：０→０,１→２→１（ゆえに、周期１が１個と周期２が１個）
ｆ３＝[１  ０  ２]：０→１→０,２→２（ゆえに周期１が１個と周期２が１個）
ｆ４＝[１  ２  ０]：０→１→２→０（ゆえに周期３が１個）
ｆ５＝[２  ０  １]：０→２→１→０（ゆえに周期３が１個）
ｆ６＝[２  １  ０]：０→２→０,１→１（ゆえに周期１が１個と周期２が１個）
よって、ｍ＝３の場合では、全ての全単射関数は、周期１が６個と周期２が３個と周期３（最大周期）が２個を有すると結論できる。この例は次のような表で表すこともできる。
【００３６】
【表２】
2011123693.tif 000004
同様に、ｍ個の自然数（整数）からなる整数系列の全ての全単射関数の入出力データの関係は、下記の表３で表すことができる。
【００３７】
【表３】
2011123693.tif 000005
図１に示す第１の実施形態の整数系列の周期判定装置１Ａは、入出力データの大きさが任意のｍの場合の全ての全単射関数の全ての整数系列の作成とその系列の全周期を判定する装置の例である。まず、本実施形態の動作の概要について説明する。
【００３８】
図４は、本実施形態の概要のフローチャートを示す。同図に示すように、整数系列の周期判定装置１Ａは、まず１つの全単射関数の出力の順列データを作成する（ステップＳ１５１）。続いて、整数系列の周期判定装置１Ａは、ステップＳ１５１で作成した順列データから、全単射関数の出力から入力への帰還を繰り返すことによる帰還系列の周期について部分周期最大周期の全ての周期（長）を判定する（ステップＳ１５２）。
【００３９】
図５は、図４のステップＳ１５１の順列データ作成動作の詳細を示す。図５に示すように、順列データ作成処理では、最初の関数の順列データを作成し（ステップＳ２０１）、続いて、二番目の関数の順列データを最初のデータから作成する（ステップＳ２０２）。以下、同様にして、ｍ！番目の関数の順列データをｍ！−１番目の順列データから作成する（ステップＳ２０３）。
【００４０】
図６は、図４のステップＳ１５２の作成した順列データから周期を判定する動作の詳細を示す。図６に示すように、周期判定処理では、最初の関数の順列データの各周期を累計し、周期記憶部１０に加算する（ステップＳ３０１）。続いて、二番目の関数の順列データの各周期を累計し、周期記憶部１０に加算する（ステップＳ３０２）。以下、同様にして、ｍ！番目の関数の順列データの各周期を累計し周期記憶部１０に加算する（ステップＳ３０３）。
【００４１】
次に、本実施形態の整数系列の周期判定装置１Ａによる動作について、更に詳細に説明する。図７及び図８は、図４で説明した本実施形態の概要動作を更に詳細に説明するフローチャートを示す。図９は、図７中のステップＳ１で作成する順列（整数系列データ）の作成方法の詳細動作説明用フローチャートを示す。図７のステップＳ１は、図５のフローチャートで概要動作を説明した処理ステップであり、図７のステップＳ２以降と図８の各ステップは、図６のフローチャートで概要動作を説明した処理の詳細動作を説明するものである。
【００４２】
まず、図１の制御部２Ａは、順列作成部４にて作成したｍ！（ここでは、ｍ＝２）個の順列A(0)〜A(m-1)を順列記憶部５に設定する（図７のステップＳ１）。このステップＳ１による順列の作成は、出力データの最初の位置として順列作成部４のA(0)から最後の位置A(m-1)に未設定の昇順の自然数（0〜m-1）を重複が発生しないように順に設定してゆく図９のバックトラック技法とインクリメンタルサーチ技法により作成可能である。
【００４３】
周期を判定すべき関数の出力データの順列が完成したら、順列作成部４の順列A(0)〜A(m-1)のデータをｍ！番目の順列記憶部５の順列S(m!,0)〜S(m!,m-1)に設定する。更に、ｍ！個のうちの残りの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)を求めることが可能であり、これを順次行うことでｍ個の系列のデータを各々有する全てのｍ！組の関数の系列データS(m!,0)〜S(m!,m-1)、・・・、S(1,0)〜S(1,m-1)を作成することが可能である。
【００４４】
なお、この順列記憶部５に設定した判定用の順列は事前にm!-1個全てを作成し準備しておくものとしているが、他の方法として一つの周期判定の前に各々順に同様の手法で作成することにより系列データの記憶場所である順列記憶部５に１つだけ事前に設定することで使用する記憶場所として順列記憶部を一つ分のみ重複して使用し記憶部の使用量をｍ！−１個削減することも可能である。
【００４５】
ここでは全単射関数の入出力データの大きさ（サイズ）ｍが２の場合についての例を説明する。
【００４６】
このステップＳ１による順列（整数系列データ）の作成方法について、図９のフローチャートと共に説明する。まず、制御部２Ａは、順列数設定部１１に全単射関数の系列の数（順列数）ｍ！（ここでは、ｍ！＝２）を設定する（ステップＳ１０１）。続いて、制御部２Ａは、データ数記憶部３にデータ数ｍ（ここではｍ＝２）を設定し（ステップＳ１０２）、更に入力指定部７の値INPをデータの先頭の位置を示すものとして０に初期化した後（ステップＳ１０３）、入力指定部７が示す位置の順列作成部４の順列データの値A(INP)を０に設定する（ステップＳ１０４）。これにより、最初の設定位置の順列データはA(INP)＝A(0)＝０となる。
【００４７】
次に、制御部２Ａは、入力指定部７の値INPがデータの先頭の設定位置である０かどうかを判断し（ステップＳ１０５）、先頭の設定位置０であればステップＳ１０６へ進み、先頭の位置０でなければデータの重複有無のチェックのためステップＳ１０８へ進む。ここでは、入力指定部７の値INPがステップＳ１０３により先頭の設定位置０とされているので、ステップＳ１０６に進み、入力指定部７の値INPが最後の設定位置ｍ−１（＝１）かどうかを判断する。ここでは、入力指定部７の値INPが先頭の設定位置０であり最後の設定位置ｍ−１（＝１）ではないので、入力指定部７の値INPを次のデータの設定位置として１だけ加算した後（ステップＳ１０７）、順列作成部４の値A(INP)（ここでは、A(1)）に設定データとして０を設定する（ステップＳ１０４）。これにより、A(INP)＝A(1)＝０となる。
【００４８】
次に、制御部２Ａは、入力指定部７の値INPが先頭のデータの位置として０かどうかを判断する（ステップＳ１０５）。ここでは、INPはステップＳ１０７により１とされており、先頭の位置０ではないのでステップＳ１０８へ進み、検索位置指定部１２が示す検索位置POSを０に初期化する。続いて、制御部２Ａは、入力指定部７が示す順列作成部４の値A(INP)が、検索位置指定部１２が示す順列作成部４の値A(POS)と等しいかどうかを判定する（ステップＳ１０９）。ここでは、設定されているデータの値A(INP)がA(1)＝０であり、検索位置のデータA(POS)がA(0)であり、A(0)は最初のステップＳ１０４の処理で０とされているため、両者は等しく、重複していると判定される（ステップＳ１０９のYes）。
【００４９】
制御部２Ａは、これにより、入力指定部７が示す順列作成部４の値A(INP)がデータの最大の設定値ｍ−１と等しいかどうか判定する（ステップＳ１１５）。この時点では、A(INP)＝A(1)＝０であり、１（＝ｍー１）と等しくないため、入力指定部７が示す順列作成部４の値A(INP)を１だけ加算して（ステップＳ１１９）、ステップＳ１０５に戻る。これにより、A(1)＝１となる。
【００５０】
続いて、制御部２Ａは、入力指定部７の値INPが先頭の設定位置０であるかどうかを判定し（ステップＳ１０５）、ここでは先頭の設定位置０ではないので、ステップＳ１０８に進んで検索位置指定部１２が示す検索位置POSを先頭の設定位置０に初期化した後、再び入力指定部７が示す順列作成部４の値A(INP)が、検索位置指定部１２が示す順列作成部４の値A(POS)と等しいかどうかを判定する（ステップＳ１０９）。この時点では、A(INP)がA(1)＝１であり、A(POS)がA(0)＝０であるため、両者は等しくないと判定される（ステップＳ１０９のNo）。
【００５１】
これにより、制御部２Ａは、検索位置指定部１２の検索位置の値POSを１だけ加算した後（ステップＳ１１０）、検索位置指定部１２の値POSと入力指定部７の値INPとが等しいかどうかを判定する（ステップＳ１１１）。ステップＳ１１１の判定の結果、上記のPOSとINPとが等しいときには、全てのデータに重複が無いということになり、ステップＳ１０６に進み、等しくないときにはステップＳ１０９に進む。この時点では、上記のPOSとINPとは共に１であるので、両者は等しいと判定される。これにより、制御部２ＡはステップＳ１０６に進み、入力指定部７の値INPがデータの最後の設定位置１（＝ｍ−１）かどうかを判定する。
【００５２】
ステップＳ１０６では、等しいと判定されるため、一つの関数のデータの作成が完了したことになり、続いて制御部２Ａは順列数設定部１１のPM（これはステップＳ１０１で設定されたｍ！＝２である）の示す順列記憶部５の順列S(PM,0)〜S(PM,m-1)、すなわちS(2,0)、S(2,1)に、作成済みの関数のデータが設定された順列作成部４の値A(0)〜A(m-1)、すなわち、１番目の関数データの順列の値としてA(0)＝0、A(1)＝１を設定する（ステップＳ１１２）。
【００５３】
続いて、制御部２Ａは、順列数設定部１１の示す値PMが最後の関数の数列の設定数の１かどうかを判定するが、1であれば全ての関数のデータｍ！−１個を作成済みとなり、もし１で無ければさらに残りの関数のデータの作成を行う（ステップＳ１１３）。この時点では、順列数設定部１１の示す値PMは２であり、最後の関数データの値１ではないので、順列数設定部１１の示す値PMを１だけ減算し次の関数データの設定位置を示すようにした後（ステップＳ１１４）、入力指定部７が示す順列作成部４の値A(INP)がデータの最大の設定値ｍ−１であるかどうかを判定する（ステップＳ１１５）。
【００５４】
この時点では、入力指定部７が示す順列作成部４の値A(INP)がA(1)＝１であり、最大の値ｍ−１に等しいので、続いて入力指定部７の値INPを１だけ減算し順列作成部の設定位置を戻した後（ステップＳ１１６）、入力指定部７の値INPはデータの先頭の設定位置０かどうか判定する（ステップＳ１１７）。この時点では入力指定部７の値INPは０で先頭であるので、制御部２Ａは続いて入力指定部７の示す順列作成部４の値A(INP)、すなわちA(0)が最大の値ｍ−１であるかどうかを判定する（ステップＳ１１８）。この時点では、A(0)は０であり、最大の値ｍ−１（＝１）に等しくないので、制御部２Ａは入力指定部７の示す順列作成部４の値である関数の設定データA(INP)を次の順序の値として１だけ加算して（ステップＳ１１９）、ステップＳ１０５に戻る。これにより、関数データの設定値A(0)は１とされる。
【００５５】
制御部２Ａは、ステップＳ１０５において、入力指定部７の値INPが先頭のデータの設定位置０であると判定し、続いてステップＳ１０６において入力指定部７の値INPがデータの最大の設定値１（＝ｍ−１）と等しくないと判定し、ステップＳ１０７において入力指定部７のデータの設定位置の値INPを１だけ加算して次の設定データの位置の値として１とした後、ステップＳ１０４に戻り、入力指定部７の示す順列作成部４の関数データの設定値A(INP)を０に設定する。これにより、２番目の設定データA(INT)＝A(1)＝０となる。
【００５６】
続いて、制御部２Ａは、入力指定部７のデータの設定位置の値INPが先頭の位置０かどうかを判定し（ステップＳ１０５）、この時点ではINPは１であり、先頭の位置の値０ではないので、検索位置指定部１２の検索位置の値POSを０に設定し（ステップＳ１０８）、入力指定部７が示す順列作成部４の値A(INP)が、検索位置指定部１２が示す順列作成部４の値A(POS)と等しいかどうかを判定する（ステップＳ１０９）。ここでは、設定されたデータA(INP)がA(1)＝０であり、検索位置のデータはA(POS)＝A(0)＝１であり、両者は等しくないため、ステップＳ１１０へ進んで検索位置指定部１２の検索位置の値POSを次の値１にした後、ステップＳ１１１において検索位置の値POSが入力指定部７の値INPと等しいかどうかを判定する。この時点では、POS＝INP＝１であるので、ステップＳ１０６に進んで入力指定部７のデータ設定位置の値INPが１（＝ｍ−１）と等しいかどうかを判定する。この時点では、データの設定位置INP＝１で最後の位置であるので、ステップＳ１１２に進んで順列記憶部５の順列S(PM,0)〜S(PM,m-1)、すなわち２番目の関数データの順列の値としてS(1,0)、S(1,1)に、順列作成部４の設定データの値A(0)＝１、A(1)＝０を設定する。
【００５７】
そして、制御部２Ａは順列数設定部１１の値PMが最後の関数の数列の設定数の１であるかどうかを判定する（ステップＳ１１３）。この時点では順列数設定部１１の値PMが最後の関数の設定数１であるので、制御部２Ａは全数列を作成したことになるので、処理を終了する。
【００５８】
このようにして、順列記憶部５の順列S(PM,0)〜S(PM,m-1)、すなわちS(2,0)、S(2,1)、S(1,0)、S(1,1)に、順列作成部４の値（順列）が記憶される。
【００５９】
再び図７及び図８に戻って説明する。上記のステップＳ１の処理後、制御部２Ａは、順列数設定部１１に任意のデータ数mの全ての全単射関数の存在数（出力系列の数）PMとしてｍ！（＝２）を設定した後（図７のステップＳ２）、データ数記憶部３に入出力データ（原像及び像）の数Ｍ（＝ｍ＝２）を設定する（図７のステップＳ３）。
【００６０】
続いて、制御部２Ａは、周期記憶部１０の各周期の個数を設定するPR(1,1)〜PR(m!,m)に各系列（１からｍ！）の各周期（１からｍ）の初期値として０を設定した後（図７のステップＳ４）、順列記憶部５に記憶され、順列数設定部１１が示す全単射関数の１番目（ＰＭ＝２）の系列データである順列S(2,0)〜S(2,m-1)の値（S(2,0)＝0、S(2,1)＝１）を周期計算部６にm個（ｍ＝２）の周期の計算用データP(0)〜P(m-1)として各々設定する（P(0)＝0、P(1)＝１）（図７のステップＳ５）。
【００６１】
続いて、制御部２Ａは、周期累計部９の値PSを０に設定した後（図７のステップＳ６）、最初の入力データに相当する先頭の位置（先頭のデータとして０）を入力指定部７の値INPに設定する（INP=0）（図７のステップＳ７）。次に、制御部２Ａは、入力指定部７の値INPが示す、周期計算部６の周期の配列P(1)〜P(m)の位置の入力データ（データは０）に対応する出力データP(INP)（データは０）を出力記憶部８の値OUTPとして設定する（図７のステップＳ８）。
【００６２】
続いて、制御部２Ａは、出力記憶部８の出力データの値OUTPが既に系列に使用済みかどうかを判定する（図７のステップＳ９）。使用済みの場合は、使用済みのマークとして−１の値となっている。使用済みであれば図７のステップＳ１０に進み、使用済みでなければ図８のステップＳ１５に進む。この時点では、OUTPは０であり、−１（使用済み）ではないので、制御部２ＡはステップＳ１５に進み、入力指定部７が示す値INP（ここでは０）の位置の周期計算部６の値P(INP)を、使用済みのマークとして−１に更新し、系列に使用済みであることを示す。
【００６３】
続いて、制御部２Ａは、出力記憶部８の出力データの値OUTP（ここでは０）を入力指定部７の値INPに設定する（図８のステップＳ１６）。続いて、制御部２Ａは、周期累計部９の値PSに１を加算して周期数を１に更新した後（図８のステップＳ１７）、入力指定部７の値INP（ここでは０）が示す周期計算部６の位置の入力データに対応する出力データの値P(INP)（ここでは−１）を出力記憶部８の値OUTPに設定する（図８のステップＳ１８）。
【００６４】
次に、制御部２Ａは、出力記憶部８の値OUTPが、既に系列に使用済みであることを示す−１であるかどうかを判定し（図８のステップＳ１９）、使用済み（ー１）であればステップＳ２３に進み、使用済みでなければステップＳ２０に進む。ここでは、使用済みであるので、ステップＳ２３に進み、順列数設定部１１の値PMが示す周期記憶部１０のｍ個の値PR(PM,1)〜PR(PM,m)のうち、周期累計部９の値PSに相当する位置PR(PM,PS)の周期の値に１を加算し（ここでは、周期１の位置に１を加算するPR(2,1)=PR(2,1)+1）、周期数を更新した後、次の周期の計算のために図７のステップＳ６に進む。
【００６５】
ステップＳ６において、制御部２Ａは、周期累計部９の値PSを０にクリアする。その後、制御部２Ａは、最初の入力データに相当する先頭の位置（先頭のデータとして０）を入力指定部７の値INPに設定する（図７のステップＳ５）。続いて、制御部２Ａは、入力指定部７の値INP（ここでは０）が示す周期計算部６の位置の入力データに対応する出力データの値P(INP)（ここでは−１）を出力記憶部８の値OUTPに設定する（図７のステップＳ８）。
【００６６】
次に、制御部２Ａは、出力記憶部８の値OUTPが、既に系列に使用済みであることを示す−１であるかどうかを判定し（図７のステップＳ９）、使用済み（ー１）であれば図７のステップＳ１０に進み、使用済みでなければ図８のステップＳ１５に進む。この時点では、使用済みであるので、制御部２ＡはステップＳ１０に進み、入力指定部７の値INPが系列の最後の位置を示す値(m-1)かどうかを判定する。この時点では、上記の値INPは０であり、最後の位置１(＝m-1)ではないので、値INPを１に更新した後（図７のステップＳ１１）、ステップＳ８に戻り、再び入力指定部７の値INP（ここでは１）が示す周期計算部６の位置の入力データに対応する出力データの値P(INP)（ここでは１）を出力記憶部８の値OUTPに設定する。
【００６７】
続いて、制御部２Ａは、ステップＳ９において、出力記憶部８の値OUTPが、既に系列に使用済みであるかどうかを判定する。ここでは、出力記憶部８の値OUTPは１であり、−１ではないので、制御部２Ａは図８のステップＳ１５に進み、出力記憶部８の値OUTPが示す位置（ここでは１）の周期計算部６のデータの値P(INP)を使用済みのマークとして−１に更新し、系列に使用済みであることを記す。続いて、制御部２Ａは、出力記憶部８の値OUTP（ここでは１）を入力指定部７の値INPに設定した後（ステップＳ１６）、周期累計部９の値PSに１を加算して周期数を更新する（ステップＳ１７）。これにより、周期数は１となる。続いて、制御部２Ａは、入力指定部７の値INP（ここでは１）が示す周期計算部６の位置の入力データに対応する出力データの値P(INP)（ここでは−１）を出力記憶部８の値OUTPに設定する（ステップＳ１８）。
【００６８】
続いて、制御部２Ａは、出力記憶部８の値OUTPが−１かどうかを判定する（ステップＳ１９）。この時点では、上記のステップＳ１８により上記の値OUTPは−１とされているので、制御部２ＡはステップＳ１９において−１である（使用済みである）と判定し、続いてステップＳ２３において順列数設定部１１の値PMが示す周期記憶部１０のｍ個の値PR(PM,1)〜PR(PM,m)のうち、周期累計部９の値PSに相当する位置PR(PM,PS)の周期の値に１を加算し（ここでは、周期１の位置に１を加算し周期１が２個となるPR(2,1)=PR(2,1)+1）、周期数を更新し図７のステップＳ６に進む。
【００６９】
続いて、制御部２Ａは、ステップＳ６で周期累計部９の値PSを０にクリアし、ステップＳ７で先頭の位置（先頭のデータとして０）を入力指定部７の値INPに設定し、ステップＳ８で入力指定部７の値INPが示す、周期計算部６の位置の入力データに対応する出力データP(INP)（ここでは−１）を出力記憶部８の値OUTPとして設定する。
【００７０】
続いて、制御部２Ａは、ステップＳ９において、出力記憶部８の値OUTPは−１であるかどうかを判定する。この時点では、値OUTPは−１であるので、制御部２ＡはステップＳ９において−１である（使用済みである）と判定し、次にステップＳ１０に進んで入力指定部７の値INPが系列の最終の位置を示す値１(＝m-1)であるかどうかを判定する。この時点では、入力指定部７の値INPは先頭の位置０であり、最後の位置１ではないので、制御部２Ａは次にステップＳ１１に進んで入力指定部７の値INPに１を加算して次の位置としステップＳ８に進む。これにより、上記の値INPは１となる。
【００７１】
続いて、制御部２Ａは、ステップＳ８において入力指定部７の値INPが示す、周期計算部６の位置の入力データに対応する出力データP(INP)（ここでは−１）を出力記憶部８の値OUTPとして設定した後、ステップＳ９において、出力記憶部８の値OUTPは−１であるかどうかを判定する。この時点では、値OUTPは−１であるので、制御部２ＡはステップＳ９において−１である（使用済みである）と判定し、次にステップＳ１０に進んで入力指定部７の値INPが系列の最後の位置を示す値１(＝m-1)であるかどうかを判定する。
【００７２】
この時点では、入力指定部７の値INPは１であり、系列の最後の位置を示す値１と等しいので一つの関数に存在する全ての周期が求められたこととなり、制御部２Ａは次にステップＳ１２に進んで順列数設定部１１の値PMが最後の関数に相当する値１であるかどうかを判定する。この時点では、順列数設定部１１の値PMはステップＳ２で設定された２（＝ｍ！）であり、１ではないので、制御部２Ａは順列数設定部１１の値PMを１減算して１とした後（図７のステップＳ１３）、ステップＳ５に戻り、再び順列数設定部１１の値PMの示す順列記憶部５に記憶されている全単射関数の全ての系列データである順列S(PM,0)〜S(PM,m-1)に設定されたｍ個のデータ（ここでは、PM＝1であるので、前述したように２番目の関数の２個のデータS(1,0)＝1,S(1,1)＝0）を、周期計算部６の周期の計算用データP(0)〜P(m-1)、すなわちP(0)=1、P(1)=0として各々設定する。
【００７３】
制御部２Ａは続いてステップＳ６で周期累計部９の値PSを０にクリアし、ステップＳ７で先頭の位置（先頭のデータとして０）を入力指定部７の値INPに設定した後、ステップＳ８へ進み、ここで入力指定部７の値INPが示す周期計算部６の位置の入力データに対応する出力データP(INP)（ここでは１）を出力記憶部８の値OUTPに設定する。続いて、制御部２ＡはステップＳ９に進んで値OUTPが−１（使用済み）ではないと判定した後、図８のステップＳ１５へ進んで入力指定部７が示す値INPの位置の周期計算部６の値P(INP)を、使用済みのマークとして−１に更新し、系列に使用済みであることを示す。
【００７４】
続いて、制御部２Ａは、ステップＳ１６で出力記憶部８の出力データの値OUTP（ここでは１）を入力指定部７の値INPに設定し、次のステップＳ１７で周期累計部９の値PSに１を加算して周期数を１に更新し（周期数は１となる）、次のステップＳ１８で入力指定部７の値INP（ここでは１）が示す、周期計算部６の位置の入力データに対応する出力データP(INP)（ここでは０）を出力記憶部８の値OUTPに設定する。
【００７５】
次に、制御部２Ａは、出力記憶部８の値OUTPが、既に系列に使用済みであることを示す−１であるかどうかを判定し、使用済み（ー１）であればステップＳ２３に進み、使用済みでなければステップＳ２０に進む。ここでは、OUTPは０であり−１ではない（使用済みでない）ので、ステップＳ２０に進み、入力指定部７の値INP(ここでは１)が示す位置の周期計算部６の出力データの値P(INP)である０を入力指定部７の値INPに設定する。
【００７６】
続いて、制御部２Ａは、入力指定部７の値INP（ここでは０）が示す位置の周期計算部６の出力データの値P(0)を、−１に更新して系列に使用済みであることを記した後（図８のステップＳ２１）、周期累計部９の値PSを１加算し周期数を更新し、ステップＳ１８に進む。これにより、周期の値PSは２となる。
【００７７】
ステップＳ１８では入力指定部７の値INPが示す、周期計算部６の位置P(INP)の入力データに対応する出力データの値（INP=0でP(INP)は−１）を出力記憶部８の値OUTPに設定する。続いて、制御部２Ａは、ステップＳ１９において出力記憶部８の値OUTPが−１であるかどうかを判定する。ここでは、出力記憶部８の値OUTPが−１であるので、ステップＳ２３に進み、順列数設定部１１の値PMが示す周期記憶部１０のｍ個の周期の値PR(PM,1)〜PR(PM,m)のうち、周期累計部９の値PSに相当する値PR(PM,PS)に１を加算し（ここでは、周期２の位置に１を加算しPR(1,2)=1となり、周期２が１個となる）、周期数を更新した後、図７のステップＳ５に進む。
【００７８】
続いて、制御部２Ａは、再び前述したステップＳ６、Ｓ７を経てステップＳ８へ進み、ここで入力指定部７の値INPが示す周期計算部６の値P(INP)の位置の入力データ（ここでは０）に対応する出力データ（ここでは−１）を出力記憶部８の値OUTPに設定する。続いて、制御部２ＡはステップＳ９に進んで出力記憶部８の値OUTPが−１であり、使用済みであると判定した後、ステップＳ１０に進んで入力指定部７の値INPが０であり、系列の最終の位置１（＝ｍ−１）ではないと判定するので、ステップＳ１１に進んで入力指定部７の値INPを１加算してINPを１とする。
【００７９】
続いて、制御部２Ａは、ステップＳ８において入力指定部７の値INP（ここでは１）が示す周期計算部６の値P(INP)の位置の入力データ（ここでは１）に対応する出力データ（ここでは−１）を出力記憶部８の値OUTPに設定した後、ステップＳ９に進んで出力記憶部８の値OUTPが−１であり、使用済みであると判定した後、ステップＳ１０に進んで入力指定部７の値INPが１であり、系列の最後の位置１（＝ｍ−１）であると判定する。
【００８０】
これにより、制御部２Ａは、順列数設定部１１が示す値PMがデータの最後の位置の１かどうかを判定する（図８のステップＳ１２）。この時点では、前述したステップＳ１３の処理によりPMは１となっているので、ステップＳ１２でPMが１であると判定され、全ての系列の処理が行われたと判断して処理を終了する（図８のステップＳ１４）。全ての処理を終了した場合には、周期記憶部１０には、この全単射関数の各々の系列の各周期長の全ての存在数が求まっている。ここでは、ｍ＝２であり、周期記憶部１０には、周期１が２個、周期２が１個を示す値が記憶されている。
【００８１】
このように、本実施形態によれば、図１０に示すような関数の帰還により周期を求めることができる。図１０において、ｍ！個の全単射関数の作成した順列データのそれぞれについて、各全単射関数の０からｍ−１までのｍ個の入力データのうちの最小のものである０の値を最初の入力データとし、その出力データを更に入力データとして帰還し、入力データが最初の入力データである０に戻るまでの帰還回数を求めて系列周期とする。このとき出現した出力データには出現済みと判断できるように−１等の出力データに存在しない値を周期計算部６に設定することで、未出現の出力データと区別する。
【００８２】
もし、ｍ個の全てのデータが系列に出現した場合には最大周期となり、完全擬似乱数の系列が作成されたことになる。しかし、未出現の出力データが残存する場合には、周期は部分的な系列のものであり、未出現の残りのデータに更に部分的な別の周期が存在することになる。未出現の出力データが残存する場合には、更に未出現の出力データのうちの入力データの最小のものを新たな周期の最初の入力データとし、その入力データに戻るまでの新たな系列周期を求め、全ての出力データが系列に出現し尽すまでこの手順を繰り返す。そして、ｍ！個の全ての順列データ（関数）について、この手順でそれぞれの周期数とその各周期の存在数を求める。
【００８３】
このようにして、本実施形態によれば、全ての全単射関数の全ての整数系列の全周期を判定することができる。そして、任意の周期の全単射関数を用いた擬似乱数系列や変換表などを作成することができる。
【００８４】
（第２の実施形態）
図１１は、本発明になる整数系列の周期判定装置の第２の実施形態のブロック図を示す。同図に示すように、本実施形態の整数系列の周期判定装置１Ｂは、装置１Ｂ全体を統括的に制御する制御部２Ｂ、データ数記憶部３、順列作成部４、順列記憶部５、周期計算部６、入力指定部７、出力記憶部８、周期累計部９、周期記憶部１０から構成されており、第１の実施形態の整数系列の周期判定装置１Ａと比較すると、順列数設定部１１と検索位置指定部１２を有しない。
【００８５】
制御部２Ｂ、順列作成部４及び周期計算部６は、例えば中央処理装置（ＣＰＵ）により構成される。また、データ数記憶部３、出力記憶部８、周期累計部９及び周期記憶部１０は記憶装置により構成され、入力指定部７は所定の入力装置により構成される。
【００８６】
データ数記憶部３は、単射で、かつ、全射でもある関数である全単射関数の有する連続した自然数の入出力データ（原像及び像）の数Ｍを記憶する。順列作成部４は、周期を判定するために予め事前に用意されたデータである、全単射関数の入力に対する出力データ（原像に対する像）の並びである順列A(i)を設定する。この場合、順列A(i)は、出力データの値に重複せず、全ての値が出現するように作成されたものとする。順列記憶部５は、任意のデータ数ｍの全単射関数の入力に対する出力データ（原像に対する像）の並びである順列S(j)を予め記憶している第１の記憶部である。周期計算部６は、後述するように任意の全単射関数の入力に対する出力データ（原像に対する像）を更に入力とする手順を繰り返し行って、判定する整数系列の周期Pを計算する。
【００８７】
入力指定部７は、入力位置（原像の位置）INPを指定する。出力記憶部８は、入力指定部７で指定された入力位置の周期計算部６の出力データ（像）の値OUTPを記憶する。周期累計部９は、周期計算部６で計算した周期Pの累積結果PSを記憶する。周期記憶部１０は、周期計算部６の周期計算結果PR(PM,M)を記憶する第２の記憶部である。本実施形態では、周期記憶部１０は、任意のデータ数ｍ（ここでは、ｍ＝３とする）の全単射関数の部分周期を含めた全ての周期について存在数を記憶する。
【００８８】
上記の構成のうち、制御部２Ｂ、データ数記憶部３、順列作成部４、周期計算部６、入力指定部７、及び周期累計部９は、ｍ！個の全単射関数のうち、所望の１個の全単射関数のｍ個の整数からなる整数系列の入力に対する出力の状態を順列として生成して第１の記憶部である順列記憶部５に記憶する順列記憶手段を構成する。また、制御部２Ｂ、周期計算部６、入力指定部７、出力記憶部８及び周期累計部９は、順列記憶部５に記憶された順列の周期を計算して第２の記憶部である周期記憶部１０に記憶する周期計算及び累計手段を構成する。
【００８９】
次に、本実施形態の動作について、図１２及び図１３のフローチャートを併せ参照して説明する。
【００９０】
図１１において、制御部２Ｂは、まず、データ数記憶部３にデータ数ｍ（ここでは、ｍ＝３）を設定する（図１２のステップＳ３１）。続いて、制御部２Ｂは、周期記憶部１０に記憶されている周期PR(0)〜PR(m-1)の各値を０に設定した後（図１２のステップＳ３２）、順列作成部４に全単射関数の入出力データとして、入力データ（０からｍ−１までの自然数）に対応する出力系列データA(0)〜A(m-1)を設定する（図１２のステップＳ３３）。具体的には、この出力系列データA(0)〜A(m-1)は、０からｍ−１までの重複しない自然数の任意の組み合わせのデータで、ここではｍ＝３であるので、例えば、A(0)＝２，A(1)＝０，A(2)＝１の３個のデータである。
【００９１】
続いて、制御部２Ｂは、順列作成部４に設定した上記の３個の出力系列データA(0)〜A(2)を順列記憶部５の順列S(0)〜S(m-1)にそれぞれ格納する（図１２のステップＳ３４）。ここでは、上記の順列記憶部５には、S(0)＝２，S(1)＝０，S(2)＝１の３個の順列が格納されることになる。
【００９２】
続いて、制御部２Ｂは、順列記憶部５に格納された順列S(0)〜S(m-1)を、周期計算部６に計算用のデータP(0)〜P(m-1)としてそれぞれ関数の出力データを設定する（図１２のステップＳ３５）。ここでは、上記の周期計算部６には、P(0)＝２，P(1)＝０，P(2)＝１の３個が設定されることになる。
【００９３】
続いて、制御部２Ｂは、周期累計部６の周期の値PSを０に設定（クリア）した後（図１２のステップＳ３６）、最初の入力データに相当する先頭のデータの位置（例えば０）を入力指定部７の値INPとして設定する（図１２のステップＳ３７）。次に、制御部２Ｂは、入力指定部７の値INPが示す周期計算部６の入力データに対応する出力データの値P(INP)を出力記憶部８の値OUTPに設定する（図１２のステップＳ３８）。ここでは、INPは０であるので、入力データはP(0)であり、それに対応する出力データは前述したように２であるから、OUTPは２に設定される。
【００９４】
続いて、制御部２Ｂは、出力記憶部８の値OUTPが既に系列に使用済みかどうかを比較する（図１２のステップＳ３９）。使用済みなら使用済みのマークとして−１の値となっている。ここでは、OUTPは２であり、−１ではないので、制御部２Ｂは使用済みでないと判定し、図１３のステップＳ４３に進んで、入力指定部７の値INPが示す周期計算部６の入力データに対応する出力データの値P(INP)を−１に設定し、系列に使用済みであることを示す。これにより、P(0)＝−１となる。
【００９５】
次に、制御部２Ｂは、出力記憶部８の値OUTP（ここでは２）を入力指定部７の値INPに設定する（図１３のステップＳ４４）。続いて、制御部２Ｂは、周期累計部９の値PSに１を加算し周期数を更新する（図１３のステップＳ４５）。これにより、周期数PSは１となる。続いて、制御部２Ｂは、入力指定部７の値INP（ここでは２）が示す、周期計算部６の入力データに対応する出力データの値P(INP)を出力記憶部８の値OUTPに設定する（図１３のステップＳ４６）。ここでは、INPは２であるから、P(2)に対応する出力データは前述したように１であるから、OUTPは１に設定される。
【００９６】
次に、制御部２Ｂは、出力記憶部８の値OUTPが使用済みであることを示す−１であるかどうかを判定する（図１３のステップＳ４７）。ここでは、上記のようにOUTPは１であり、−１ではないので、制御部２Ｂは、入力指定部７の値INP（ここでは２）が示す、周期計算部６の位置の入力データの値P(INP)に対応する出力データ（ここでは１）を入力指定部７の値INPに設定する（図１３のステップＳ４８）。続いて、制御部２Ｂは、入力指定部７の値INP（ここでは１）が示す、周期計算部６の入力データに対応する出力データの値P(INP)を−１に設定し、系列に使用済みであることを示す（図１３のステップＳ４９）。これにより、P(1)＝−１となる。
【００９７】
次に、制御部２Ｂは、周期累計部９の周期の値PSに１を加算して２とし、周期数を更新した後（図１３のステップＳ５０）、ステップＳ４６に戻り、入力指定部７の値INP（ここでは１）が示す、周期計算部６の位置の入力データに対応する出力データの値P(INP)を出力記憶部８の値OUTPに設定する。ここでは、INPは１であるから、P(1)に対応する出力データは−１であるから、OUTPは−１に設定される。
【００９８】
次に、制御部２Ｂは、出力記憶部８の値OUTPが使用済みであることを示す−１であるかどうかを判定する（図１３のステップＳ４７）。ここでは、上記のようにOUTPは−１であるから、制御部２Ｂは使用済みと判断し、周期累計部９の示す値PS（ここでは２）に相当する、周期記憶部１０の位置の周期の値PR(PS)に１を加算して、周期数を更新した後（図１３のステップＳ５１）、図１２のステップＳ３６に進む。これにより、PR(2)は１になる。つまり、周期２の周期数が１個と判定される。
【００９９】
続いて、制御部２ＢはステップＳ３６において、周期累計部６の値PSを０に設定（クリア）した後、最初の入力データに相当する先頭の位置（例えば０）を入力指定部７の値INPとして設定し（ステップＳ３７）、更に、入力指定部７の値INPが示す周期計算部６の位置の入力データに対応する出力データP(INP)を出力記憶部８の値OUTPに設定する（ステップＳ３８）。ここでは、INPは０であるので、入力データはP(0)であり、それに対応する出力データは前述したように−１であるから、OUTPは−１に設定される。
【０１００】
続いて、制御部２Ｂは、ステップＳ３９において、出力記憶部８の値OUTPが−１であり、既に系列に使用済みであると判定してステップＳ４０に進む。ステップＳ４０では、制御部２Ｂは、入力指定部７の値INPが系列の最後の位置(m-1)を示す２であるかどうかを判定する。ここでは、INPは０であり２ではないので、制御部２Ｂは入力指定部７の値INPを１加算して１とした後（図１２のステップＳ４２）、ステップＳ３８に進み入力指定部７の値INPが示す周期計算部６の位置の入力データに対応する出力データP(INP)を出力記憶部８の値OUTPに設定する。ここでは、INPは１であるので、入力データはP(1)であり、それに対応する出力データは前述したように１であるので、OUTPは１に設定される。
【０１０１】
続いて、制御部２Ｂは出力記憶部８の値OUTPが使用済みであることを示す−１であるかどうか判定する（ステップＳ３９）。ここでは、OUTPは１であり、−１ではないので、制御部２Ｂは使用済みでないと判定し、図１３のステップＳ４３に進んで、入力指定部７の値INPが示す周期計算部６の位置の入力データの値に対応する出力データP(INP)を−１に設定し、系列に使用済みであることを示す。これにより、P(1)＝−１となる。
【０１０２】
以後、制御部２Ｂは、前述したステップＳ４４、Ｓ４５、Ｓ４６の各処理を行った後、ステップＳ４７で出力記憶部８の値OUTPが使用済みであることを示す−１であると判定し、ステップＳ５１に進んで周期累計部９の示す値PS（ここでは１）に相当する、周期記憶部１０の位置の周期の値PR(PS)に１を加算して、周期数を更新する。これにより、PR(1)は１になる。つまり、周期１の周期数が１と判定される。
【０１０３】
その後、制御部２Ｂは、前述したステップＳ３６、Ｓ３７、Ｓ３８の各処理を行った後、ステップＳ３９で出力記憶部８の値OUTPが使用済みであることを示す−１であると判定し、ステップＳ４０に進んで入力指定部７の値INPが系列の最後の位置(m-1)を示す２であるかどうかを判定する。ここでは、INPは０であり２ではないので、制御部２Ｂは入力指定部７の値INPを１加算して１とした後（ステップＳ４２）、ステップＳ３８に進み入力指定部７の値INPが示す周期計算部６の位置の入力データP(INP)に対応する出力データを出力記憶部８の値OUTPに設定する。ここでは、INPは１であるので、入力データはP(1)であり、それに対応する出力データは前述したように−１であるので、OUTPは−１に設定される。
【０１０４】
続いて、制御部２Ｂは、ステップＳ３９において、出力記憶部８の値OUTPが−１であり、既に系列に使用済みであると判定してステップＳ４０に進む。ステップＳ４０では、制御部２Ｂは、入力指定部７の値INPが系列の最後の位置(m-1)を示す２であるかどうかを判定する。ここでは、INPは１であり２ではないので、制御部２Ｂは入力指定部７の値INPを１加算して２とした後（ステップＳ４２）、ステップＳ３８に進み入力指定部７の値INPが示す周期計算部６の位置の入力データに対応する出力データP(INP)を出力記憶部８の値OUTPに設定する。ここでは、INPは２であるので、入力データはP(2)であり、それに対応する出力データは前述したように−１であるので、OUTPは−１に設定される。
【０１０５】
続いて、制御部２Ｂは、ステップＳ３９において、出力記憶部８の値OUTPが−１であり、既に系列に使用済みであると判定してステップＳ４０に進む。ステップＳ４０では、制御部２Ｂは、入力指定部７の値INPが系列の最後の位置(m-1)を示す２であるかどうかを判定する。ここでは、INPは２であるので、制御部２Ｂは入力指定部７の値INPが系列の最後の位置に達し、全ての入出力データの処理を行ったと判断して、全ての処理を終了する（図１２のステップＳ４１）。このようにして、周期記憶部１０に格納されている周期PR(1)〜PR(3)には、この関数の各周期長の全ての存在数が設定された状態となる。本実施形態では、ｍ＝３の場合であり、上記のようにこの全単射関数の有する各周期数として周期数１を示すPR(1)が１個と、周期数２を示すPR(2)が１個と求まる。
【０１０６】
このようにして、本実施形態によれば、任意の入出力データ数の全単射関数の任意のデータ系列についての部分周期を含めた全ての周期を求めることができる。
【０１０７】
（第３の実施形態）
次に、本発明になる整数系列の周期判定装置の第３の実施形態について説明する。本実施形態の周期判定装置のハードウェア構成は、図１１に示した整数系列の周期判定装置１Ｂと同じ構成であるが、制御部２Ｂによるソフトウェア動作が以下説明するように第２の実施形態と異なる。
【０１０８】
本実施形態は、大きさ３（ｍ＝３）の自然数からなる全単射関数が与えられた場合、その全単射関数が最大周期３（＝ｍ）を有するかの確認方法として、或る初期値（例えば０）を入力値として全単射関数に与えて、その出力（例えば０）が初期値に戻るまで全単射関数の変換を繰り返し、その繰り返しの回数である周期が３（＝ｍ）となった場合には、全ての入出力値を網羅し、最大周期であると判定し、変換の繰り返し回数が３（＝ｍ）より小さかった場合には最大周期ではないと判断する。
【０１０９】
次に、本実施形態のハードウェア資源を利用したソフトウェア動作について、図１４のフローチャートと共に説明する。前述したように、ｍ＝３の場合の最大周期は３である。本実施形態は、例えば、前記ｆ５のように入力０のとき出力２、入力１のとき出力０、入力２のとき出力１のデータが最大周期３となるかどうかの判定を行う。
【０１１０】
図１１において、制御部２Ｂは、まず、データ数記憶部３にデータ数ｍ（ここでは、ｍ＝３）を設定する（図１４のステップＳ６１）。続いて、制御部２Ｂは、周期累計部９の値PSを０に設定（クリア）した後（ステップＳ６２）、順列作成部４に全単射関数の入出力データとして、入力データ（０からｍ−１までの自然数）に対応する出力系列データA(0)〜A(m-1)を設定する（ステップＳ６３）。具体的には、この出力系列データA(0)〜A(m-1)は、０からｍ−１までの重複しない自然数の任意の組み合わせのデータで、ここではｍ＝３であるので、例えば、A(0)＝２，A(1)＝０，A(2)＝１の３個のデータである。ここで、A(0)＝２は、入力０のとき出力２、A(1)＝０は入力１のとき出力０、A(2)＝１は入力２のとき出力１を示す。
【０１１１】
続いて、制御部２Ｂは、順列作成部４に設定した上記の３個の出力系列データA(0)〜A(2)を順列記憶部５の順列S(0)〜S(m-1)にそれぞれ格納する（ステップＳ６４）。ここでは、上記の順列記憶部５には、S(0)＝２，S(1)＝０，S(2)＝１の３個の順列が格納されることになる。これら３個の順列は、所望の１個の全単射関数の３つの入力値に対する出力の状態を記述したものである。
【０１１２】
続いて、制御部２Ｂは、順列記憶部５に格納された順列S(0)〜S(m-1)を、周期計算部６に周期P(0)〜P(m-1)としてそれぞれ設定する（ステップＳ６５）。ここでは、上記の周期計算部６には、P(0)＝２，P(1)＝０，P(2)＝１の３個の周期が設定されることになる。ここで、P(0)＝２は、入力０のとき出力２の周期、P(1)＝０は入力１のとき出力０の周期、P(2)＝１は入力２のとき出力１の周期を示す。
【０１１３】
続いて、制御部２Ｂは、最初の入力データに相当する先頭の位置（この場合、入力位置０）を示す値を入力指定部７の値INPに設定する（ステップＳ６６）。これにより、INPは０となる。続いて、制御部２Ｂは、入力指定部７の値INP（ここでは０）が示す、周期計算部６の位置の入力データに対応する、出力データP(INP)を出力記憶部８の値OUTPに設定する（ステップＳ６７）。ここでは、INPは０であるので、入力データは０であり、それに対応する出力データP(0)は前述したように２であるから、OUTPは２に設定される。
【０１１４】
続いて、制御部２Ｂは、出力記憶部８の値OUTP（ここでは２）を入力指定部７の値INPに設定した後（ステップＳ６８）、周期累計部９の周期の値PSに１を加算して周期数を更新する（ステップＳ６９）。これにより、INPは２、PSは１となる。
【０１１５】
次に、制御部２Ｂは、出力記憶部８の値OUTP（ここでは２）が最初の入力データの値０であるかどうかを判定する（ステップＳ７０）。OUTPの値が最初の入力データの値と等しければステップＳ７１に進み、等しくなければステップＳ６７に戻る。この時点では、OUTPは２であり、０ではないので制御部２ＢはステップＳ６７に戻り、入力指定部７の値INP（ここでは２）が示す、周期計算部６の位置の入力データに対応する、出力データP(INP)を出力記憶部８の値OUTPに設定する。ここでは、入力データINPは２であるので、それに対応する出力データは前述したように１であるから、OUTPは１に設定される。
【０１１６】
続いて、制御部２Ｂは、出力記憶部８の値OUTP（ここでは１）を入力指定部７の値INPに設定した後（ステップＳ６８）、周期累計部９の値PSに１を加算して周期数を更新する（ステップＳ６９）。これにより、INPは１、PSは２となる。
【０１１７】
次に、制御部２Ｂは、出力記憶部８の値OUTP（ここでは１）が最初の入力データの値０であるかどうかを再び判定する（ステップＳ７０）。この時点では、OUTPは１であり、０ではないので制御部２ＢはステップＳ６７に戻り、再び入力指定部７の値INP（ここでは１）が示す、周期計算部６の位置の入力データINPに対応する、出力データP(INP)を出力記憶部８の値OUTPに設定する。ここでは、INPは１であるので、入力データに対応する出力データP(1)は前述したように０であるから、OUTPは０に設定される。
【０１１８】
続いて、制御部２Ｂは、出力記憶部８の値OUTP（ここでは０）を入力指定部７の値INPに設定した後（ステップＳ６８）、周期累計部９の値PSに１を加算して周期数を更新する（ステップＳ６９）。これにより、INPは０、PSは３となる。
【０１１９】
次に、制御部２Ｂは、出力記憶部８の値OUTP（ここでは０）が最初の入力データの値０であるかどうかを再び判定する（ステップＳ７０）。この時点でOUTPが０であり、最初の入力値であると判定される。続いて、制御部２Ｂは周期累計部９の周期の値PSは系列長ｍであるかどうかを判定する（ステップＳ７１）。この時点では、累計計算部９の値PSは系列長ｍ（＝３）に等しいので、制御部２Ｂは最大長（最大周期）であると判定する（ステップＳ７２）。すなわち、ｍ＝３の場合、入力０のとき出力２、入力１のとき出力０、入力２のとき出力１のデータが最大周期であると判定され、その周期長PSは３と求められる。
【０１２０】
なお、ステップＳ７１において、周期累計部９の値PSが系列長ｍでないと判定されたときは、そのときの入力データは最大長ではないと判定される（ステップＳ７３）。
【０１２１】
このようにして、本実施形態によれば、任意の入出力データの大きさの全単射関数の最大周期長を判定することができる。そして、最大周期となる全単射関数を用いて、擬似乱数系列や変換表などを作成することができる。
【０１２２】
ところで、以上の実施形態では、データ数（系列長）ｍが２又は３の場合について説明したが、ｍが９までの周期長の個数は表４に示される。
【０１２３】
【表４】
2011123693.tif 000006
この表４から分るように、入出力データ数（系列長）ｍを有する全単射関数の平均周期長はｍ／２となる。これにより、ｍが２128の場合では、全単射関数の数は２128！個となり、周期長は１が２128！個で、２が２128！／２個、３が２128！／３個で、最大周期となる周期長２128は２128！／２128個存在する。ここで、平均周期長は２128／２となる。
【０１２４】
また、１２８ビットブロック暗号の場合について考えると、１２８ビット鍵の数は２128個であることから、１２８ビットブロック暗号はｍ＝２128の全単射関数全ての関数２128！個のうちの２128個を鍵で選択して用いているといえる。そして、ｍ＝２128の全単射関数の最大周期２128は２128！／２128個存在することから、１２８ビットブロック暗号の鍵の総数から考慮して、全ての鍵から最大周期となるものは、
２128！／２128×２128／２128！＝１
と記述できることから全ての鍵のうちで最大周期となるものの確率は、高々１個である。
【０１２５】
ただし、ここで述べている最大周期とは１２８ビットの出力データの組み合わせが各々１回出現することであり、その出力データの任意の１ビットをそれぞれ抽出した場合に、その系列としてＭ系列のような最大長のビット系列が必ず得られるものではなく、そのためには最大周期となる系列から更に選択が必要である。
【０１２６】
なお、以上の実施形態で判定した最大周期を持つ全単射関数の整数系列を２種類以上組み合わせて用いることで、更に長い周期の擬似乱数系列を生成することもできる。例えば、ｍ１とｍ２の２つの周期の異なる最大長系列において、１以外の約数を持たない互いに素となる周期の組み合わせとなるものを組み合わせれば、最大周期はｍ１×ｍ２となる。
【０１２７】
なお、本発明は以上の実施形態に限定されるものではなく、例えば、図７、図８、図９と共に説明した第１の実施形態の各ステップの処理や、図１２及び図１３と共に説明した第２の実施形態の各ステップの処理や、図１４と共に説明した第３の実施形態の各ステップの処理をコンピュータによるソフトウェア処理により実行させる整数系列の周期判定プログラムも本発明は包含するものである。この整数系列の周期判定プログラムは、図１の制御部２Ａや図１１の制御部２Ｂにより実行される。
【符号の説明】
【０１２８】
１Ａ、１Ｂ  整数系列の周期判定装置
２Ａ、２Ｂ  制御部
３  データ数記憶部
４  順列作成部
５  順列記憶部
６  周期計算部
７  入力指定部
８  出力記憶部
９  周期累計部
１０  周期記憶部
１１  順列数設定部  
１２  検索位置指定部
【図１】
2011123693.tif 000007
【図２】
2011123693.tif 000008
【図３】
2011123693.tif 000009
【図４】
2011123693.tif 000010
【図５】
2011123693.tif 000011
【図６】
2011123693.tif 000012
【図７】
2011123693.tif 000013
【図８】
2011123693.tif 000014
【図９】
2011123693.tif 000015
【図１０】
2011123693.tif 000016
【図１１】
2011123693.tif 000017
【図１２】
2011123693.tif 000018
【図１３】
2011123693.tif 000019
【図１４】
2011123693.tif 000020