📝

離散対数の法則

2024/04/23に公開

SSHのことを調べていて→DH鍵共有が出てきて→離散対数と出てきたので自分なりにまとめてみます。

(a^2)^3 = a^{2\times3} = a^6

指数と指数,つまりここでいう２乗と３乗が掛け算できるという法則です。
ちなみにべき乗する数が変わっても成り立つ法則となります。

(a^4)^2 = a^{4\times2} = a^8

という具合にべき乗する数が変わっても成り立ちます。

x ≡ r(mod\enspace n)

これは以下のような意味になります。
xをnで割った余り　＝　rをnで割った余り

実例で考えてみます。
7 ≡ 4(mod 3)
7 ÷ ３ = ２余り1
4 ÷ 3 = １余り1
両方余りが1になりますね。

また以下のような例も成り立ちます。

(105\enspace\times\enspace 109)\enspace mod\enspace100 ＝ (105\enspace mod \enspace100)\enspace\times\enspace(109\enspace mod\enspace100)

分解して確認してみます。まず左辺を計算してみます。
(105 x 109) mod 100
＝１００４５　÷　100
＝４５
次に右辺を計算してみます。
(105 mod 100) x (109 mod 100)
＝5 x 9
＝４５

同様の式でべき乗を交えても同じように成り立ちます。

A = g^a\enspace mod\enspace n

B = g^b\enspace mod\enspace n

であるならば

A^b ≡ B^a(mod\enspace n)