札幌の予備校・塾|大学受験(英語・数学)は札幌のマンツーマン個別指導塾、高上へお電話ください!大学受験において偏差値を上げる塾ですので、生徒の地力を底上げします。札幌駅、大通り駅にある予備校・塾のマンツーマン個別指導塾高上は、大学受験の英語、数学、物理、化学を静かな環境の個室で指導します。周りの声が邪魔になることはありません。英作文の添削、スカイプでの指導も全国どこからでも随時受け付けております。
お気軽にお問い合わせください。
TEL:080-1885-3972
受付時間:10:00~21:00
年中無休(相談などについては要予約)
※指導中はお電話に出られません。
お問い合わせページよりご連絡ください。
公開日:2020年9月28日
最終更新日:2020年10月3日

はじめに

こんにちは。「ャに」と申します。
これから数学に関する記事を書いていくことになりました。
代表に「自由に書いてよい」と言われたので、医学部受験予備校のウェブサイトですが、まずは自分の好きなコンピュータ科学に関わる数学の話をしていきたいと思います。

テーマ

最初のテーマは「RSA暗号の数学」です。
RSA暗号はインターネットで広く使われている現代暗号のひとつです。
執筆時点でRSA暗号はこのサイトでも使われています (PCでこのサイトを見ている方は鍵マーク (正確には錠ですが) をクリックして詳細情報を表示すれば、どこかに「RSA」と書かれた文字列を発見できるでしょう)。

RSA暗号自体の詳しい説明はまだしません。
この連載「RSA暗号の数学」ではRSA暗号で使われる数学を丁寧に解説していきます。
意欲のある高校生がこの連載を読み終わった後、平均的な情報系大学生以上にRSA暗号の数学的理解が得られることを目標とします。
一部、高校数学では扱われない発展的な内容を扱うことがあるかもしれませんが、なるべくわかりやすく説明します。
現行課程の「数学I」、「数学II」の一部と「数学A」の整数の単元を既習と仮定して進めていきます。

合同式

コンピュータの世界の「数」は基本的に「有限」でその大きさには限りがあるので、基本的にコンピュータは有限の整数を扱います。
RSA暗号を含むほとんどの現代暗号は余りの世界を考えます。

非負整数 \(n\) を正の整数 \(p\) で割った余り \(r\) を考えると \(0 \leq r \lt p\) が成り立ちます。
この余りに注目すれば、集合 \(\{0, 1, \dots, p – 1\}\) の元 (要素) だけでいろいろできそうです。

ここで便利な記法を用意しましょう。

合同式の定義
整数 \(a, b\), 正の整数 \(m\) に対して、\(a – b\) が \(m\) の倍数のとき、$$a \equiv b \pmod{m}$$と表記する。
このような式を合同式といい、\(a, b\) は \(m\) を法として合同であるという。

合同式に慣れるために、時間に余裕があって意欲のある方は以下の問題を解いてみましょう。
解かずに解説を読んでいただいてもかまいません。

問題

(1) 基本的性質

\(a \equiv b \pmod{m}\) かつ \(c \equiv d \pmod{m}\)が成り立つとき、次の式が成り立つことを示せ。

(a) \(a \pm c \equiv b \pm d \pmod{m}\) (復号同順)
(b) \(ac \equiv bd \pmod{m}\)
(c) \(a^n \equiv c^n \pmod{m}\) (\(n\) は正の整数)
(2) 3の倍数の条件
自然数が3の倍数であるための必要十分条件が、その10進表示の各桁の和が3の倍数であることを示せ。
(3) Freshman’s dreamが成り立つ場合
\(p\) が素数のとき, 整数 \(a, b\)に対して$$(a + b)^p \equiv a^p + b^p \pmod{p}$$が成り立つことを示せ。
(4) フェルマーの小定理 (Fermat’s little theorem)
\(p\) が素数で、非負整数 \(a\) が \(p\) と互いに素のとき$$ a^{p – 1} \equiv 1 \pmod{p}$$が成り立つことを示せ。
ただし、\(p\) を法とするとき、任意の \(a \in \{1, 2, \dots, p – 1\}\) に対して、\(ab \equiv ba \equiv 1 \pmod{p}\) となる \(b \in \{1, 2, \dots, p – 1\}\) がただ一つ存在することは証明なしで用いてよい。
(ヒント: まずは任意の非負整数 \(m\) で \(m^p \equiv m \pmod{p}\) を示す。)
(5) おまけ
上述の合同式の定義が「\(a\) を \(m\) で割った余りが \(b\) を \(m\) で割った余りと等しい」と同値であることを示せ。

解答例と解説

