離散対数の法則

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

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

$$(a2)3=a2×3=a6 (a^2)^3 = a^{2\times3} = a^6$$

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

$$(a4)2=a4×2=a8 (a^4)^2 = a^{4\times2} = a^8$$

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

合同式

$$x≡r(modn) x ≡ r(mod\enspace n)$$

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

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

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

$$(105×109)mod100＝(105mod100)×(109mod100) (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=gamodn A = g^a\enspace mod\enspace n$$

$$B=gbmodn B = g^b\enspace mod\enspace n$$

であるならば

$$Ab≡Ba(modn) A^b ≡ B^a(mod\enspace n)$$

この最後の式はDH鍵共有でも核となって概念的に使用されているようです。

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