最近、仕事で暗号技術を使うことがあり、暗号技術入門として有名なアリス本を読んでみました。
すごくわかりやすいので、おすすめです！
アリス本には公開鍵暗号の1つRSAについて計算方法が詳しく書いてあります。RSAでは剰余(あまり)を求める計算を暗号の基盤として行います。「mod」とか「%」で表される計算です。
(「%」はプログラミングの世界だけかな？？)
その剰余の計算で以下のような式が使われています。
(a + b) % x = { (a % x) + (b % x) } % xみなさんはこれをすぐ証明できますか？
僕はすぐには証明できませんでした。そこで気になったら止まらない性分なので、久々に数学脳を呼び起こして証明してみました。
下に僕の証明を書いてあるのですが、もし数学好きな人がいたらこの証明に挑戦してみてください。結構面白いですよ！
証明
以下の式が成り立つことを証明せよ
(a + b) % x = { (a % x) + (b % x) } % x
(a + b) % x = y とおく (1)
(1)を以下のように変形する。zは(a+b)/x の商とする。
(a + b) = zx + y (1')
次に以下の二つの式を考える
a % x = A (2)
b % x = B (3)
(2),(3)を以下のように変形する。mはa/xの商とする。nはa/xの商とする。
a = mx + A (2')
b = nx + B (3')
(1')に(2'),(3')を代入し、各項を移行する
mx + A + nx + B = zx + y
A + B = x(z - m - n) + y (4)
次に(4)の両辺をxで剰余する
(A + B) % x = { x(z - m - n) + y } % x (4')
ここで、(rs + t) % sという式について考える。
被除数(rs + t)はrを除数s倍したものにtを足しているのだから、(rs + t) % sの結果はtとなる。
つまり(4')は以下のようになる。
(A + B) % x = y (4'')
(4'')に(2),(3)を代入する。
{(a % x) + (b % x)} % x = y
(1)より
(a + b) % x = { (a % x) + (b % x) } % x
証明終わり
久々に数学（算数？）してみました。これが解けたところでRSAを理解できるわけじゃないですが、わからないところをそのままにしておくのは良くないですよね！
あ、なんか間違いがあったら教えてください。
