そろそろ まとめの講義をします
∼ 無限粒子系，乱数生成とハッシュ関数 ∼
三重大学 教育学部 谷口礼偉
【 １．数学との馴れ初め 】
東山線が「藤が丘」まで開通して暫くたったころ（４０年以上前），
愛知県のある金融機関のオンラインシステムのファイルシステムを担当。
オンライン ファイルシステム
集団ディスク
顧客
ロジカルＩ／Ｏ
ＡＴＭ
口座番号
キャッシュカード
ＬＩＯ
ドライブＮｏ
シリンダＮｏ
フィジカルＩ／Ｏ
トラックＮｏ
セクターＮｏ
ＰＩＯ
アクセス
（ハードディスク上の場所）
● ディスク内に顧客データを均一に分散させるために，
口座番号を，
乱数
を使って作った。
● このファイルシステムは１秒間に何件のデータを処理できるか？
⇒ハードウェアシミュレーション，モンテカルロシミュレーション，
待ち行列理論
ボレル集合体？ ポアソン入力？
ρ /(1 − ρ ) ？
Ｍ／Ｍ／ｓ？
顧客データ
【 ２．古典力学の運動方程式に従う無限個の粒子 】
i − 2 i −1
i 粒子（質量１）
i +1
( qi , vi ) : i 番目の粒子（質量１）の位置と速度
初期配置 x = ( qi , vi ) i , L < q−1 < 0 ≤ q0 < q1 < L
時刻 ｔ での配置
x (t ) = ( qi (t ), vi (t )) i
ニュートンの運動方程式
dqi (t )
dt = vi (t )
dv (t )
i
= −Φ ′( qi (t ) − qi −1 (t )) + Φ ′( qi +1 (t ) − qi (t ))
（３．１）
dt
(qi (0), vi (0)) i = (qi , vi ) i
？
Ll.exe
Φ (r ) : ポテンシャル
lim r→+0 Φ ( r ) = ∞ ,
lim r→∞ Φ ( r ) = 0
lim r→+0 − Φ′( r ) = ∞ ,
lim r→∞ − Φ′( r ) = 0
Φ′( r ) < 0 より粒子間には斥力が働く
どのような初期配置 ( qi (0), vi (0)) i = ( qi , vi ) i に対して，（３．１）は永続的な解を持つか？
［それまでの結果］ ハードコア粒子（一定巾の硬い核を持っている粒子）に対して調べられていた。
（各粒子は一定巾の核を持っているので，有限区間に入る粒子数は制限される）
（続き）
Ａ
【 ２．古典力学の運動方程式に従う無限個の粒子 】
∆ n = [− n, n ]
区間
区間内のエネルギー
N ( x; ∆ n ) =# {i | qi ∈ ∆ n }
区間内の粒子数
H ( x; ∆ n ) = 2 −1 ∑q ∈∆ vi2 + ∑q ∈∆
i
n
i
n
or qi +1∈∆
Φ (qi +1 − qi )
X γ = { x | sup n=1, 2,L (2n) −1 N ( x; ∆ n ) < ∞ , sup n=1, 2,L (2n) −1−γ H ( x; ∆ n ) < ∞} , 0 ≤ γ < 1
平均粒子数
平均エネルギー
ある γ に対して x ≡ ( qi , vi ) i ∈ X γ ならば，（３．１） は 以下を満たす解を持つ。
(i) L < qi −1 (t ) < qi (t ) < qi +1 (t ) < L ,
(ii) ( qi (t ), vi (t )) i ∈ X γ ,
(iii) ∃δ > 0 s.t. ∀i ∀t
lim k →∞ σ i +k o L o σ i +1 o σ i (t ) = ∞
lim k →∞ σ i −k o L o σ i −1 o σ i (t ) = ∞
ただし σ i (t ) = inf{s ≥ t | qi +1 ( s ) − qi ( s ) ≤ δ }
i i +1
s ≥ t , qi +1 ( s ) − qi ( s ) ≤ δ
〔証明の考え方〕
有限区間 ∆ K = [ − K , K ]
の外にある粒子を固定しておいて運動方程式を解く。 ( K = 1,2,L)
それらの解 {qi (t )}i は t ∈ [−1,0] で， i ごとに一様に有界で， t = [−1,0] に対して同程度
連続であるので，Ascoli-Arzela の定理と，対角線論法で，全ての i で収束する部分列を抜き出
す。
K
【 ３．離散時間 完全非対称 単純 排除過程 （交通流の確率モデル） 】
確率 α
確率 α
確率 α
α
α
α
α
α
α
確率 α
i −1 i i +1
無限個の粒子は，時刻が ｔ から ｔ＋１ に変るとき，左側が空いていれば，
それぞれ独立に確率 α (0<α<1) で左に移動する。
Synchronous Totally Asymmetric Simple Exclusion Process, STASEP
X = {0,1}Z
i
x ≡ (L x −1 x0 x1 L) ∈ X
xi = 1
xi = 0
座標 i に粒子有り
座標 i に粒子無し
[ai L a j ] j = {(L x −1 x0 x1 L) ∈ X | xl = al , i ≤ l ≤ j }
P( x, i[ai L a j ] j )
座標 i から j までの配置が ai L a j
であるような X の要素の全体（筒集合）
時刻 t での配置が であったとき，
時刻 t+1 での配置が 集合 i [ai L a j ] j に入る確率（推移確率）
X 上の離散時間マルコフ過程 (MP) が定義される
？
初期配置から出発して，時間が経過したとき，どのような定常状態に落着くか？
（＝ 定常状態に現れる X 上の確率測度
µ
を全て決定せよ）
µ ( A) = ∫ µ (dx ) P ( x, A)
X
［それまでの結果］ ない。（ＳＴＡＳＥＰという名称も当時はなかった）
（続き） 【 ３．離散時間 完全非対称 単純 排除過程 （交通流の確率モデル） 】
β,
Ａ
0<γ < ∞
を， 1 − α = (1 − β )(1 − βγ ) を満たす数とする。 (0 < β < α )
X 上の確率測度
π γ を以下で定める：
(1 − βγ )( β / α )
f ( n ) = −1
n−2
n
γ (1 − β ) ( βγ / α )
#10
#11
j −i
1 − βγ βγ
γ
# 1
(1 − β ) 00
π γ ( i [a i L a j −1 0] j ) =
γ γ α
1+ γ
#10
#11
j −i
π ( [a L a 1] ) = 1 (1 − β )#00 1 1 − βγ βγ
i
i
j −1
j
γ
γ γ α
1+ γ
n =1
n = 2,3, L
f (3) f (1) f (1) f (2)
# uv ([a i L a j ]) = # {l | al a l +1 = uv}
●
●
π γ , 0 < γ < ∞,
●
πγ
●
πγ
(最終的な状態)
はマルコフ過程 (MP) の定常確率である。
(1 − βγ )( β / α )
では，隣り合う粒子間の距離の分布は f (n) = γ −1 (1 − β )n −2 ( βγ / α )n
であり，これらは互いに独立である。(renewal measure)
では，位置 i に粒子が存在する確率は
0 < α ≤ 1 / 2 の時は以下の定常状態に限られる：
i) 状態 π γ
iv) 状態
以下では粒子が全部詰まっている；
n = 2,3,L
1
，粒子の平均速度は βγ である。
1+ γ
ii) 状態 π 0（粒子が何もない）， π ∞ （全ての場所に粒子が詰まっている）
iii) 状態 Θn（座標 n
n =1
n + 1 以上には粒子が無い）
i)∼iii) が混じり合った状態
● 1 / 2 < α < 1 の時は，“に限られる”の部分の証明がまだない。
〔 “以下の定常状態に限られる” の部分の証明の考え方 〕
α
coupled Markov 法による。
●●
●
t
⇒ t +1
● ●
●
●●
● α
●●
●
1-2α
【 ４．１次元格子上の 連続時間 最隣接作用 排除過程 】
i −1 i i +1
x ≡ (L x −1 x0 x1 L) ∈ X
X = {0,1}
Z
xi = 1
xi = 0
座標 i に粒子有り
座標 i に粒子無し
各粒子は，指数分布
F ( t ) = 1 − e − λt
ただし
2α （隣り合う粒子数が１の時）
2 β （隣り合う粒子数が０の時）
λ=
α > β ：斥力
α < β ：引力
に従う独立なタイマーを持ち，ベルが鳴ったら，コインを振り，ジャンプする方向（+1, -1）を決める。
そこに粒子がなかったら，実際にジャンプし，タイマーをリセットする。（同時にジャンプする可能性は測度０でない）
X 上の連続時間マルコフ過程(MP)c
( Ωf )( x ) =
∑{αχ
i∈Z
11
( xi −1 xi ) + βχ01 ( xi −1 xi ) + αχ11 ( xi +1 xi +2 ) + βχ 01 ( xi +1 xi +2 )}[ f ( x i ,i +1 ) − f ( x )]
1
0
χ ab (uv ) =
？
if uv = ab
if uv ≠ ab
x i ,i +1 ≡ (L x0 LL xi −1 xi +1 xi xi +2 L)
初期配置から出発して，時間が経過したとき，どのような定常状態 µ に落着くか？
∫
X
(Ω f )( x )dµ ( x ) = 0
［それまでの結果］ α = β （単純排斥過程）の場合が調べられている。
（ ⇒ exchangeable measure :ベルヌーイ測度，あるいは，これらが混じり合った状態，になる。）
問題点： α ≠ β の時，coupled Markov法が使えない。
（続き） 【 ４．１次元格子上の 連続時間 最隣接作用 排除過程 】
Ａ
0 < ρ < 1 とし， q, q′ ∈ (0, 1)
qq′ /[(1 − q)(1 − q′)] = β / α
X 上の確率測度
µρ を
を，以下を満たす数とする：
(1 − q′) /(1 − q′) = (1 − ρ ) / ρ
µ ρ ([1]) = ρ
µρ ([0]) = 1 − ρ
µ ρ ([ai L a j 00]) = qµρ ([ai L a j 0])
µ ([a L a 11]) = q′µ ([a L a 1])
j
ρ
i
j
ρ i
により定める。
f ρ (3) f ρ (1) f ρ (1) f ρ ( 2)
●
µ ρ , 0 < ρ < 1,
はマルコフ過程 (MP)c の定常確率である。
q′
▲ µ ρ では，隣り合う粒子間の距離の分布は f ρ (k ) =
k −1
(α / β ) q ′q
であり，これらは互いに独立である。(renewal measure)
▲
µρ
では，位置 i に粒子が存在する確率は ρ
● (MP)cの定常状態は以下に限られる：
i) 状態 µ ρ , 0 < ρ < 1
ii) 状態 µ 0（粒子が何もない）， µ1 （全ての場所に粒子が詰まっている）
iii) 状態
i), ii) が混じり合った状態
k =1
k = 2,3, L
である。
〔証明の考え方〕
初期状態 ν 0 = ν から出発したとき，
[− n, n ] 上の相対エントロピー
H ∆n (ν t ) =
∑
ν t (ζ ) logν ((ν t (ζ ) / µ ρ (ζ ))
ζ ≡ − n [ a− n Lan ]n
は，境界からの影響を除けば ｔ に関し
て単調性がある。
【 ５．エントロピー法の 離散時間 最隣接作用 排除過程への応用 】
● 再隣接作用が，左右対称な場合は旨くいった。
● 再隣接作用が，左右非対称な場合は証明の基本になる不等式の証明まで。（見並）
【 ６．新しい乱数生成法の起源 】
sin x
x3 x5 x7 x 9
x 2 n −1
n −1
= x−
+
−
+
− L + ( −1)
+ L （無限に続く）
3! 5! 7! 9!
( 2n − 1)!
ラジアン
マクローリン展開
● コンピュータでは無限に続く項を扱えないので，公式を途中で打ち切る:
sin x ≈
=
x3 x5 x7 x9
x 2 n −1
n −1
x−
+
−
+
− L + ( −1)
3! 5! 7! 9!
( 2n − 1)!
F1 ( x ) + F2 ( x ) + F3 ( x ) + L + Fn ( x )
単精度で計算
（有効桁数は約６桁）
n = 10
n = 20
n = 26
Aitecsin.exe
（続き）
【 ６．新しい乱数生成法の起源 】
x = 22 での sin x ≈ F1 ( x ) + F2 ( x ) + F3 ( x ) + L + F30 ( x ) を見る。
単精度計算 （有効桁数 ： 約６桁）
F1
F2
F3
F4
F5
F6
F7
F8
F9
F10
F11
F12
F13
F14
F15
F16
F17
F18
F19
F20
F21
F22
F23
F24
F25
F26
F27
F28
F29
F30
22.0000000000000
-1774.66662597656
42946.9335937500
-494912.281250000
3326910.25000000
-14638405.0000000
45416588.0000000
-104674424.000000
186258896.000000
-263594464.000000
303761248.000000
-290554240.000000
234380416.000000
-161595616.000000
96320536.0000000
-50128108.0000000
22975382.0000000
-9344609.00000000
3395488.50000000
-1108918.00000000
327266.031250000
-87705.8437500000
21439.2070312500
-4799.52636718750
987.657653808594
-187.461288452148
32.9213600158691
-5.36496257781982
0.813484311103821
-0.115057393908501
計
-16.1806468963623
倍精度計算 （有効16~17桁）
22.0000000000000
-1774.66666666667
42946.9333333333
-494912.279365079
3326910.32239859
-14638405.4185538
45416591.1703848
-104674429.173649
186258910.735463
-263594481.859545
303761260.047666
-290554248.741246
234380427.317938
-161595622.253393
96320543.3135989
-50128110.7137439
22975384.0771326
-9344609.99439681
3395488.91688292
-1108918.10780792
327266.075718922
-87705.8586090578
21439.2098822141
-4799.52709666588
987.657786898931
-187.461321121209
32.9213640865984
-5.36496303633455
0.813484370171028
-0.115057403612735
-0.0223788063394826
有効桁数 ： 約６桁
単精度での計算
・ 個々の Fi ( x ) はＯＫ
・ F1 ( x ) + L + F30 ( x ) はダメ
⇓
F8 ,L, F14 の有効桁が，
和をとることにより消滅
⇓
桁落ち誤差（cancellation
error）の発生
【 ７．sin x をホーナー法で計算する 】
sin x ≈
桁落ちが起こりにくい
計算法とされている
x3 x5 x7 x9
x 2 n −1
n −1
x−
+
−
+
− L + ( −1)
3! 5! 7! 9!
(2n − 1)!
x 2
x2
x2
⋅⋅⋅
1 −
( n = 30)
= x 1−
⋅ ⋅ ⋅ 1 −
2 ⋅ 3 ( 2n − 4)( 2n − 3) ( 2n − 2)( 2n − 1)
G
G
を
G0 = 1 ,
と計算する。
Gk = 1 −
1
2
x2
× Gk −1 ,
(2n − 2k )( 2n − 2k + 1)
ホーナー法
PPTlinkAitec.exe
G 30 = x ⋅ G 29
［例］
x−
x 3 x5
x2
x2
1 −
+
= x 1 −
3! 5!
2 ⋅ 3 4 ⋅ 5
（続き） 【 ７．sin x をホーナー法で計算する 】
x = 22, n = 30
単精度計算
G0
G1
G2
G3
G4
G5
G6
G7
G8
G9
G10
G11
G12
G13
G14
G15
G16
G17
G18
G19
G20
G21
G22
G23
G24
G25
G26
G27
G28
G29
G30
（有効桁数 ： 約６桁）
1.0
0.858562231063843
0.869817018508911
0.858252048492432
0.849276483058929
0.838804006576538
0.827388942241669
0.814775109291077
0.800832748413086
0.785380363464355
0.768217027187347
0.749111294746399
0.727800428867340
0.703987061977386
0.677339255809784
0.647492229938507
0.614056348800659
0.576633512973785
0.534848988056183
0.488405317068100
0.437171012163162
0.381313532590866
0.321486204862595
0.259050846099854
0.196278139948845
0.136376187205315
0.0832489654421806
0.0406547784805298
0.0161543600261211
-0.303118377923965
-6.66860437393188
}
桁落ちが連続して発生
倍精度計算
（有効16~17桁）
1.0
0.858562244301578
0.869817003057029
0.858252043946262
0.849276491556607
0.838803991406511
0.827388974557504
0.814775086176766
0.800832756712346
0.785380368633015
0.768217013159525
0.749111312841289
0.727800393832445
0.703987066710165
0.677339261091174
0.647492255518142
0.614056340306921
0.576633520358191
0.534848960244392
0.488405342374929
0.437170986406034
0.381313574793800
0.321486138969856
0.259050993993284
0.196277685302889
0.136378184667289
0.0832355364032255
0.0408095328771154
0.0124093043738067
-0.00101721948707606
-0.0223788287156735
x 2
x2
x2
1 −
⋅⋅⋅
⋅ ⋅ ⋅ 1 −
x 1 −
2 ⋅ 3 ( 2n − 4)( 2n − 3) (2n − 2)( 2n − 1)
G
G
1
2
● k = 26,27,28 あたりで，桁落ちが発生
Gk = 1 −
x2
× Gk −1
( 2n − 2k )( 2n − 2k + 1)
計算直後の有効桁
= ( − )0.0 • • • • • • • ????????
{
桁落ち
計算機に記憶される桁
【 ８． sin x の Horner 法計算値から乱数を作る 】
（１） x=22 から x=26 までを 19999 等分し，
各点で sin x の 単精度 Horner法 計算をする。
（２） 得られた値の上位３桁の数字を捨て，
残った桁から続けて4桁の数をとる。
-6.66860437393188
-7.80057716369629
-7.64557886123657
4.75384521484375
.....
8604
0577
5578
3845
得られた４桁整数値を，（Ｘ座標，Ｙ座標）として点表示
乱数とは？
・ 独立性
出現する数の間には因果関係が無い
・ 一様性
発生可能な数値が同程度に発生される
数学的には，
Ω = {0, 1, 2, L, k , L, n − 1}
（乱数値の空間）
X i , i = 0, 1, 2, L （i 番目の乱数値を表す確率変数）
としたとき
P( X 1 = k1 , X 2 = k 2 , L, X l = kl ) = P( X 1 = k1 ) P( X 2 = k 2 ) L P( X l = k l )
P( X i = k ) =
1
n
∀i , ∀k
【 ９．桁落ちを人為的に発生させる 】
計算直後の有効桁
x2
Gk = 1 −
× Gk − 1
(2 n − 2k )( 2n − 2k + 1)
= ( − )0.0 • • • • • • • ????????
{
桁落ち
実際に記憶される桁
桁落ち を，
0.0 • • • • • • • ??
桁落ちのメカニズム
←シフト
0.0 • • • • • • • ??
シフト
シフトを人為的に発生させる
±
±
1.4567 ?? × 10 ∈ [1,2)
0
＊………仮数部(52ビット) ………
←シフト
仮数部
指数部
0.001234567 = 1.234567 × 10 −3
（仮数部シフトの例）
指数部
と考える
⋅ ⋅ ⋅ ×20
………………………………….0
（＊が落ちる）
（0が入る）
【 １０．人為的な桁落ちを利用した乱数生成法（ＳＳＲ） 】
Simplified Shift-Real random number generator
人為的な桁落ちを利用して，新しい乱数生成法を構成する。
Φ x (t )
i)
SSR計算
t , x ∈ [1,2) に対し t × x を計算し，（→ 結果を w とおく）
ii) w の仮数部の全ビットを１ビット左にシフト し，
ＭＳＢ
w
±
指数部(11ビット)
シフトを人為的に発生させる
ＬＳＢ
＊………………仮数部(52ビット) …………………
左シフト
左シフト
左シフト
（0が入る）
（＊が落ちる）
w
±
⋅ ⋅ ⋅ ×20
………………..…………………………………….0
ＭＳＢ
ＬＳＢ
iii) w の指数部を × 20 となるように設定する（⇒ w ∈ [1,2) ）。
（１）
Φ 24
x ( w0 ) = Φ x (⋅ ⋅ ⋅Φ x (Φ x ( w0 )) ⋅ ⋅⋅)
1444
424444
3 の上位３桁を棄て，
24
続く４桁を乱数値とする。 1.7758451
（２）
5845
x を x1 , x 2 , x3 ,L と変化させて，多くの乱数値を得る。
2 xt − 2 xt + 1 if 1 ≤ xt < 2
Φ x (t ) =
if 2 ≤ xt < 4
xt − xt + 1
【 １１．乱数生成法ＳＳＲの解析 】
2 xt − 2 xt + 1 if 1 ≤ xt < 2
Φ x (t ) =
if 2 ≤ xt < 4
xt − xt + 1
SSR計算
Φ x (1)
Φ 3x (1)
Φ 14
x (1)
Φ 7x (1)
x
x
x
x
SSR乱数の分布
PPTlinkAitec.exe
24
Φ 24
x (1.e ) ≡ Φ x (1.271828 L)
の上位３桁を棄て，続く４桁を乱数値とする。
● x を x1 , x 2 , x 3 ,L と，区間 [1,2) 内を一様に変化させた時の乱数値の分布
⇓
1.002
Ｋ改良
1.001
⇒
1
0.999
24
Φ 24
x (1.e) − Φ x (1.π )
0.998
0.997
0.996
0
0.2
0.4
0.6
乱数値の分布
0.8
1
1.002
1.001
1.000002
1.000001
1
0.999
0.998
1
0.999999
0.999998
dist of J(y)
0.997
0.996
0.999997
0.999996
0
0.2
0.4
0.6
0.8
Ｋ改良後(SSRK)の乱数値分布
1
【 １２．SSRアルゴリズムの単純化（SSI） と [1,2) 上のβ変換】
（単純化）
SSI （Simplified Shift-Integer）
2 xt − 2 xt + 1 if 1 ≤ xt < 2
Φ x (t ) =
if 2 ≤ xt < 4
xt − xt + 1
M β (t )
M β (t ) , t ∈ [1,2)
M β : [1,2) → [1,2)
の代わりに，
β = 23 ×1.2781L
M β (t ) = β t − β t + 1 , β > 1
≡ β t mod [1,2)
t
（[1,2) 上のβ変換）
を使う。
xn = 1 +
n
, n = 0,1, L ,19999
20000
yn
y n = ( M 23 x )16 (1) ,
β = 23 xn
n
n = 0,1,2, L
y n = ( M 23 x ) (1)
16
xn
n
xn , n = 0,1, L
1
M 23 x
M 23 x
M 23 x
n
n
n
144444444
42444444444
3
16 回
y n = ( M 23 x )16 (1)
n
【 １３．ＳＳＩ３２： [1,2) 上のβ変換を利用した乱数生成 】
SSI32K乱数生成法
あらかじめ整数 x, y
を固定しておく。
p, q, r (< p ), s(< q) を素数とし， k = 0 ,1, 2 , 3,⋅ ⋅ ⋅
に対し
( rk , s k ) = ( rk mod p , sk mod q )
を計算し，
xk = ( x ⊕ rk ) ,
⊕ ：XOR（排他的論理和）
とおく。
M 2232 x ( w0 )
k
y k = ( y ⊕ sk )
−M
23
2 2 yk
(v0 ) の b17 Lb48 を k 番目の乱数値 として使う。
SSIK乱数の周期
SSIK乱数 (32 bits)
64
47448
xxx … xxx ooooooo…ooooooo xxx … xxx
b1
非再帰的乱数生成法
（ｋ番目の乱数を直接
生成する）
b16 b17LLLLL
b48 b49
b64
= period of {xk } × { yk }
= pq
≈ 1.18 × 10 21
p = 34359738337
q = 34359738319
【 １４．乱数の応用：銀行の窓口端末（モンテカルロシミュレーション） 】
ある銀行の窓口では，２人のテラーがそれぞれの端末を通して，１台の現金処理機を共有している。
現金処理機を使う取引の割合41％
⇓
乱数を使って，0.41 の確率 で
現金処理機を使わせる
顧客
現金処理機
0.56 人／分 （平常日）
0.91 人／分 （繁忙日）
乱数を使って，毎秒 λ=0.0152
の確率で到着させる
テラー端末
⇓
Ａ：現金処理機を使わない取引の平均処理時間
Ｂ：現金処理機を使う取引の一件の平均処理時間
（Ｂの場合の現金処理機の占有時間
YOSI2008_4.exe
57秒／件
78秒／件
32秒／件）
【 １５．ハッシュ関数への応用 】
任意長のバイト列データ
入力
ハッシュ関数
出力
MD5 : 128ビット
SHA1 : 160ビット
RIPEMD-160 : 160ビット
さらに長いビット長もある
固定長の乱数値
ハッシュかんすうハッシュ関数 【 hash function 】
メッセージダイジェスト関数 / message digest function
ハッシュアルゴリズム / hash algorithm
与えられた原文から固定長の疑似乱数を生成する演算手法。
生成した値は「ハッシュ値」と呼ばれる。「要約関数」「メッセージダイジェス
ト」とも呼ばれる。
通信回線を通じてデータを送受信する際に，経路の両端でデータのハッ
シュ値を求めて両者を比較すれば，データが通信途中で改ざんされてい
ないか調べることができる。
不可逆な一方向関数を含むため，ハッシュ値から原文を再現することは
できず，また同じハッシュ値を持つ異なるデータを作成することは極めて
困難である。
通信の暗号化の補助や，ユーザ認証やデジタル署名などに応用されて
いる。
hashSample.exe
【 １６．小型ハッシュ関数 MB32hash 】
B=
入力バイト列
1
2
B1
B2
N-2 N-1 N (byte)
LLL
BN − 2 BN −1 BN
MBnhash, n=160, ..., 4096
に拡張可能
out put
→ ζ : ３２ビット擬似乱数
MB32hash
1. e ≡ 1 +
1 1 1 1
1 + + + + L = 1.27181L
10 1! 2! 3!
e = 2.7181L
有理係数の代数方程式の解とな
らないような数（超越数）
MB32hash
Stage 1. B の圧縮
⊕ ：XOR（排他的論理和）
w0 = 1. e , wk = M 231.e ( wk −1 ⊕ Bk ) ,
B1
1.e = w0
Stage 2.
y
⊕
B2
M 231. e
⊕
B3
M 231. e
の撹乱 （擬似乱数の作成）
y
y
y = wN ⊕ N
M 23 y
⊕
BN
M 231. e
⊕
M 231. e
= wN
⊕
z = ( M 2 3 y )16 ( y )
M 23 y
M 23 y
144444444
42444444444
3
z = ( M 2 y )16 ( y )
16 times
３２−ビット ハッシュ値の取り出し
N
ζ = 2 32 ( 211 z − 211 z )
3
y
【 １７．アルゴリズムの観点から見たMB32hashの安全性 】
圧縮過程
1.e = w0
B1
B2
B3
BN
⊕
⊕
⊕
⊕
M 231. e
２つの 入力 B ，B^ に対して何時
M 231. e
M 231. e
N
M 231. e
= wN
⊕
y
wN = wˆ Nˆ となるか？
wN = wˆ Nˆ となるためには， γ ≡ 231.e は，変数 γ~ に関する以下の代数方程式群の解の
中に含まれている必要がある :
γ~ N (1.e + t1 ) + γ~ N −1 ( ~p1 + t2 ) + L + γ~( ~p N −1 + t N ) + ~p N
ˆ
ˆ
= γ~ N (1.e + tˆ ) + γ~ N −1 ( q~ + tˆ ) + L + γ~( q~ + tˆ ) + q~
1
1
しかしながら， γ
B=B^ 以外で
撹乱過程
２つの
2
Nˆ −1
Nˆ
1 1 1 1
= 2 3 1 + 1 + + + + L
10 1! 2! 3!
Nˆ
t i and tˆj are of the form ± 0.0000000b8 b9 Lb15 000 L ,
~pi and q~ j are in {−9,−10,L,−19} .
( → totally, (2 8 × 2) N + Nˆ × 11N + Nˆ equations)
は超越数であるので ,
wN = wˆ Nˆ となることはない。（⇒ 圧縮過程は安全である）
z = ( M 23 y )16 ( y )
ハッシュ値の取り出し
ζ = 2 32 ( 211 z − 211 z )
y, yˆ に対して何時 ζ = ζˆ となるか？
y − yˆ > 2−91 を満たす y , yˆ を見つけようとすると y , yˆ に関する５次以上の
代数不等式を解かなければならない。
⇒ ５次以上の代数方程式を解くことは一般に困難 （⇒ 撹乱過程は安全）
• 仮に
y , yˆ を見つけても， y , yˆ を生じる B ，B^ を見つけることは大変難しい。
【 １８．アルゴリズムの実装という観点から見たMB32hashの安全性 】
• 圧縮過程での
wk −1 ⊕ Bk の取り方 ⇒
1.b1 L b7 (b8 ⊕ c1 ) L (b15 ⊕ c8 )b16b17 L b31
(MBnhash)
⊕ で触られれない
部分を確保する
1.b1 L b23 (b24 ⊕ c1 ) L (b31 ⊕ c8 ) の時，ζ = ζˆ とできる
B=0x0000
⊕ B1
mul. x
w0 = a 2cb4411
→ a 2cb44(1 ⊕ 0)(1 ⊕ 0) = a 2cb4411
→ 6785e38a890 f 0921
shift 4
→ 785e38a890 f 0921 OR
→
f 85e38 a890 f 0921 cut
→ f 85e38 a8 = w1
⊕ B2
mul. x
cut
→ f 85e38(a ⊕ 0)(8 ⊕ 0) = f 85e38a8
→ LL
→ df 0d 49ac = w2
B1
mul. x
w0 = a 2cb4411 ⊕
→ a 2cb44(1 ⊕ 0)(1 ⊕ 1) = a 2cb4410
→ 6785e389e643c510
ˆ
B^=0x0136
shift 4
→ 785e389e643c510 OR
→
f 85e38 9e643c510 cut
→
f 85e38 9e = wˆ 1
B2
mul. x
⊕
→ f 85e38(9 ⊕ 3)(e ⊕ 6) = f 85e38a8(B の時と同じ)
→ L → wˆ 2 ( = w2 )
ˆ
• 撹乱過程で y が y + η に変化するとき，
η > 2 −91 ならばハッシュ値 ζ に影響がでる
数値計算で ζ = ζˆ となる
y, yˆ を精密に求めても，
３２ビットに丸める時点で ζ = ζˆ が狂ってしまう
数値計算は役に立たない
【 １９．[1,2) 上のβ変換の性質 】
β >1
元々のβ変換
Tβ ( s ) = ( β s mod 1) = β s − β s
Tβ : [0,1) → [0,1),
β > 1, 0 ≤ α < 1
Linear mod １ 変換
β >1
[1,2) 上のβ変換
Mβ
M β (t ) = ( β t mod [1,2) ) = β t − β t + 1
M β : [1,2) → [1,2),
Tβ ,α の性質
Tβ ,α
Tβ ,α ( x) = ( β x + α mod 1) = β x + α − β x + α
Tβ ,α : [0,1) → [0,1),
β = β + βˆ
Tβ
とすると M β (t ) = Tβ , βˆ (t − 1) + 1 , t ∈ [1,2) .
X = [0,1) , ( X , B, λ ) : 確率空間
∑
(Parry) hβ ,α ( x) =
x < T βn,α (1), n ≥ 0
1
β
n
−
ν β ,α ( E ) = ∫ hβ ,α ( x)dλ ( x )
E
∑
x < Tβn,α ( 0 ), n ≥1
1
β
n
Tβn,α ( t ), n = 1,2,3, L ,
とすると，
の分布を記述する
は， Tβ ,α の不変測度である。
• h ( x) を利用してSSI乱数の分布の関数表現を調べる（西村）
• SSR写像の不変測度について h ( x) のような表現を調べ，乱数の分布を調べる（山口）
β ,α
β ,α
まとめの講義を終わります
© Copyright 2024 ExpyDoc
