お世話になります。
下記、問題について教えてください。
============ 問題 =============
線形合同法は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ベストアンサー
- 回答日時:
> (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
> 反証があることから、(1)の仮定は成立しない。
>
> となるのではないでしょうか?
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% …
ご返信ありがとうございました。
>>おそらく、質問者さんは合同式でつまづいているのではないでしょうか?
おっしゃる通りです。この○を法として・・・といった部分が感覚的によく分からなかったんです。(特に演算の仕方が・・(汗))
URLも今後、参考にしてもう少し自分で理解できるようにしたいと思います。
また何かございましたら、ぜひよろしくお願いいたします。
丁寧な解答をありがとうございました!!
No.1
- 回答日時:
乱数には詳しくないのですが、
似たような分野に少し取り組んでいるので、分かる範囲で答えてみます。
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)・・・(1)
(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
反証があることから、(1)の仮定は成立しない。
となるのではないでしょうか?
また、試しに行っていただいた乱数についてですが、
乱数を発生させる過程において、事前にA,C,Pを定めておく必要があるはずだと思うんですが、R_{1}以降のR_{2},R_{3}はこのアルゴリズムに従っていますか?
質問ばかりですみません。
お時間のある時にでも、ご解答いただけますと幸いです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 工学 疑似乱数生成器 3 2023/01/05 02:06
- 数学 「f(z)=1/(z^2-1)に関して ローラン展開を使う場合、マクローリン展開を使う場合、テイラー 3 2022/08/27 19:56
- Ruby 初心者プログラミング 3 2022/10/12 11:31
- 数学 数2Bの数列の問題です。 自分は、 まず数列 an=ar^(n-1)と置き こちらの問題の、y= の 1 2022/07/07 16:26
- その他(プログラミング・Web制作) pythonのプログラムについての質問です。 1 2023/05/26 10:31
- 物理学 大学物理に詳しい方に質問です。 ラザフォードたちが実験で知りたかったことは衝突パラメータbと原子核の 1 2023/03/16 03:39
- 数学 数学Ⅲの関数の極限、関数の連続・不連続に関しての質問でございます。 問題集には、次の関数の〔 〕内の 5 2022/05/19 10:43
- 数学 【大至急】数学のレポートの問題なんですが分からないので是非教えていただきたいです!本当にお願いします 5 2022/07/25 06:52
- 大学受験 推薦入試について教えていただきたいことがあります。 私は、この春高校三年生になります。進路について考 1 2022/04/05 02:04
- 高校 日商簿記3級の勉強中なのですが 精算表が完成せず困っています。 こちらの問題の回答を教えていただきた 2 2023/03/02 09:07
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
SQL文のwhere条件文で使う <> ...
-
1/∞=0は、なぜ?
-
公務員試験 数列の問題です
-
数学で、項を指すとき、例えば2...
-
x/(x+1) = 1 - 1/(x+1)
-
記号(イコールの上に三角形)...
-
説明変数と被説明変数とは何で...
-
x^n+1をx^2+x+1で割った余りを...
-
質問です。 a+b+c=0のとき、...
-
A∩(B-C)=(A∩B)ー(...
-
どうしてa>0, b>0のとき、a=b⇔a...
-
高2数学です α二乗+β二乗=α...
-
√(-1)・√(-1)≠1 を証明し...
-
数IIの問題
-
高2恒等式
-
整数問題 18 海外の数学オリン...
-
【数3 積分法】 上と下の写真の...
-
球ベッセル関数の漸化式
-
楕円体の内側かどうかの判別
-
プール代数の問題なんですけど ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
SQL文のwhere条件文で使う <> ...
-
1/∞=0は、なぜ?
-
京都大学理系 過去問 整数問題
-
Xの二乗-X+1=0 という2次方程式...
-
数学で、項を指すとき、例えば2...
-
数学の等式の証明の最後を省略...
-
数学 剰余の定理
-
化学反応式について教えて下さ...
-
VBAでセルの右下をいちばん下ま...
-
等式記号に似た三本線
-
どうしてa>0, b>0のとき、a=b⇔a...
-
「別々のセルの3つの日付が同じ...
-
nは偶数で、nに45をかけるとあ...
-
x/(x+1) = 1 - 1/(x+1)
-
高2数学です α二乗+β二乗=α...
-
数学における 等価と同値って同...
-
二重根号についてです。 なぜ下...
-
1/7=1/m+1/nを満たすmとnの求め方
-
数学の質問です。(2)の導けとは...
-
定数分離すべきかどうか。
おすすめ情報