読者です 読者をやめる 読者になる 読者になる

剰余(あまり)の計算について

tech

最近、仕事で暗号技術を使うことがあり、暗号技術入門として有名なアリス本を読んでみました。

すごくわかりやすいので、おすすめです!


アリス本には公開鍵暗号の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を理解できるわけじゃないですが、わからないところをそのままにしておくのは良くないですよね!
あ、なんか間違いがあったら教えてください。