整数ロジスティック写像の逆軌道

計算精度が無制限ならば，2値系列u₀u₁· · ·u_tとx_t+1から，逆軌道x₀, x₁, . . . , x_tを正確に求めることができる．しかし，整数ロジスティック写像は切捨て演 算の影響のため，順軌道と逆軌道は必ずしも一致しない．両軌道の関係を定量 的に調べるために，数値計算を試みた．

定義 3.7. 式(2.4)と式(3.19)において，t ≥0に対し，整数∆X_tを

∆X_t=X_t−X˜_t (3.21)

で定義する．　　　　　　 ¤

順軌道と逆軌道の比較

1. 計算精度N，軌道長T で，区間[1,3×2^N−3]の中から任意に選んだM個の 値それぞれを初期値X₀とおき，順軌道

　　　　　　　　(X₀, X₁, . . . , X_T) を求める．

2. 式(3.20)を用いて，対応する2値系列（逆計算符号列）

　　　　　　　　Y₀Y₁· · ·Y_T を出力する．

3.3. 収束 3. 逆計算はX˜T =XT を初期値にして，逆計算符号を用いて逆計算軌道 　　　　　　　　( ˜X₀,X˜₁, . . . ,X˜_T)

を求める．

4. 最後に，−2^N < k <2^N に対し，∆X_t(0≤t < T)のとる値の頻度 　　　　　　　　f_k=|{t|∆X_t=k, 0≤t < T}|

を求める．　　　　　　 　 ¤ 例として，N = 128, T = 1000に対し，あるX₀に対して上の手順を実施して 求められた∆Xtの取る値の頻度分布を図3.2に示す．図3.2において，横軸は

∆Xtのとる値，縦軸はその頻度である．

図 3.2: 計算精度N = 128ビットで得られた∆Xt=Xt−X˜tの頻度分布．

図3.2から∆X_t = 0となるtの割合は75%以上みてとれる．言い換えれば，

逆軌道の中からランダムにX_tを選ぶと，X_t= ˜X_tとなる確率は0.75以上ある．

逆軌道は順軌道と一致ではないが，その近似にあることが示されている．

この結果をさらに詳細に吟味するために，以下の実験を行った．

計算機シミュレーションによって等確率でN = 128ビットの初期値X₀ を

M = 1000個発生させ，それぞれの値に対して，T = 1000とおいて，上述した

比較手順を実施した．

次に，−2^N < k < 2^N となる各kに対し，第i回目の試行において∆X_t = k となる頻度f_k⁽ⁱ⁾から，平均頻度

f_k= XM

i=1

1 Mf_k⁽ⁱ⁾

第3章 発散，収束，周期性 を求める．また，

　　　　　　d⁽ⁱ⁾₋ = min{k|f_k⁽ⁱ⁾>0} 　　　　　　d⁽ⁱ⁾₊ = max{k|f_k⁽ⁱ⁾ >0} とおき，M回の試行での平均をそれぞれ

d₋ = XM

i=1

1 Md⁽ⁱ⁾₋ ,

d₊ = XM

i=1

1 Md⁽ⁱ⁾₊

とおく．さらに，x⁽ⁱ⁾ =f₀⁽ⁱ⁾, d⁽ⁱ⁾₋, and d⁽ⁱ⁾₊ に対し，x.maxとx.minをそれぞれ 　　　　　　x.max= max{x⁽ⁱ⁾}

　　　　　　x.min= min{x⁽ⁱ⁾} と記す．

以上に述べた比較手順を実施して得られた結果を表3.1に掲げる．

表 3.1: f₀，d₋，d₊とf₀⁽ⁱ⁾，d⁽ⁱ⁾₋，d⁽ⁱ⁾₊ の最大最小値

f₀ f₀.max f₀.min d₋ d₋.max d₋.min d₊ d₊.max d₊.min 755.530 806 694 -86.996 -6 -3713 279.516 25317 6

　　　　　　　　f₀：∆X_t= 0の頻度の平均 　　　　　　　　f₀.max：f₀⁽ⁱ⁾の最大値 　　　　　　　　f₀.min：f₀⁽ⁱ⁾最小値 　　　　　　　　d₋.max：d⁽ⁱ⁾₋ の最大値 　　　　　　　　d₋.min：d⁽ⁱ⁾₋ の最小値 　　　　　　　　d₊.max：d⁽ⁱ⁾₊ の最大値 　　　　　　　　d₊.min：d⁽ⁱ⁾₊ の最小値

表3.1から1000回の試行から逆軌道と順軌道の状態が平均75%以上一致して いることが示されている．図3.2と同等な結果であった．

また，|∆X_t| >0が逆計算に拡大されなく0に収束していることも観察され た．1000回の試行から逆軌道と順軌道で，X˜₀ = X₀となったのが788回あり，

3.3. 収束 f₀に近い．すなわち，対称性を利用して生成した2値系列（式(3.20)）は逆計 算を用いれば，0.75以上の確率で，初期値が求まる．このような2値系列は情 報セキュリティにそのまま応用することは不適切である．

N = 128ビットの整数ロジスティック写像の順計算と逆計算のデータの一例

を付録Bに示す．