(1) 基本的性質
(a) \(a \equiv b \pmod{m}\) より、\(a – b\) は \(m\) の倍数だから、ある整数 \(k\) を用いて \(a – b = mk\) と表せる。
同様にして、ある整数 \(l\) を用いて \(c – d = ml\) と表せる。
これを用いると$$\begin{align*}(a \pm c) – (b \pm d) &= (a – b) \mp (c – d) = mk \mp ml\\&= m(k \mp l)\ \textrm{(複号同順)}\end{align*}$$となり、\((a + c) \pm (b + d)\) が \(m\) の倍数であることがわかる。
よって、与式が成り立つ。
(b) $$\begin{align*}ac – bd &= ac – bc + bc – bd = (a – b)c + b(c – d)\\ &= (mk)c + b(ml) = m(bl + ck)\end{align*}$$より、\(ac – bd\) は \(m\) の倍数となる。
よって、与式が成り立つ。
(c) 数学的帰納法で示す。
\(n = 1\)のときは明らか。
\(n = k\) (\(k\) は正の整数)のとき、題意が成り立つと仮定すると、\(n = k + 1\)のとき、$$a^{k + 1} = a\cdot a^{k}$$となる。
いま、\(a \equiv c \pmod{m}, a^k \equiv c^k \pmod{m}\)が成り立つから、(b)より、$$a\cdot a^{k} \equiv c\cdot c^{k} \equiv c^{k + 1}\pmod{m}$$となる。
したがって、\(a^{k + 1} \equiv c^{k + 1} \pmod{m}\)となる。
よって、与式が成り立つ。

次の3問はこれらの性質を利用して解いていきます。

(2) 3の倍数の条件
\(n\) 桁の \(10\) 進整数 \(N\) を$$N = a_0 + a_1\times 10 + a_2\times 10^2 + \cdots + a_{n – 1}\times 10^{n – 1} = \sum_{i = 0}^{n – 1} a_i\times10^i$$と表す。
ただし、\(a_i \in \{0, 1, 2, \dots, 9\}\ (i = 0, 1, \dots, n – 1)\) である。
\(10 \equiv 1 \pmod{3}\) より、任意の非負整数 \(k\) に対して \(10^k \equiv 1^k \equiv 1 \pmod{3}\) が成り立つ。
したがって、$$N \equiv \sum_{i = 0}^{n – 1}a_i\times 10^i \equiv \sum_{i = 0}^{n – 1} a_i \pmod{3}$$となる。
よって、題意は示された。

\(N\) とその桁の和が \(\equiv\) で結べてしまいました。
合同式が役に立つ一例です。

(3) Freshman’s dream が成り立つ場合
まず、\(1 \leq r \leq p – 1\) において、\(\cmb{p}{r}\) が \(p\) の倍数であることを示す。
\(\cmb{p}{r}\) の定義により、$$\cmb{p}{r} = \frac{p!}{r!(p – r)!} = p\cdot\frac{(p – 1)!}{r!(p – r)!}$$となる。
\(p\) は素数だから、分母と互いに素であり、約分されない。
したがって、\(1 \leq r \leq p – 1\)のとき \(\cmb{p}{r}\) は \(p\) の倍数である。次に、\((a + b)^n \equiv a^n + b^n \pmod{p}\) を示す。
二項定理より、$$(a + b)^p = \sum_{r = 0}^{p} \cmb{p}{r}a^{p – r}b^{r} = a^p + b^p + \sum_{r = 1}^{p – 1} \cmb{p}{r}a^{p – r}b^{r}$$となる。
ここで、上で示した事実より、$$\sum_{r = 1}^{p – 1}\cmb{p}{r} \equiv 0 \pmod{p}$$となるから、$$\sum_{r = 1}^{p – 1} \cmb{p}{r}a^{p – r}b^{r} \equiv 0 \pmod{p}$$となる。
よって、\((a + b)^p \equiv a^n + b^n \pmod{p}\) が成り立つ。

\(\cmb{p}{r}\) の分母は \(p\) より小さい正の整数の積なので \(p\) は約分されません。
この問題は英語で「freshman’s dream」とよばれる一般的には成り立たない等式 \((a + b)^n = x^n + y^n\) が成り立つ場合を示す問題です。

(4) フェルマーの小定理 (Fermat’s little theorem)
まず、
任意の非負整数 \(m\) に対して \(m^p \equiv m \pmod{p}\) が成り立つことを \(m\) についての数学的帰納法で示す。
\(m = 0\) のときは明らか。
\(m = k\) (\(k\)は非負整数) のとき、上式が成り立つと仮定すると、\(m = k + 1\)のとき、前問より$$(k + 1)^p \equiv k^p + 1^p \equiv k^p + 1 \equiv k + 1 \pmod{p}$$が成り立つ。
したがって、任意の非負整数 \(m\) に対して \(m^p \equiv m \pmod{p}\) が成り立つ。\(m\) に \(p\) と互いに素な任意の非負整数 \(a\) を代入して \(a^p \equiv a \pmod{p}\) を得る。
ここで、\(ab \equiv ba \equiv 1 \pmod{p}\) となる \(b \in \{1, 2, \dots, p – 1\}\)を用いると、$$a^{p – 1} \equiv a^pb \equiv ab \equiv 1 \pmod{p}$$が成り立つことがわかる。
よって題意は示された。

この問題は、実は、前の問題が解けていればそこまで難しい問題ではありません。
この定理はRSA暗号を理解するために重要な定理です。
今後、逆元の存在とその唯一性を証明します。

(5) おまけ

そんなに難しくないので暇な方は証明してみましょう。

次回予告

今回は合同式の性質について紹介しました。
次回は「オイラーのトーシェント関数 (Euler’s totient function) または \(\varphi\)関数」か「ユークリッドの互除法 (Euclidean algorithm)」の話をしようと考えています。
それでは。

この記事の著者

webma_user
記事一覧

高上は医学部合格率80%!
結果が出る指導を受けてみませんか?

 医学部合格実績を見る 

著者一覧