擬似乱数生成について

質問

お世話になります。
下記、問題について教えてください。

＝＝＝＝＝＝＝＝＝＝＝＝　問題　＝＝＝＝＝＝＝＝＝＝＝＝＝

線形合同法はA,C,Pを秘密の定数（Pは素数）,初期値をR1として下記演算によって計算される系列 R1,R2,R3・・・・を擬似乱数として用いる。
R_{i} = A・R_{i-1} + C (mod P)
このアルゴリズムと素数Pがわかっているとき、いくつの乱数値がわかれば次の乱数値が計算できるか？その理由も示せ。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

自分なりに調べてやってみたのですが、いまいちよくよく分かりません。

直感的に、未知数が3個あるので連続した3つの乱数値を各Rとして代入すれば、2元1次方程式を得られ、A,Cが決定できると思ったのですが、どうもうまくいかない・・・

暗号理論の専門書を読んでみたところ、やはりPが判明いてる場合、連続した3つの値で良いようです。もしPが判明していない場合でも、4つ以上の連続した値から次の乱数値が分かるそうです。

完全に混乱しています。どなたか分かる方、解説していただけませんか。
よろしくお願いします。

回答No.2

R_Earl · ベストアンサー

> (mod P)同士の加算を一般的に示すと
> A(mod P)+B(mod P)において、A=4,B=5,P=3とした場合
> （与式）= 4(mod 3) + 5(mod P) = 1 + 2 = 3
> 上記の演算が可能ならば、
> （与式） = 4 + 5 (mod 3) = 9 (mod 3) = 0 ≠ 3
> 反証があることから、（１）の仮定は成立しない。
>
> となるのではないでしょうか？

3を法とする合同式なら、3と0は合同です。
なので一つ目の式も、二つ目の式も、同じ値を意味しています。
それから、計算中に(mod 3)を0個にするのはだめです。
それでは、合同式ではなくなってしまいます。

おそらく、質問者さんは合同式でつまづいているのではないでしょうか？
modはある意味、+や×のような演算子とは別物です。
例えば、a = b (mod N)という合同式では、(mod N)は左辺と右辺両方に作用します。
つまり4 = 7 (mod 3)のような式もOKということです。
(左辺を3で割ると余り1、右辺を3で割ると余り1なので合同)

一つ目の式
> （与式）= 4(mod 3) + 5(mod P) = 1 + 2 = 3
は、正確にはこうなります。
（与式）= { 4(mod 3) + 5(mod 3) } (mod 3) = 1 + 2 (mod 3)= 3 (mod 3) = 0 (mod 3)

二つ目の式
> （与式） = 4 + 5 (mod 3) = 9 (mod 3) = 0
も、正確にはこうなります。
（与式） = 4 + 5 (mod 3) = 9 (mod 3) = 0 (mod 3)

最後の最後まで(mod 3)が無くならない点に注意して下さい。

> また、試しに行っていただいた乱数についてですが、
> 乱数を発生させる過程において、事前にA,C,Pを定めておく必要があるはずだと思うんですが、R_{1}以降のR_{2},R_{3}はこのアルゴリズムに従っていますか？

R_{1} = 3に関しては適当に決めましたが、それ以外は
R_{i} = 4R_{i-1} + 2 (mod 13)に従っています。

R_{2} = 4R_{1} + 2 (mod 13)
R_{2} = 4 × 3 + 2 (mod 13)
R_{2} = 14 (mod 13)
R_{2} = 1 (mod 13)

R_{3} = 4R_{2} + 2 (mod 13)
R_{3} = 4 × 1 + 2 (mod 13)
R_{3} = 6 (mod 13)

参考URL：

http://ja.wikipedia.org/wiki/%E5%90%88%E5%90%8C%E5%BC%8F

お礼

ご返信ありがとうございました。

>>おそらく、質問者さんは合同式でつまづいているのではないでしょうか？
おっしゃる通りです。この○を法として・・・といった部分が感覚的によく分からなかったんです。（特に演算の仕方が・・（汗））

URLも今後、参考にしてもう少し自分で理解できるようにしたいと思います。
また何かございましたら、ぜひよろしくお願いいたします。

丁寧な解答をありがとうございました！！

回答No.1

R_Earl

乱数には詳しくないのですが、
似たような分野に少し取り組んでいるので、分かる範囲で答えてみます。

R_{i} = A・R_{i-1} + C (mod P)の形が、
高校数学の数列でやった、a_{n+1} = 2a_{n} + 1のような漸化式に似ているので、
その時に使った方法で考えてみます。

まず、次の式を用意します。

R_{i} = A・R_{i-1} + C (mod P)
R_{i-1} = A・R_{i-2} + C (mod P)

左辺は左辺同士、右辺は右辺同士で引き算すれば、

R_{i} - R_{i-1} = A(R_{i-1} - R_{i-2}) (mod P)

となります。これでCの無い式に変形できました。
R_{i}, R_{i-1}, R_{i-2}の3つの値が分かるなら、
この方程式からAが決定できるはずです。
次に既知の乱数値とAを用いて、
R_{i} = A・R_{i-1} + C (mod P)の式からCを求められるはずです。

試しにR_{i} = 4R_{i-1} + 2 (mod 13)で実際に乱数を作ってみて
A、Cが決定できるのか試してみました。
R_{1} = 3 (適当に決めました)
R_{2} = 1
R_{3} = 6
です。
R_{i} - R_{i-1} = A(R_{i-1} - R_{i-2}) (mod P)にあてはめて
6 - 1 = A(1 - 3) (mod 13)
5 = -2A (mod 13)
5 = 11A (mod 13)
これを満たすAは、A = 4。
R_{i} = A・R_{i-1} + C (mod P)にA = 4, i = 3を代入して、
6 = 4 × 1 + C (mod 13)
6 = 4 + C (mod 13)
∴C = 2
というわけで、AとCが求められました。
一応、R_{1}～R_{4}でも試してみましたが、こちらでも同じ結果がでました。

間違っている点がありましたらご指摘下さい。

お礼

詳細なご解答ありがとうございました。
早速なんですが、

まず、下記の式は間違っているような気がします。
＞＞　R_{i} - R_{i-1} = A(R_{i-1} - R_{i-2}) (mod P)・・・（１）

(mod P)同士の加算を一般的に示すと
A(mod P)+B(mod P)において、A=4,B=5,P=3とした場合
（与式）= 4(mod 3) + 5(mod P) = 1 + 2 = 3
上記の演算が可能ならば、
（与式） = 4 + 5 (mod 3) = 9 (mod 3) = 0 ≠ 3
反証があることから、（１）の仮定は成立しない。

となるのではないでしょうか？

また、試しに行っていただいた乱数についてですが、
乱数を発生させる過程において、事前にA,C,Pを定めておく必要があるはずだと思うんですが、R_{1}以降のR_{2},R_{3}はこのアルゴリズムに従っていますか？

質問ばかりですみません。
お時間のある時にでも、ご解答いただけますと幸いです。