📝

離散対数の法則

2024/04/23に公開

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

指数法則|べき乗のべき乗

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

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

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

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

合同式

x ≡ r(mod\enspace n)

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

実例で考えてみます。
7 ≡ 4(mod 3)
7 ÷ 3 = 2余り1
4 ÷ 3 = 1余り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
=10045 ÷ 100
=45
次に右辺を計算してみます。
(105 mod 100) x (109 mod 100)
=5 x 9
=45

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

A = g^a\enspace mod\enspace n
B = g^b\enspace mod\enspace n

であるならば

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

https://zenn.dev/isosa/articles/448bb0e013a5b0

Discussion