練習問題

整数 \(a_{0}\), \(\ldots\), \(a_{n}\) の線形結合の線形結合は \(a_{0}\), \(\ldots\), \(a_{n}\) の線形結合だと示せ。

自身と異なる正の約数の和が自身に等しい整数を完全数 (perfect number) と呼ぶ。例えば \(6 = 1 + 2 + 3\) より \(6\) は完全数であり、\(28 = 1 + 2 + 4 + 7 + 14\) より \(28\) は完全数である。\(2^{k} - 1\) が素数のとき \(2^{k-1}(2^{k} - 1)\) が完全数である理由を説明せよ¹。

\(x\), \(y\) を次のように定める:

Euclid のアルゴリズム (第 9.2.1 項) を使って \(x\) と \(y\) の最大公約数を見つけよ。

ヒント: 一見すると難しく見えるが、実際にはそうでもない。

\(x\), \(y\) を次のように定める:

1. \(\operatorname{gcd}(x, y)\) を求めよ。

2. \(x\) と \(y\) の最小公倍数 \(\text{lcm}(x, y)\) を求めよ。

任意の \(a, b \in \mathbb{Z}\) で次の等式が成り立つと示せ:

整数 \(m\), \(n\) の最小の正の整数線形結合は \(\operatorname{gcd}(m, n)\) に等しいと示せ。

Euclid のアルゴリズム (第 9.2.1 項) を使って次の等式を示せ:

1. 粉砕法 (第 9.2.2 項) を使って、次の等式を満たす整数 \(x\), \(y\) を求めよ:

   \[ x \cdot 30 + y \cdot 22 = \operatorname{gcd}(30, 22) \]

2. 整数 \(x^{\prime}\), \(y^{\prime}\) であって \(0 \leq y^{\prime} < 30\) と次の等式を満たすものを求めよ:

   \[ x^{\prime} \cdot 30 + y^{\prime} \cdot 22 = \operatorname{gcd}(30, 22) \]

1. 粉砕法 (第 9.2.2 項) を使って \(\operatorname{gcd}(84, 108)\) を求めよ。

2. 整数 \(x\), \(y\) であって \(x \leq y < 84\) と次の等式を満たすものを求めよ:

   \[ x \cdot 84 + y \cdot 108 = \operatorname{gcd}(84, 108) \]

3. \(\mathbb{Z}_{108}\) に \(84\) の乗法逆元は存在するか？ もし存在するなら求め、存在しないなら理由を説明せよ。

次に示す最大公約数に関する命題が正しいかどうかを答え、正しくない命題に対しては反例を示せ:

1. \(\operatorname{gcd}(a, b) \neq 1\) かつ \(\operatorname{gcd}(b, c) \neq 1\) なら \(\operatorname{gcd}(a, c) \neq 1\)

2. \(a \; | \; bc\) かつ \(\operatorname{gcd}(a, b) = 1\) なら \(a \; | \; c\)

3. \(\operatorname{gcd}(a^{n}, b^{n}) = \operatorname{gcd}(a, b)^{n}\)
4. \(\operatorname{gcd}(ab, ac) = a \cdot \operatorname{gcd}(b, c)\)
5. \(\operatorname{gcd}(1 + a, 1 + b) = 1 + \operatorname{gcd}(a, b)\)

6. \(1\) に等しい \(a\) と \(b\) の整数線形結合が存在するなら、\(1\) に等しい \(a\) と \(b^{2}\) の整数線形結合が存在する。

7. \(2\) に等しい \(a\) と \(b\) の整数線形結合が存在しないなら、\(2\) に等しい \(a^{2}\) と \(b^{2}\) の整数線形結合も存在しない。

\(a\), \(b\) を \(0\) でない整数とする。整除性と最大公約数に関する次の命題を証明せよ。解答では \(\operatorname{gcd}(a, b)\) が \(a\) と \(b\) の線形結合である事実 (定理 9.2.2) を使って構わないが、素因数分解の一意性 (定理 9.4.1) は使ってはいけない (ここに示した性質の一部は素因数分解の一意性を示すときに利用される)。

1. \(a\) と \(b\) の公約数は \(\operatorname{gcd}(a, b)\) を割り切る。

2. 任意の \(k \in \mathbb{N}\) に対して \(\operatorname{gcd}(ka, kb) = k \cdot \operatorname{gcd}(a, b)\) が成り立つ。

3. \(a \; | \; bc\) かつ \(\operatorname{gcd}(a, b) = 1\) なら \(a \; | \; c\) が成り立つ。

4. 素数 \(p\) に対して \(p \; | \; bc\) なら \(p \; | \; b\) または \(p \; | \; c\) が成り立つ。

5. \(a\) と \(b\) の正の整数線形結合の中で最小のものを \(m\) とするとき、\(m = \operatorname{gcd}(a, b)\) が成り立つ。

数論を使うと必勝戦略が示せるゲームを紹介しよう。このゲームは、異なる二つの正整数 \(a\), \(b\) を黒板に書いた状態で始まる。二人のプレイヤーは「黒板に書かれている二つの数字の差であって、まだ黒板に書かれていないものを書く」操作を交互に繰り返す。数字を書けなくなったプレイヤーの負けとなる。最初に数字を書くプレイヤーはあなたが選べるとする。

例えば、最初に \(12\) と \(15\) が黒板に書かれているなら、先攻のプレイヤーは必ず \(3\) を黒板に書く。それから後攻のプレイヤーが \(12 - 3 = 9\) を書き、先攻のプレイヤーが \(16 - 9 = 6\) を書いたとすれば、次に後攻のプレイヤーが書ける数字は存在しないので後攻のプレイヤーの敗北となる。

1. ゲームが終了する時点で黒板に書かれる数字は全て \(\operatorname{gcd}(a, b)\) の倍数だと示せ。

2. \(\operatorname{max}(a, b)\) 以下の \(\operatorname{gcd}(a, b)\) の倍数はゲーム終了時点で全て黒板に書かれると示せ。

3. 任意のゲームに勝つ戦略を示せ。

粉砕法 (第 9.2.2 項) を表す状態機械を次のように定義する:

1. この状態機械で次の性質が保存不変状態だと示せ:

   \[ \begin{aligned} \operatorname{gcd}(x, y) &= \operatorname{gcd}(a, b) \\ sa + tb &= y \\ ua + vb &= x \end{aligned} \]

2. この状態機械が部分的正当性を持つことを示せ。

3. この状態機械が Euclid のアルゴリズム (第 9.2.1 項) と同じ回数の遷移の後に停止すると示せ。

Euclid のアルゴリズム (第 9.2.1 項) をモデル化する状態機械は次の遷移で定義される:

ここで \(y\) は正整数を表す。

この状態機械が \(n\) 回の遷移を行うような初期状態 \((a, b)\ (a \geq b)\) を全て考えたときの \(a\), \(b\) の最小値はそれぞれ \(F(n-1)\), \(F(n)\) だと示せ²。ここで \(F(n)\) は \(n\) 番目の Fibonacciフィボナッチ 数 (第 5.2.2 項) を表す。

ヒント: 数学的帰納法を使う。

第 9.1.3 項で見た「容器に水を入れる問題」を拡張して、\(3\) 個の容器と \(1\) 個のタンクを使えるとした場合を考える。タンクにはいくらでも水を入れられるものの、そこに入っている水の量を知る方法は存在せず、「満杯にする」操作が行えないとする。また、容器およびタンクの水を排水溝に捨てることもできる。この設定で可能な操作を次に示す:

1. 容器を水で満杯にする。

2. タンクの水から容器に、タンクが空になるか容器が満杯になるまで移す。

3. 容器の水を全て排水溝に捨てる。

4. 容器の水を全てタンクに入れる。

5. 容器の水を別の容器に、いずれかの容器が空または満杯になるまで移す。

次の設問に答えよ:

1. このシナリオを状態機械でモデル化せよ。状態は何か？ それぞれの操作にはどんな遷移が対応するか？

2. \(k \in \mathbb{N}\) が \(\operatorname{gcd}(a, b, c) \; | \; k\) を満たすなら、上記の操作を使ってタンクに \(k\) だけの水を入れることができると示せ。

次の状態機械がモデル化するアルゴリズムは二進 GCD (binary GCD) と呼ばれ、正整数 \(a\), \(b\) の最大公約数を \(2\) による除算と減算だけで計算する。そのため、このアルゴリズムは数値を二進数で表現するハードウェアで非常に効率的よく実行できる。第 9.2.1 項で説明した Euclid のアルゴリズムの方がよく知られているものの、現実のハードウェアではこちらの方が高速に動作する。

1. 不変条件の原理を使って、この状態機械が停止するとき、つまり状態 \((x, y, e)\) からの遷移が不可能なとき、\(e = \operatorname{gcd}(a, b)\) が成り立つと示せ。

2. 最初の遷移規則

   \[ (x, y, e) \to (x/2,y/2,2e) \]

   は他の遷移規則が一度でも使われた後は使われないことを示せ。

3. この状態機械は高々 \(1 + 3(\log a + \log b)\) 回の遷移の後に停止すると示せ。

問題 9.16 で示した二進 GCD アルゴリズムを拡張して得られる、\(2\) による除算と減算だけを用いる新しい粉砕法 (第 9.2.2 項) を説明せよ。

ヒント: 二進 GCD は入力 \(x\), \(y\) を同時に \(2\) で割れるだけ割る処理が最初にある。その後、少なくとも一方が奇数である \(a\), \(b\) に対する \(\operatorname{gcd}(a, b)\) の計算を開始する。この計算では \(\operatorname{gcd}(x, y) = \operatorname{gcd}(a, b)\) を満たす組 \((x, y)\) に \((a, b)\) を更新する処理が繰り返される。この手続きを拡張し、次の条件を満たす係数 \(u_{x}\), \(v_{x}\), \(u_{y}\), \(v_{y}\) を計算・更新する処理を追加する:

\(a\) と \(b\) の少なくとも一方が奇数で \(ua + vb\) が偶数の場合を考えるときは、\(u\) と \(v\) が両方偶数であるか、そうでなければ \(u - b\) と \(v + a\) が両方偶数だと示す。

整数の集合 \(A\) に対する \(\operatorname{gcd}(A)\) を次のように定義する:

この \(\operatorname{gcd}\) に関する次の有用な性質は「自明」の一言で片付けることもできる:

この定理は素因数分解の一意性定理の簡単な系として示せる。この問題では、次に示す補題 9.2.6 の \((b)\) を繰り返し用いる数学的帰納法を使った証明を作成する:

\(\text{(AuB)}\) の証明で鍵となるのは、\(\text{(gcddiv)}\) を有限集合に一般化したときの性質である:

1. 全ての整数 \(a\), \(b\), \(c\) で次の等式が成り立つと示せ:

   \[ \operatorname{gcd}(a, \operatorname{gcd}(b, c)) = \operatorname{gcd}(\operatorname{gcd}(a, b), c) \]

以降では \(\left\{ a \right\} \cup A\) を \(a \cup A\) と略記する。

2. 全ての整数 \(a\), \(b\), \(c\) と \(C \subseteq \mathbb{Z}\) で次の関係が成り立つと示せ:

   \[ d \; | \; (a \cup b \cup C) \ \ \longleftrightarrow \ \ d \; | \; (\operatorname{gcd}(a, b) \cup C) \]

3. \(\text{(a)}\), \(\text{(b)}\) の結果と \(A\) の要素数に関する数学的帰納法を使って、全ての整数 \(a, d\) と有限集合 \(A \subset \mathbb{Z}\) で次の関係が成り立つと示せ:

   \[ d \; | \; (a \cup A) \ \ \longleftrightarrow \ \ d \; | \; \operatorname{gcd}(a, \operatorname{gcd}(A)) \]

   この結果から \(\text{(A-iff-gcdA)}\) が従う理由を説明せよ。

4. 定理 \(\text{(AuB)}\) を証明せよ。

5. \(\operatorname{gcd}(A)\) は \(A\) の要素の整数線形結合だと結論付けよ。

全ての整数 \(m\), \(b\), \(r\) で \(\operatorname{gcd}(mb + r, b) = \operatorname{gcd}(b, r)\) だと証明せよ。

MIT にある Stataスタタ Centerセンター の繊細なバランスは、秘密の部屋に置かれている二つのバケツによって保たれている。大きい方のバケツの容量は \(25\) ガロンで、小さい方のバケツの容量は \(10\) ガロンである。大きい方のバケツにちょうど \(13\) ガロンの水が入った状態になると、Stata Center は崩壊する。現在、このバケツに入っている水を特定の規則に従って遠隔で満たしたり空にしたりできる対話的展示が行われている。この展示を状態機械でモデル化しよう。

状態機械の状態は組 \((b, l)\) であり、\(b\) が大きい方のバケツに入っている水の量を、\(l\) が小さい方のバケツに入っている水の量を表す。

1. 来場者が実行できる操作の非形式的な説明を次に示す。それぞれの操作を状態機械の遷移として表現せよ。最初の操作に対する解答は例として示してある。

   1. 大きいバケツを満たす:

      \[ (b, l) \to (25, l) \]

   2. 小さいバケツを空にする。

   3. 大きいバケツに入っている水を可能な限り小さいバケツに移す。つまり、大きなバケツに入っている水が全て小さい方のバケツに入るなら全て移し、入らないなら小さい方のバケツが満杯になるまで移す。

2. 不変条件の原理を使って、二つのバケツが空の状態から始めるとき Stata Center が崩壊しないことを示せ。つまり、状態 \((13, x)\) が到達不能だと証明せよ。保存不変条件を示すときは、\(\text{(a)}\) で解答した遷移だけを考えれば十分である。

整数 \(m\), \(n\), \(p\) を次のように定める:

1. \(\operatorname{gcd}(m, n, p)\) を求めよ。

2. \(m\), \(n\), \(p\) の最小公倍数 \(\text{lcm}(m, n, p)\) を求めよ。

\(k > 1\) に対して、\(n\) を割り切る最大の \(k\) の冪の指数を \(\nu_{k}(n)\) と定義する。つまり、次のように定める:

正整数の非空集合 \(A\) に対しても \(\nu_{k}(A)\) を定義する:

3. \(\nu_{k}(A)\) を使って \(\nu_{k}(\operatorname{gcd}(A))\) を表せ。

4. \(p\) を素数とする。\(\nu_{p}(A)\) を使って \(\nu_{p}(\text{lcm}(A))\) を表せ。

5. \(\nu_{6}(\text{lcm}(a, b)) > \operatorname{max}(\nu_{6}(a), \nu_{6}(b))\) を満たすような正整数 \(a\), \(b\) の例を示せ。

6. \(A\) の全要素の積を \(\prod A\) と表記する。\(\nu_{p}(A)\) を使って \(\nu_{p}(\prod A)\) を表せ。

7. \(B\) を正整数の非空集合とする。次の等式が成り立つと結論付けよ:

   \[ \operatorname{gcd}(A \cup B) = \operatorname{gcd}(\operatorname{gcd}(A), \operatorname{gcd}(B)) \tag{9.19}\]

   ヒント: 両辺を \(\nu_{p}\) を使って書き換える。次の等式を仮定してよい:

   \[ \operatorname{min}(A \cup B) = \operatorname{min}(\operatorname{min}(A), \operatorname{min}(B)) \tag{9.20}\]

\(p\) を素数、\(a_{1}\), \(\ldots\), \(a_{n}\) を整数とする。次の補題を数学的帰納法で証明せよ:

証明では \(n = 2\) の場合 (補題 9.4.2) の成立を仮定して構わない。帰納法の仮定、ベースケース、そして帰納ステップをはっきりと明示すること。

1. \(m = 2^{9} \cdot 5^{24} \cdot 11^{7} \cdot 17^{12} \), \(\,n = 2^{3} \cdot 7^{22} \cdot 11^{211} \cdot 13^{1} \cdot 17^{9} \cdot 19^{2}\) とする。\(m\) と \(n\) の最小公倍数 \(\text{lcm}(m, n)\) を求めよ。さらに、次の等式が成り立つことを確かめよ:

   \[ \operatorname{gcd}(m, n) \cdot \text{lcm}(m, n) = mn \tag{9.21}\]

2. \(m\) と \(n\) の素因数分解から \(\operatorname{gcd}(m, n)\) と \(\text{lcm}(m, n)\) を求める方法を説明し、等式 \(\text{(9.21)}\) が任意の正整数 \(m\), \(n\) で成り立つと結論付けよ。

整数 \(m\), \(n\) を使って \(m + n \sqrt{-5}\) と書ける複素数全体の集合を \(\mathbb{Z}[\,\sqrt{-5}\,]\) と表記する。この \(\mathbb{Z}[\,\sqrt{-5}\,]\) では素因数分解が一意性を持たないことを見よう。

\(\mathbb{Z}[\,\sqrt{-5}\,]\) に属する要素同士の和と積は \(\mathbb{Z}[\,\sqrt{-5}\,]\) に属する。また、\(\mathbb{Z}[\,\sqrt{-5}\,]\) は複素数全体の集合の部分集合だから、加算と乗算に関する通常の性質も成り立つ。しかし \(\mathbb{Z}[\,\sqrt{-5}\,]\) では奇妙なことが起こる。例えば素数 \(29\) は因数分解できる:

1. \(xy = 29\), \(x \neq \pm 1\), \(y \neq \pm 1\) を満たす \(x, y \in \mathbb{Z}[\,\sqrt{-5}\,]\) を求めよ。

これに対して、\(3\) は \(\mathbb{Z}[\,\sqrt{-5}\,]\) でも「素数」のままである。複素数 \(p \in \mathbb{Z}[\,\sqrt{-5}\,]\) が \(\mathbb{Z}[\,\sqrt{-5}\,]\) で既約 (irreducible) とは、ある \(x, y \in \mathbb{Z}[\,\sqrt{-5}\,]\) が \(xy = p\) を満たすとき必ず \(x = \pm 1\) または \(y = \pm 1\) が成り立つことを言う。このとき次の主張が成り立つ:

この主張から、\(9\) を \(\mathbb{Z}[\,\sqrt{-5}\,]\) で既約な複素数の積に分解する方法が二つあると分かる:

つまり \(\mathbb{Z}[\,\sqrt{-5}\,]\) は非一意分解整域 (non-unique factorization domain) と呼ばれる概念の例である。

次の設問に答えよ。解答では、読者も知っているはずの複素数に関する次の補題を (証明せずに) 使って構わない:

2. 全ての \(x \in \mathbb{Z}[\,\sqrt{-5}\,]\) で \(|x|^{2} \neq 3\) だと示せ。

3. \(x \in \mathbb{Z}[\,\sqrt{-5}\,]\) かつ \(|x| = 1\) なら \(x = \pm 1\) だと示せ。

4. ある \(x, y \in \mathbb{Z}[\,\sqrt{-5}\,]\) で \(|xy| = 3\) なら \(x = \pm 1\) または \(y = \pm 1\) だと示せ。

   ヒント: 任意の \(z \in \mathbb{Z}[\,\sqrt{-5}\,]\) で \(|z|^{2} \in \mathbb{N}\) が成り立つ。

5. 上記の主張の証明を完成させよ。

\(a \equiv b \ \ (\text{mod } 14)\) かつ \(a \equiv b \ \ (\text{mod } 5)\) なら \(a \equiv b \ \ (\text{mod } 70)\) だと示せ。

次の関係を満たす整数 \(x\) が存在すると示せ:

1. 整数 \(n\) が \(3\) で割り切れないなら \(n^{2} \equiv 1 \ \ (\text{mod } 3)\) だと示せ。

2. \(n\) が奇数なら \(n^{2} \equiv 1 \ \ (\text{mod } 8)\) だと示せ。

3. ここまでの結果を使って、\(p\) が \(3\) より大きい素数なら \(p^{2} - 1\) が \(24\) で割り切れると示せ。

多項式 \(p(n) ::= n^{2} + n + 41\) の値は \(n\) が \(0\) 以上 \(39\) 以下の整数のとき素数である (参照: 第 1.1 節)。この \(p\) では素数を無限に生成できない。では、整数に対する値が必ず素数となる多項式は存在するだろうか？ もちろん存在しない！ 実は、ずっと強い主張が証明できる:

1. 上に示した整数多項式関数の再帰的定義に関する構造的帰納法を使って、全ての \(q \in P\) と整数 \(j\), \(k\), \(n\) (\(n > 1\)) が次の関係を満たすと示せ:

   \[ j \equiv k \quad (\text{mod } n) \ \ \longrightarrow \ \ q(j) \equiv q(k) \quad (\text{mod } n) \]

   帰納法の仮定、ベースケース、構築ステップをはっきりと明示すること。

2. \(q \in P\) が倍数生成 (produce mutiples) とは、\(q\) の値域に属する \(1\) より大きい任意の整数 \(n\) について、\(q\) の値域に \(n\) の倍数が無限に含まれることを意味すると定める。例えば \(q(4) = 7\) で \(q\) が倍数生成なら、\(q\) の値域には \(7\) の倍数が無限に含まれる。\(7\) を除けば、これらの値は素数でない。

   \(q\) が正次数かつ最高次の係数が正なら \(q\) は倍数生成だと示せ。この条件を満たす任意の多項式 \(q(n)\) は十分大きい \(n\) に対して狭義増加である事実を証明せずに使ってよい。

\(\text{(b)}\) の結果から、最高次の係数が正である任意の整数係数多項式は値域に無限に多くの非素数を含むと分かる。ただ、この事実は多変数多項式では成り立たない。Yuriユーリ Matiyasevichマチャセビッチ が示した Hilbertヒルベルト の第十問題への解答 [35] から導ける驚異的な結果の一つに「多変数多項式は整数の集合を生成する汎用なプログラムとして理解できる」がある。つまり、もし非負整数の集合が何らかのプログラムで生成できるなら、値域がその集合に等しい整数係数多変数多項式が存在する！ 特に、\(x_{1}\), \(\ldots\), \(x_{7}\) の変域が \(\mathbb{N}\) であるとき、\(p\) の値域と \(\mathbb{N}\) の共通部分が素数全体の集合とちょうど等しいような七変数多項式 \(p(x_{1}, \ldots, x_{7})\) の存在が証明されている！

\(n > 1\), \(a\), \(b\) を整数とする。次に示す命題の中で、

と同値であるものを全て選び、その理由を簡単に説明せよ。

1. \(2a \equiv 2b \ \ (\text{mod } n)\)
2. \(2a \equiv 2b \ \ (\text{mod } 2n)\)
3. \(a^{3} \equiv b^{3} \ \ (\text{mod } n)\)
4. \(\operatorname{rem}(a, n) = \operatorname{rem}(b, n)\)
5. \(\operatorname{rem}(n, a) = \operatorname{rem}(n, b)\)
6. \(\operatorname{gcd}(n, a - b) = n\)

7. \(a - b\) が \(n\) の倍数

8. \(\exists k \in \mathbb{Z}.\ a = b + nk\)

\(\operatorname{rem}(3^{101}, 21)\) の値は何か？

合同関係は算術式の評価で保存されると示せ。つまり、整数 \(n > 1\), \(a\), \(b\) が

を満たすなら、任意の \(e \in \text{Aexp}\) (第 7.4 節) に対して次の合同関係が成り立つと示せ:

集合 \(R\) が可換環 (commutative ring) であるとき、\(R \mathrel{\times} R\) から \(R\) への二項演算 \(\oplus\), \(\otimes\) が存在する。さらに、\(R\) は零元 (zero-element) と呼ばれる要素 \(\textbf{0}\) と単位元 (unit-element) と呼ばれる要素 \(\textbf{1}\) を持つ。また、可換環に関連付く二項演算 \(\oplus\), \(\otimes\) と任意の \(r, s, t \in R\) は次に示す環の公理 (ring axioms) を満たす:

1. 零元が一意だと示せ。言い換えれば、ある \(z \in R\) が任意の \(r \in R\) に対して

   \[ z \oplus r = r \tag{9.24}\]

   を満たすなら \(z = \textbf{0}\) だと証明せよ。

2. 加法に関する逆元が一意だと示せ。言い換えれば、任意の \(r \in R\) に対して

   \[ r \oplus r_{1} = \textbf{0} \tag{9.25}\]
   \[ r \oplus r_{2} = \textbf{0} \tag{9.26}\]

   を満たす \(r_{1}, r_{2} \in R\) が存在するとき \(r_{1} = r_{2}\) だと証明せよ。

3. 乗法に関する逆元が一意だと示せ。言い換えれば、任意の \(r \in R\) に対して

   \[ r \otimes r_{1} = \textbf{1} \]
   \[ r \otimes r_{2} = \textbf{1} \]

   を満たす \(r_{1}, r_{2} \in R\) が存在するとき \(r_{1} = r_{2}\) だと証明せよ。

この問題では「任意の正整数は無限に多くの Fibonacci 数を割り切る」という命題を合同算術の初等的な性質を使って証明する。

関数 \(f\colon \mathbb{N} \to \mathbb{N}\) が \(d\) 次線形再帰的 (degree \(d\) linear-recursive) とは、\(d\) 個の非負整数 \(c_{1}, \ldots, c_{d}\) が存在して、全ての \(n \geq d\) が次の等式を満たすことを言う:

関数 \(f\colon \mathbb{N} \to \mathbb{N}\) が \(n\) と \(k\) から始まる法 \(m\) の \(d\) 次反復 (degree \(d\) repeat) を持つとは、次の合同関係が全て成り立つことを言う:

ここで \(k > n \geq d - 1\) である。

この問題で考える線形再帰性および反復の次数は常に \(d \geq 1\) だと仮定する。

1. 線形再帰的な関数が \(n\) と \(k\) から始まる法 \(m\) の反復を持つなら、\(n + 1\) と \(k + 1\)から始まる法 \(m\) の反復も持つことを示せ。

2. 全ての \(m > 1\) に対して、任意の線形再帰的な関数 \(f\) に \(n, k \in [d-1..d+m^{d})\) が存在して、\(f\) が \(n\) と \(k\) から始まる法 \(m\) の反復を持つと示せ。

3. \(d\) 次線形再帰的な関数が逆線形 (reverse-linear) とは、\(d\) 次の係数 \(c_{d}\) が \(1\) または \(-1\) であることを言う。線形再帰的かつ逆線形な関数が \(n \geq d\) と \(k\) から始まる法 \(m\) の反復を持つなら、\(n - 1\) と \(k - 1\) から始まる法 \(m\) の反復も持つと示せ。

4. 関数 \(f\) が線形再帰的かつ逆線形なら、ある \(j > 0\) が存在して、\(f\) が \(d - 1\) と \((d - 1) + j\) から始まる法 \(m\) の反復を持つと結論付けよ。

5. 関数 \(f\) が線形再帰的かつ逆線形で \(f(k) = 0\) を満たす \(k \in [0..d)\) が存在するとき、任意の正整数は無限個の \(f(n)\) の約数だと結論付けよ。

6. 任意の正整数は無限に多くの Fibonacci 数の約数であると結論付けよ。

   ヒント: Fibonacci 数を \(1\), \(1\) ではなく \(0\), \(1\) から始める。

次の値を求めよ:

\(n\) を法とする合同算術に関する次の性質は、どれも合同関係の定義と整除性の単純な性質から従う。本文中で示した証明を読み返さずに証明できるか試してみよ:

1. \(a \equiv b \ \ (\text{mod } n)\) なら \(ac \equiv bc \ \ (\text{mod } n)\)

2. \(a \equiv b \ \ (\text{mod } n)\) かつ \(b \equiv c \ \ (\text{mod } n)\) なら \(a \equiv c \ \ (\text{mod } n)\)

3. \(a \equiv b \ \ (\text{mod } n)\) かつ \(c \equiv d \ \ (\text{mod } n)\) なら \(ac \equiv bd \ \ (\text{mod } n)\)

4. \(\operatorname{rem}(a, n) \equiv a \quad (\text{mod } n)\)

1. 整数が \(9\) で割り切れるのは、その十進表記の各桁の和が \(9\) で割り切れるとき、かつそのときに限る。その理由を説明せよ。

   ヒント: \(10 \equiv 1 \ \ (\text{mod } 9)\)

2. 大きな整数を思い浮かべてほしい。その十進表記の各桁に \(1\) と \(-1\) を交互に乗じながら足した和を考える。例えば \(37273761261\) に対しては次の値となる:

   \[ 3 + (-7) + 2 + (-7) + 3 + (-7) + 6 + (-1) + 2 + (-6) + 1 = -11 \]

   最初に思い浮かべた整数が \(11\) で割り切れるのは、この和が \(11\) で割り切れるとき、かつそのときに限る。その理由を説明せよ。

あるとき、整数の \(13\) 乗である \(100\) 桁の整数の \(13\) 乗根を暗算で計算した人物が「世界最高の人間計算機」としてギネス世界記録に登録された。なんとも興味深い問題を選んだものだ...。

この問題では、全ての \(n\) で次の合同関係が成り立つことを示す:

1. 合同関係 \(\text{(9.29)}\) が Euler の定理から直ちに従わない理由を説明せよ。

2. \(0 \leq d < 10\) を満たす整数 \(d\) で次の合同関係が成り立つと示せ:

   \[ d^{13} \equiv d \quad (\text{mod } 10) \tag{9.30}\]

3. 合同関係 \(\text{(9.29)}\) を示せ。

1. \(10\) 人の海賊が金貨と銀貨の入った宝箱を見つけた。銀貨は金貨の二倍ある。金貨を分けるにあたって、海賊たちは「任意の二人の手にする金貨の枚数の差が \(10\) で割り切れないようにする」と定めた。さらに、同様の規則で銀貨を分けられるときに限って銀貨を持ち帰ると決めた。海賊たちは銀貨を持ち帰ることができるだろうか？ 解答を証明せよ。

2. 宝箱の中には硬貨の他に \(3\) 個の袋があり、それぞれ \(5\), \(49\), \(51\) 個のルビーが入っていた。海賊船の物品整理係は退屈していたので、次のゲームを遊ぶことにした。このゲームのプレイヤーは次の操作のいずれかを行える:

   • ルビーが積まれた山を二つ選び、一つにする。

   • 偶数個のルビーが積まれた山を二つの山に等分する。

   このゲームはそれぞれの袋に入っているルビーをそのまま積んだ \(3\) 個の山がある状態から始まり、\(1\) 個のルビーからなる山が \(105\) 個できたとき終了する。このゲームを終了させることはできるか？

計算の各ステップを注意深く説明しながら、次の剰余を計算せよ:

整数の十進表記の各桁の和は元の整数と \(9\) を法として合同である。例えば次の合同関係が成り立つ:

このとき「\(9\) は基数 \(10\) で優れた法である」と言うことにする。

これを一般化して、任意の非負整数 \(n\) に対して、\(n\) の \(b\) 進表記の各桁の和が \(k\) を法として \(n\) と合同なとき「\(k\) は基数 \(b\) で優れた法 (good modulus) である」と定める。例えば、\(763 \not \equiv 7 + 6 + 3 \ \ (\text{mod } 2)\) からは基数 \(10\) で \(2\) は優れた法でないと分かる。

1. 基数 \(10\) に対して優れた法となる整数 \(k > 1\) を全て答えよ。

2. \(b \equiv 1 \ \ (\text{mod } k)\) なら \(k\) は基数 \(b\) で優れた法だと示せ。

3. 逆に、\(k\) が基数 \(b \geq 2\) で優れた法なら \(b \equiv 1 \quad (\text{mod } k)\) だと示せ。

4. 基数 \(106\) で優れた法となる整数 \(k > 1\) を全て答えよ。

\(p(x)\) を整数係数多項式とする。つまり \(p(x) = \sum_{i=0}^{d} c_{i}x^{i}\) としたとき \(c_{0}\), \(\ldots\), \(c_{d}\) は全て整数である。

1. 全ての整数 \(n > 1\) と \(k\) に対して \(p(k) \equiv p(\operatorname{rem}(k, n)) \ \ (\text{mod } n)\) である理由を説明せよ。

\(q(x)\) と \(q(\mathbb{N})\) を次のように定める:

2. \(3\) が \(q(\mathbb{N})\) の任意の要素を割り切ると示せ。

3. \(4\) が \(q(\mathbb{N})\) の任意の要素を割り切ると示せ。

4. \(\operatorname{gcd}(q(\mathbb{N})) = 12\) を示せ。

次の規則で数列 \(\left\{ a_{n} \right\}\) を定義する:

強い数学的帰納法を使って、全ての \(n \geq 0\) で \(\operatorname{rem}(a_{n}, 3) = 1\) だと示せ。

構造的帰納法を使って、全ての \(q \in P\) と全ての整数 \(j,k,n\) \(\ (n > 1)\) に対して次の関係が成り立つことを示せ:

解答では帰納法の仮定、ベースケース、構築ステップをはっきりと示すこと。

1. 整数 \(m, n \in \mathbb{Z}^{+}\) に対して粉砕法 (第 9.2.2 項) を実行したとき、最終的に計算される \(x, y \in \mathbb{Z}\) がどのような条件を満たすか答えよ。

2. \(n > 1\) とする。粉砕法で計算される \(x\), \(y\) を使って法 \(n\) の合同算術における \(m\) の逆元を (存在するなら) 計算する方法を説明せよ。

\(\mathbb{Z}_{7}\) における \(2\) の乗法に関する逆元を求めよ。復習: 定義より、解答は \(0\) 以上 \(6\) 以下の整数である。

1. \(25x + 32y = \operatorname{gcd}(25, 32)\) を満たす整数係数 \(x\), \(y\) を求めよ。

2. \(\mathbb{Z}_{25}\) における \(32\) の乗法に関する逆元は何か？

1. \(40s + 7t = \operatorname{gcd}(40, 7)\) を満たす整数 \(s\), \(t\) を粉砕法 (第 9.2.2 項) で求めよ。

2. \(\text{(a)}\) の結果を利用して、\(\mathbb{Z}_{40}\) における \(7\) の乗法に関する逆元を求めよ。

平面上の平行でない二直線はどこかで交わる。代数の言葉を使えば、次の二直線は \(m_{1} \neq m_{2}\) のとき一意な解 \((x, y)\) を持つ:

この事実は \(x\), \(y\) を整数に制限するとき成り立たない。交点が非整数の座標を持つ可能性があるためである:

しかし、素数 \(p\) を法とする合同算術を考えるなら、同様の事実は成り立つ。\(m_{1} \neq m_{2}\) のとき、次の合同関係を満たす \((x, y)\) を求めよ:

解答は次の形で表すこと:

ここで \(?\) は \(m_{1}\), \(m_{2}\), \(b_{1}\), \(b_{2}\) を含む式を表す。

ヒント: 元々の方程式を実数について解く。

「\(k \in [0..n)\) が \(n\) を法とする合同算術で逆元を持つ」と「\(k\) が \(\mathbb{Z}_{n}\) で逆元を持つ」が同値だと示せ。

\(\operatorname{rem}(24^{79}, 79)\) の値は何か？

ヒント: 乗算を計算する必要は一切ない！

1. \(22^{12001}\) が \(\mathbb{Z}_{175}\) で乗法に関する逆元を持つと示せ。

2. \(\phi\) を Euler の \(\phi\) 関数とする。\(\phi(175)\) の値を求めよ。

3. \(22^{12001}\) を \(175\) で割った剰余を求めよ。

\(1\) 以上 \(6042\) 以下の整数の中で \(3780\) と互いに素なものはいくつあるか？

ヒント: \(3780\) は \(53\) で割り切れる。

\(1\) 以上 \(3780\) 以下の整数の中で \(3780\) と互いに素なものはいくつあるか？

1. \(1\) 以上 \(360\) 以下の整数を一様ランダムに選択したとき、選択された整数が \(360\) と互いに素である確率を求めよ。

2. \(\operatorname{rem}(7^{98}, 360)\) を求めよ。

\(26^{1818181}\) を \(297\) で割った剰余を求めよ。

ヒント: 等式 \(1818181 = (180\cdot 10101) + 1\) と Euler の定理を使う。

\(7^{7^{7^{7}}}\) の最後の一桁を求めよ。

整数 \(n\) と \(n^{5}\) の最後の一桁が一致することを証明せよ。例えば、次の等式が成り立つ:

Fermat の小定理 (系 9.10.8) を使って、\(23\) を法とする合同算術における \(13\) の乗法に関する逆元 \(i\) \(\ (1 \leq i < 23)\) を求めよ。

\(\phi\) を Euler の \(\phi\) 関数とする。

1. \(\phi(2)\) の値は何か？

2. \(\phi(k) = 2\) を満たす整数 \(k > 1\) を三つ答えよ。

3. 整数 \(k > 2\) では \(\phi(k)\) が偶数だと証明せよ。

   ヒント: \(k\) が奇数の素数を因数に持つかどうかを分けて考える。

4. \(\phi(k) = 2\) を満たす整数 \(k\) がちょうど三つしか存在しない理由を簡単に説明せよ。

\(a\), \(b\) を互いに素な \(1\) より大きい整数とする。この問題では次の中国剰余定理 (Chinese remainder theorem) を証明する。中国剰余定理は、任意の整数 \(m\), \(n\) に対して、次の合同関係を満たす \(x\) が存在すると主張する:

さらに、この \(x\) は \(ab\) を法とする合同関係に関して一意である。言い換えれば、合同関係 \(\text{(9.31)}\), \(\text{(9.32)}\) を満たす任意の \(x\), \(x^{\prime}\) は次の合同関係を満たす:

1. 任意の整数 \(m\), \(n\) に対して、合同関係 \(\text{(9.31)}\), \(\text{(9.32)}\) を満たす \(x\) が存在することを示せ。

   ヒント: \(b^{-1}\) を \(\mathbb{Z}_{a}\) における \(b\) の逆元として、\(e_{a} ::= b^{-1}b\) と定める。\(e_{b}\) も同様に定義して、\(x = me_{a} + ne_{b}\) だと示す。

2. 次の関係を示せ:

   \[ (x \equiv 0 \ \ (\text{mod } a)\ \ \operatorname{\text{\footnotesize AND}} \ \ x \equiv 0 \ \ (\text{mod } b)) \ \ \longrightarrow \ \ x \equiv 0 \ \ (\text{mod } ab) \]

3. 次の関係が成り立つと結論付けよ:

   \[ (x \equiv x^{\prime} \ \ (\text{mod } a)\ \ \operatorname{\text{\footnotesize AND}} \ \ x \equiv x^{\prime} \ \ (\text{mod } b)) \ \ \longrightarrow \ \ x \equiv x^{\prime} \ \ (\text{mod } ab) \]

4. 中国剰余定理が成立すると結論付けよ。

5. \(\text{(c)}\) の逆は成り立つか？

\(k \in \mathbb{Z}_{n}\) の位数 (order) とは、\(k^{m} = 1 \ \ (\mathbb{Z}_{n})\) を満たす最小の正整数 \(m\) を言う。\(\mathbb{Z}_{n}\) の要素 \(k\) の位数を \(\text{ord}(k, n)\) と表記する。

1. 次の関係を示せ:

   \[ k^{m} = 1 \quad (\mathbb{Z}_{n}) \ \ \longrightarrow \ \ \text{ord}(k, n) \; | \; m \]

   ヒント: \(m\) を位数で割ったときの剰余を考える。

\(p > 2\) を \(2^{s} + 1\) の形をした素数とする。例えば \(2^{1} + 1\), \(2^{2} + 1\), \(2^{4} + 1\) がそういった素数である。

2. \(\text{(a)}\) の結果を使って、\(0 < k < p\) に対して \(\text{ord}(k, p)\) が \(2\) の冪だと示せ。

3. \(\text{ord}(2, p) = 2s\) を示し、\(s\) は \(2\) の冪だと結論付けよ³。

   ヒント: \(k \in [1..s]\) のとき \(2^{k} - 1\) は正であるものの、小さすぎて \(\mathbb{Z}_{p}\) で \(0\) と等しくなれない。

この問題では素数 \(p\) を法とする合同算術における平方根を考える。

1. 次の関係を示せ:

   \[ x^{2} \equiv y^{2} \quad (\text{mod } p) \ \ \longleftrightarrow \ \ x \equiv y \quad (\text{mod } p) \ \operatorname{\text{\footnotesize OR}}\ x \equiv -y \quad (\text{mod } p) \]

   ヒント: \(x^{2} - y^{2} = (x + y)(x - y)\)

\(p\) を法とする合同算術で \(x\) が \(n\) の平方根 (square root) とは、次の関係を満たすことを言う:

また、このとき \(n\) を平方数 (square) と呼ぶ。例えば \(p\) を法とする合同算術で \(n\) が \(0\) または \(1\) と合同なら \(n\) は平方数であり、その平方根は \(n\) 自身である。

\(p\) を奇素数、\(n \not \equiv 0 \ \ (\text{mod } p)\) と定める。\(p\) を法とする合同算術で \(n\) が平方数かどうかを判定する単純な方法が存在する:

1. Euler の基準の \(\text{(i)}\) を示せ。ヒント: Fermat の小定理 (系 9.10.8)を使う。

2. Euler の基準の \(\text{(ii)}\) を示せ。ヒント: \(\text{(a)}\) の結果を使う。

3. \(p \equiv 3 \ \ (\text{mod } 4)\) で、\(p\) を法とする合同算術で \(n\) は平方数と定める。\(n\) の平方根を \(n\) と \(p\) からなる簡単な式で表せ。

   ヒント: \(p = 4k + 3\) として Euler の基準を使う。どこかで等式の両辺に \(n\) を乗じることになるだろう。

\(a\), \(b\) を \(1\) より大きい互いに素な整数とする。この問題では Euler の \(\phi\) 関数が乗法的であることを証明する。つまり、次の等式を示す:

この事実は中国剰余定理 (問題 9.61) の簡単な系である。

1. 中国剰余定理を使って、次の規則で定義される関数 \(f\colon [0..ab) \to [0..a) \times [0..b)\) が全単射だと示せ:

   \[ f(x) ::= \left( \operatorname{rem}(x, a), \operatorname{rem}(x, b) \right) \]

2. 任意の正整数 \(k\) に対して、\(k\) と互いに素な \(k\) 以下の非負整数全体の集合を \(\mathbb{Z}_{k}^{\ast}\) と定義する。\(\text{(a)}\) で定義した関数 \(f\) が \(\mathbb{Z}_{ab}^{\ast}\) から \(\mathbb{Z}_{a}^{\ast} \times \mathbb{Z}_{b}^{\ast}\) への全単射も定義すると示せ。

3. ここまでの結果を使って次の等式を示せ:

   \[ \phi(ab) = \phi(a)\phi(b) \]

4. 系 9.10.11 を示せ: 任意の整数 \(n > 1\) の全ての因数分解を \(p_{1}\), \(p_{2}\), \(\ldots\), \(p_{j}\) とするとき、次の等式が成り立つ:

   \[ \phi(n) = n \left( 1 - \frac{1}{p_{1}} \right) \left( 1 - \frac{1}{p_{2}} \right) \cdots \left( 1 - \frac{1}{p_{j}} \right) \]

1. 「\(k \in \mathbb{Z}_{n}^{\ast} \)」と「\(k\) が \(\mathbb{Z}_{n}\) で有限の位数を持つ」が同値だと示せ。

2. 全ての \(k \in \mathbb{Z}_{n}^{\ast}\) に対して、\(\mathbb{Z}_{n}\) における \(k\) の位数が \(\phi(n)\) を割り切ると示せ。

   ヒント: \(m = \text{ord}(k, n)\) として、\(\phi(n)\) を \(m\) で割った商と剰余を考える。

中国剰余定理 (問題 9.61) を一般化すると、互いに素な三つ以上の整数を法とする合同関係に拡張できる。具体的には:

この事実は \(k\) に関する簡単な数学的帰納法を使えば素因数分解の一意性から簡単に証明できる: もし整数がいくつかの整数のいずれとも互いに素なら、それらの積とも互いに素である。

一般化された中国剰余定理は、巨大な整数の加算と乗算が何度も必要になる計算を高速に実行する手法の一つで利用される。

具体的には次の通りである。\(n\) は巨大であるものの、その約数 \(a_{i}\) は十分小さいので入手しやすい安価なハードウェアユニットで扱える状況を考える。この上で、多くの加算と乗算からなる計算を実行する必要があると仮定する。巨大な整数 \(x\) と \(y\) の和や積を計算する通常の方法では、\(x\) と \(y\) を算術ユニットが扱える小さい部分に分割し、その部分を算術ユニットに入力して和や積を計算し、その (場合によっては多くの) 結果を一つに組み合わせたものを全体の解答とする。このアプローチでは、それぞれの部分を計算する順序が何らかの理由で ── 例えば「繰り上がり」が必要になるために ── 制約を受けることがある。さらに、上記の処理は巨大な整数に対する加算と乗算のたびに必要になる。

巨大な整数に対する多くの加算と乗算からなる計算を実行するとき、一般化された中国剰余定理を使うと上述した通常の方法より格段に効率的に計算できることを説明せよ。

この問題では、全ての整数 \(a\), \(m\) \(\ (m > 1)\) で次の合同関係が成り立つと示す:

\(a\) と \(m\) が互いに素とは限らない点に注意してほしい。

相異なる素数 \(p_{1}\), \(\ldots\), \(p_{n}\) と正整数 \(k_{1}\), \(\ldots\), \(k_{n}\) を使って \(m = p_{1}^{k_{1}} \ldots p_{n}^{k_{n}}\) と表せると仮定する。

1. \(p_{i}\) が \(a\) を割り切らないなら次の合同関係が成り立つと示せ:

   \[ a^{\phi(m)} \equiv 1 \quad (\text{mod } p_{i}^{k_{i}}) \]

2. \(p_{i}\) が \(a\) を割り切るなら次の合同関係が成り立つと示せ:

   \[ a^{m - \phi(m)} \equiv 0 \quad (\text{mod } p_{i}^{k_{i}}) \tag{9.35}\]

3. ここまでの結果を使って合同関係 \(\text{(9.34)}\) を示せ。

   ヒント: \(a^{m} - a^{m - \phi(m)} = a^{m - \phi(m)}(a^{\phi(m)} - 1)\)

特定の料金の切手だけを使ってちょうど支払える郵便料金を考える問題をこれまでに何度か見てきた (問題 2.1, 問題 2.14, 問題 5.33 など)。この問題では、価値が正整数 \(a\), \(b\) である二種類の切手を使って支払える郵便料金を一般的に考える。この二種類の切手を使ってちょうど支払える金額を支払い可能 (makeable) と呼ぶことにする。

この補題を証明するために、無限に長い行を持つ次の表を考える:

明らかに、この表に書かれる値は全て支払い可能である。

1. 整数 \(n\) が表の特定の行の第 \(1\) 要素以上であり、かつ \(a\) を法としてその第 \(1\) 要素と合同だとする。このとき \(n\) は表に含まれると示せ。

2. \(0\) から \(a - 1\) までの全ての整数は、第 \(1\) 列の何らかの要素と \(a\) を法として合同だと示せ。

3. 一般化された郵便料金補題の証明を完了させよ: \(\text{(a)}\) と \(\text{(b)}\) の結果を使って、\(ab - a - b\) より大きい任意の整数が表に含まれる、つまり支払い可能だと示せ。

   ヒント: \(n\) が \(a\) を法として何らかの行の第 \(1\) 要素と合同だとする。その第 \(1\) 要素より \(n\) の方が小さいなら \(n \leq ab - a - b\) だと示す。

4. [スキップ可] さらに、\(ab - a - b\) は支払い可能でないとも示せる。証明せよ。

5. 一般化された郵便料金補題と \(\text{(d)}\) の結果を使うと、さらに一般化された次の補題が容易に示せる理由を説明せよ:

   補題[\(\text{一般化}^{\hspace{-1pt}\small 2}\)された郵便料金補題]

   \(m\), \(n\) が正整数で、\(g ::= \operatorname{gcd}(m, n) > 1\) が成り立つとする。このとき、価値がそれぞれ \(m\), \(n\) である二種類の切手を使ってちょうど支払える郵便料金は \(g\) の倍数に限られる。さらに、\((mn/g) - m - n\) より大きい \(g\) の倍数は全て支払い可能であり、\((mn/g) - m - n\) は支払い可能でない。

6. [スキップ可, おそらく未解決] 価値がそれぞれ \(a\), \(b\), \(c\) である三種類の切手があり、\(\operatorname{gcd}(a, b, c) = 1\) が成り立つとする。このとき「\(n_{abc}\) 以上の全ての郵便料金は三種類の切手を使ってちょうど支払える」を満たす最小の \(n_{abc}\) を表す式を答えよ。

\(63^{9601}\) を \(220\) で割った剰余を求めよ。

\(n\), \(k_{1}\), \(k_{2}\) を整数とする。命題「\(k_{1}\) と \(k_{2}\) が \(n\) と互いに素なら、\(k_{1} \cdot_{n} k_{2}\) も \(n\) と互いに素である」を...

1. 「\(k\) と \(n\) が互いに素 \(\ \ \longleftrightarrow \ \ \) \(n\) を法とする剰余算術で \(k\) が逆元を持つ」という事実を使って証明せよ。

   ヒント: 定義より \(k_{1}k_{2} \equiv k_{1} \cdot_{n} k_{2} \ \ (\text{mod } n)\) が成り立つ。

2. 「\(k\) と \(n\) が互いに素 \(\ \ \longleftrightarrow \ \ \) \(n\) を法とする剰余算術で \(k\) が打ち消し可能」という事実を使って証明せよ。

3. 素因数分解の一意性と最大公約数の基礎的な性質 (補題 9.2.1 など) を使って証明せよ。

次に示す命題が正しいか正しくないかを答え、正しくないと答えた命題に対しては反例を与えよ。変数 \(a\), \(b\), \(c\), \(m\), \(n\) の変域は \(\mathbb{Z}\) で、\(m,n > 1\) が成り立つとする。

1. \(\operatorname{gcd}(1 + a, 1 + b) = 1 + \operatorname{gcd}(a, b)\)

2. 任意の整数係数多項式 \(p(x)\) に対して、もし \(a \equiv b \ \ (\text{mod } n)\) が成り立つなら \(p(a) \equiv p(b) \ \ (\text{mod } n)\)

3. \(a \; | \; bc\) かつ \(\operatorname{gcd}(a, b) = 1\) なら \(a \; | \; c\)

4. \(\operatorname{gcd}(a^{n}, b^{n}) = \operatorname{gcd}(a, b)^{n}\)

5. \(\operatorname{gcd}(a, b) \neq 1\) かつ \(\operatorname{gcd}(b, c) \neq 1\) なら \(\operatorname{gcd}(a, c) \neq 1\)

6. \(1\) に等しい \(a\) と \(b\) の整数線形結合が存在するなら、\(1\) に等しい \(a^{2}\) と \(b^{2}\) の整数線形結合も存在する。

7. \(2\) に等しい \(a\) と \(b\) の整数線形結合が存在しないなら、\(2\) に等しい \(a^{2}\) と \(b^{2}\) の整数線形結合も存在しない。

8. \(ac \equiv bc \ \ (\text{mod } n)\) かつ \(n\) が \(c\) を割り切らないなら \(a \equiv b \ \ (\text{mod } n)\)

9. \(n\) を法とする剰余算術で \(a\), \(b\) が逆元を持つなら、\(a^{-1} \equiv b^{-1} \ \ (\text{mod } n)\) のとき \(a \equiv b \ \ (\text{mod } n)\)

10. \(ac \equiv bc \ \ (\text{mod } n)\) かつ \(n\) が \(c\) を割り切らないなら \(a \equiv b \ \ (\text{mod } n)\)

11. \(a \equiv b \ \ (\text{mod } \phi(n))\) で \(a, b > 0\) なら \(c^{a} \equiv c^{b} \ \ (\text{mod } n)\)

12. \(a \equiv b \ \ (\text{mod } nm)\) なら \(a \equiv b \ \ (\text{mod } n)\)

13. \(\operatorname{gcd}(m, n) = 1\) なら

    \[ (a \equiv b \ \ (\text{mod } m) \ \operatorname{\text{\footnotesize AND}} \ a \equiv b \ \ (\text{mod } n)) \ \ \longleftrightarrow \ \ a \equiv b \ \ (\text{mod } mn) \]

14. \(\operatorname{gcd}(a, n) = 1\) なら \(a^{n-1} \equiv 1 \ \ (\text{mod } n)\)

15. \(a, b > 1\) なら「\(b\) を法とする剰余算術で \(a\) が逆元を持つ \(\ \ \longleftrightarrow \ \ \) \(a\) を法とする剰余算術で \(b\) が逆元を持つ」

次に示す \(\text{(a)}\) から \(\text{(j)}\) は数論的な命題である。常に正しい命題もあれば、何らかの前提条件があれば正しい命題もある。前提条件の選択肢は \(\text{(i)}\)-\(\text{(viii)}\) に示してある。それぞれの命題が「常に正しい」「前提条件があれば正しい」「どの前提条件があっても正しくない」のどれかを答えよ。「前提条件があれば正しい」を選んだときは、どの前提条件が必要か答えること。ただし、最も特定的な前提条件を選んだ場合にのみ満点が与えられる。例えば \(\operatorname{gcd}(a, b) > 1\) のとき正しい命題に対して \(\operatorname{gcd}(a, b) > 2\) を答えると部分点しか与えられない。

全ての変数の変域は適切な整数全体の集合とする。例えば \(\mathbb{Z}_{k}\) を考えているときは \(k > 1\) であり、変数 \(x \in \mathbb{Z}_{k}\) は \([0..k)\) に属する。

前提条件:

1. \(\operatorname{\text{\footnotesize NOT}} (a \; | \; b)\)
2. \(\operatorname{gcd}(a, b) = 1\)
3. \(\operatorname{gcd}(a, b) > 1\)
4. \(\operatorname{gcd}(a, b) > 2\)
5. \(\operatorname{gcd}(a, b) = 1 = \operatorname{gcd}(a, c)\)

6. \(a\) が素数

7. \(b\) が素数

8. \(a\), \(b\) が両方とも素数

命題:

1. 任意の整数係数多項式 \(p(x)\) に対して、\(a = b \ \ (\mathbb{Z}_{n})\) なら \(p(a) = p(b) \ \ (\mathbb{Z}_{n})\)

2. \(a \; | \; bc\) なら \(a \; | \; c\)

3. \(\operatorname{gcd}(1 + a, 1 + b) = 1 + \operatorname{gcd}(a, b)\)

4. \(1\) に等しい \(a^{2}\) と \(b^{2}\) の整数線形結合が存在しない。

5. \(2\) に等しい \(a^{2}\) と \(b^{2}\) の整数線形結合が存在しない。

6. \(ma = na \ \ (\mathbb{Z}_{b})\) なら \(m = n \ \ (\mathbb{Z}_{b})\)

7. \(b^{-1} = c^{-1} \ \ (\mathbb{Z}_{a}^{\ast})\) なら \(b = c \ \ (\mathbb{Z}_{a}^{\ast})\)

8. \(m = n \ \ (\mathbb{Z}_{\phi(a)})\) なら \(b^{m} = b^{n} \ \ (\mathbb{Z}_{a})\)

9. \(m = n \ \ (\mathbb{Z}_{ab})\) なら \(m = n \ \ (\mathbb{Z}_{b})\)

10. \(a^{b} = a \quad (\mathbb{Z}_{b})\)

次の命題が正しいか正しくないかを答えよ。正しくない命題に対しては反例を示せ。全ての変数の変域は \(\mathbb{Z}\) とする。

1. 全ての \(a\), \(b\) に対して \(ax + by = 1\) を満たす \(x\), \(y\) が存在する。

2. 全ての \(m\), \(r\), \(k\) で \(\operatorname{gcd}(mb + r, b) = \operatorname{gcd}(r, b)\) が成り立つ。

3. 異なる二素数 \(p\), \(q\) に対して \(\phi(pq) = (p - 1)(q - 1)\) が成り立つ。ここで \(\phi\) は Euler の \(\phi\) 関数を表す。

4. \(a\) と \(b\) の両方が \(d\) と互いに素なら、次の関係が成り立つ:

   \[ ac \equiv bc \quad (\text{mod } d) \ \ \longrightarrow \ \ a \equiv b \quad (\text{mod } d) \]

\(n\) が \(2\) でも \(5\) でも割り切れないとき、\(n\) と \(n^{k}\) の最下位三桁が一致するような \(k\) を答えよ。

ヒント: Euler の定理を使う。

1. \((-12)^{482}\) が \(175\) を法とする剰余算術で乗法に関する逆元を持つ理由を説明せよ。

2. \(\phi(175)\) の値を求めよ。ここで \(\phi\) は Euler の \(\phi\) 関数を表す。

3. \(0\) 以上 \(174\) 以下の整数の何らかの冪が \(175\) を法として \(1\) と合同なとき、その整数をパワフル (powerful) と呼ぶことにする。\(0\) 以上 \(174\) 以下の整数をランダムに選択したとき、パワフルな整数が選択される確率を求めよ。

4. \((-12)^{482}\) を \(175\) で割った剰余を求めよ。

1. \(35^{86}\) を \(29\) で割った剰余を求めよ。

2. \(\text{(a)}\) より、\(35^{86}\) を \(29\) で割った剰余が \(1\) でない。よって次の「証明」には誤りが含まれている:

   \[ \begin{aligned} 1 &\not \equiv 35^{86} &&(\text{(a) より}) \\ & \equiv 6^{86} && (35 \equiv 6 \ \ (\text{mod } 29) \text{ より}) \\ & \equiv 6^{28} && (86 \equiv 28 \ \ (\text{mod } 29) \text{ より}) \\ & \equiv 1 && (\text{Fermat の小定理より}) \end{aligned} \]

   ただし合同算術の法は \(29\) である。誤りが含まれる行を指摘し、何が間違いなのか説明せよ。

1. 素数 \(p\) と整数 \(n > 0\) が \(p \; | \; n\) を満たすなら \((p - 1) \; | \; \phi(n)\) だと示せ。

2. 全ての整数 \(n > 2\) に対する \(\phi(n)\) は偶数だと示せ。

1. \(\phi(6042)\) を計算せよ。

   ヒント: \(6042\) は \(53\) で割り切れる。

2. \(6042\) と互いに素な全ての整数 \(k > 0\) で \(k^{9361} \equiv k \ \ (\text{mod } 6042)\) である理由を説明せよ。

\(S_{k}\) を次のように定める:

ここで \(p\) は奇素数、\(k\) は \(p - 1\) の正の倍数とする。次の条件が成り立つ \(a \in [0..p)\) と \(b \in (-p..0]\) を答えよ:

RSA を解読しようとしている攻撃者が、RSA で使われる \(n\) を素因数分解して \(n = pq\) を満たす異なる素数 \(p\), \(q\) を発見したとする。この攻撃者が \(p\), \(q\) と公開鍵 \((e, n)\) を使って私有鍵 \((d, n)\) を計算し、公開鍵で暗号化した任意のメッセージを解読する方法を説明せよ。

RSA が \(n = pq\) を利用していて、\(p\), \(q\) は異なる \(200\) 桁の素数だとする。メッセージ \(m \in [0..n)\) が \(\operatorname{gcd}(m, n) = p\) を満たすとき、\(m\) は危険 (dangerous) と呼ぶことにする: RSA の解読で必要な \(n\) の素因数分解を求めるとき \(m\) を利用できる可能性が生じるためである。\([0..n)\) に属するメッセージが危険である確率に最も近い値を次から選べ:

Benベン Bitdiddleビットディドル は自身が持つ全てのデータを RSA で暗号化したのだが、私有鍵を失くしてしまった。一晩中探しても見つからず途方に暮れていると、部屋に置いてあったランプから妖精が飛び出してきた！ 妖精は、RSA による暗号化で使われた巨大な整数 \(e\), \(d\), \(n\) に関する次の手続きのいずれか一つを彼のために実行すると提案した。データを復元するために、Ben はどの手続きの実行を妖精に頼むべきだろうか？ データの復元が可能になる選択肢を全て選べ:

1. \(\operatorname{gcd}(e, d)\) を計算する。

2. \(n\) を素因数分解する。

3. \(n\) が素数かどうかを判定する。

4. \(\operatorname{rem}(e^{d}, n)\) を計算する。

5. \(\mathbb{Z}_{n}\) における \(e\) の逆元を見つける。

6. \(\mathbb{Z}_{\phi(n)}\) における \(e\) の逆元を見つける。

RSA を実際に使ってみよう！ いくつかのチームに分かれ、次の指示に従って暗号文を送受信せよ:

1. 前準備ステップを実行する:

   • 比較的小さな (\(10\) 以上 \(40\) 以下程度の) 異なる二素数 \(p\), \(q\) を選択する。実際のアプリケーションでは数百桁の素数が使われるものの、余り大きすぎると紙と鉛筆で扱えなくなる。

   • \(e = 3, 5, 7, \ldots\) を順に試し、\(\operatorname{gcd}(e, (p-1)(q-1)) = 1\) が成り立つ \(e \in [0..n)\) を見つける。最大公約数の計算では Euclid のアルゴリズム (第 9.2.1 項) を利用する。

   • \(\mathbb{Z}_{(p-1)(q-1)}\) における \(e\) の逆元 \(d \in [0..d)\) を計算する。粉砕法 (第 9.2.2 項) を利用する。

前準備ステップが終わったら、公開鍵を黒板に書くこと。これで他のチームがあなたのチームに暗号化されたメッセージを送信できるようになる。

2. 他のチームの公開鍵を利用して、暗号化されたメッセージを送信する。送信する機密メッセージは次の暗号帳から選択せよ:

   • \(2 = \text{ご挨拶申し上げます}\)
   • \(3 = \text{調子どう？}\)
   • \(4 = \text{遅いぞ！}\)
   • \(5 = \text{All your base are belong to us}.\)
   • \(6 = \text{こっちのチームの一人は、そっちのチームの一人が気になってるぞ}\)
   • \(7 = \text{You \textit{are} the weakest link. Goodbye!}\)

3. 他のチームから受け取ったメッセージを復号して、正しく復号できていることを確認する！

1. RSA は公開鍵に含まれる \(n\) の素因数分解が分かると簡単に解読できるのと同じように、\(\phi(n)\) が分かった場合にも RSA は簡単に解読できる。その理由を説明せよ。

2. \(n\), \(\phi(n)\) が既知で、加えて \(n\) が二つの素数の積だと分かっているなら \(n\) を簡単に素因数分解できると示せ。

RSA に関して当然ながら重要な事実の一つとして、暗号化されたメッセージを復号すると必ず元のメッセージ \(m\) が得られることがある。具体的に言えば、\(p\), \(q\) が二つの異なる素数で \(n = pq\), \(m \in [0..pq)\) および

のとき、次の等式が成り立つ必要がある:

これを証明しよう。

1. \(m\) と \(n\) が互いに素のとき、等式 \(\text{(9.40)}\) が Euler の定理から直ちに従うことを示せ。

後は \(m\) と \(n\) が互いに素という制限を取り除く必要がある。つまり、等式 \(\text{(9.40)}\) が全ての \(m \in [0..n)\) で成り立つと示したい。

メッセージ \(m\) を RSA で暗号化して送信するとき、\(m\) と \(n\) が互いに素でない可能性を心配する現実的な理由 ── そして、両者が互いに素であることを確認する現実的な理由 ── が存在しない事実を理解することは重要である。RSA の仕組みは素因数分解の難しさを利用しており、\(m\) が \(n\) と互いに素でないなら \(\operatorname{gcd}(m, n)\) の計算を通して \(n\) を素因数分解できる。つまり、RSA の安全性を信じるとき、メッセージ \(m\) が \(n\) と互いに素でない確率が無視できる程度だと信じることになる。

ただここでは、非現実的な理論を考える純粋数学者になって、正確に言えば必要ない (しかし現実的にはそもそも成立しない) 前提条件を取り除いてみよう。そうすることの利点の一つとして、RSA に関する命題が前提条件に言及する必要がなくなり単純になる。さらに重要なこととして、次に示す証明は「\(n\) の素因数を個別に考えることで \(n\) の性質を示す」という有用なアプローチの例である。

1. \(p\) が素数で \(a \equiv 1 \ \ (\text{mod } p - 1)\) なら、次の等式が成り立つと示せ:

   \[ m^{a} = m \quad (\mathbb{Z}_{p}) \tag{9.41}\]

2. \(p_{0}\), \(\ldots\), \(p_{j}\) を相異なる素数とする。「全ての \(i \in [0..j]\) で \(a \equiv b \ \ (\text{mod } p_{i})\) なら \(a \equiv b \ \ (\text{mod } p_{0}\cdots p_{j})\)」という事実の初等的⁴な証明を示せ。

3. 等式 \(\text{(9.40)}\) は次の主張の特殊ケースである:

   主張

   \(n\) が相異なる素数の積で \(a \equiv 1 \ \ (\text{mod } \phi(n))\) なら、次の等式が成り立つ:

   \[ m^{a} = m \quad (\mathbb{Z}_{n}) \]

   この主張をここまでの結果を使って証明せよ。

RSA は四半世紀以上にわたって暗号学的な攻撃に耐えてきたものの、RSA を解読できたら素因数分解を簡単に実行できるかどうかは分かっていない。

この問題では、この安全性保証を持った Rabinラビン 暗号 (Rabin cryptosystem) を考える。つまり、Rabin 暗号を効率的に解読する手続きからは二素数の積を効率的に素因数分解する手続きが得られる。

この事実が暗号の強さを示すのはどうしてだろうか？ 数学者は素因数分解を効率的に実行する方法を数世紀にわたって研究しているものの、一つとして見つかっていないからである。Rabin 暗号が効率的な素因数分解への「抜け道」になっている可能性は非常に低い。

Rabin 暗号は次のように動作する。\(p \equiv q \equiv 3 \ \ (\text{mod } 4)\) を満たす巨大な二素数 \(p\), \(q\) を用意して、その積 \(N = pq\) を公開鍵とする。メッセージ \(m\) を Rabin 暗号で相手に伝えるには、\(\operatorname{rem}(m^{2}, N)\) を相手に送信する⁵。

私有鍵は \(N\) の素因数分解、つまり二つの素数 \(p\), \(q\) である。まず、\(p\), \(q\) を知っていれば受け取ったメッセージを復号できると示す必要がある。さらに、\(p\) と \(q\) を知らず暗号化されたメッセージだけを知っている盗聴者にはメッセージの復号が困難であることも証明が必要になる。

\(N\) を法とする合同算術で \(s\) が平方数 (square) とは、\(s \equiv m^{2} \ \ (\text{mod } N)\) を満たす整数 \(m \in [0..N)\) が存在することを言う。また、このとき \(N\) を法とする合同算術で \(m\) は \(s\) の平方根 (square root) と言う。

1. \(5\) を法とする合同算術では、どんな整数が平方数か？ \([0..5)\) に属するそういった平方数は、それぞれ平方根をいくつ持つか？

2. \([1..15)\) に属する \(15\) と互いに素な整数は、\(15\) を法とする合同算術における平方根をそれぞれいくつ持つか？ なお、そういった平方根もまた \(15\) と互いに素となる。その証明は与えないものの、これは一般的な結果である。

3. 素数 \(p\) が \(p \equiv 3 \ \ (\text{mod } 4)\) を満たすと仮定する。このとき、\(p\) を法とする合同算術における平方数はちょうど \(2\) 個の平方根を持つと示そう。まず \((p + 1) / 4\) が整数だと示し、それから \(p\) を法とする合同算術における \(1\) の二つの平方根を求めよ。その上で、\(p\) を法とする合同算術では任意の整数の平方根がその \((p + 1)/4\) 乗に等しいと示せ。つまり整数 \(s\) に対して \(m ::= \operatorname{rem}(s^{(p+1)/4}, p)\) とすれば \(s \equiv m^{2} \ \ (\text{mod } p)\) だと証明せよ。

4. 中国剰余定理 (問題 9.61) からは、\(p\), \(q\) が異なる素数なら「\(pq\) を法とする合同算術において \(s\) が平方数」と「\(p\) および \(q\) を法とする合同算術の両方で \(s\) が平方数」が同値だと分かる。特に、\(x \neq x^{\prime}\) で \(s \equiv x^{2} \equiv (x^{\prime})^{2} \ \ (\text{mod } p)\) かつ \(y \neq y^{\prime}\) で \(s \equiv y^{2} \equiv (y^{\prime})^{2} \ \ (\text{mod } q)\) なら、\(s\) は \(N = pq\) を法とする合同算術でちょうど \(4\) 個の平方根を持つ。具体的には次の \(4\) 個である:

   \[ s \equiv (xy)^{2} \equiv (x^{\prime}y)^{2} \equiv (xy^{\prime})^{2} \equiv (x^{\prime}y^{\prime})^{2} \quad (\text{mod } N) \]

   よって \(p\) と \(q\) が分かれば、\(\text{(c)}\) の結果を使うことで \(s\) の平方根を計算できる。言い換えれば、私有鍵さえあれば復号は簡単に実行できる。

   では、\(p\) と \(q\) が分からない場合はどうだろうか？

   悪意ある攻撃者が \(N\) を法とする合同算術における任意の平方数の \(4\) 個の平方根を計算できるプログラムを持っているとする。このとき、攻撃者は \(N\) の素因数分解を効率的に計算できると示せ。つまり、何世紀にもわたって数学者たちが取り組んできたにもかかわらず解答を見つけられていない問題を解けるほど聡明な攻撃者でなければ、そのような平方根計算プログラムは書けない。つまり、そんなプログラムが存在する可能性は非常に低い！

   ヒント: \([1..N)\) からランダムに \(r\) を選ぶ。もし \(\operatorname{gcd}(N, r) > 1\) なら後は易しい (なぜか？)。そうでないなら、存在が仮定されているプログラムを使って \(r\) の平方根を全て計算する。平方根を \(r\), \(-r\), \(r^{\prime}\), \(-r^{\prime}\) とすれば \(r^{2} \equiv (r^{\prime})^{2} \quad (\text{mod } N)\) である。これを使って \(N\) を素因数分解するにはどうすればいいだろうか？

5. 送信されるメッセージの選択肢が二つしかない (例えば「夜明けに会合」と「夕暮れに会合」だけ) と悪意ある攻撃者が知っていて、特定の暗号化されたメッセージがどちらを意味するかだけを知りたいとする。この状況で攻撃者は Rabin 暗号を破ることができるか？

RSA 暗号の仕組みは理解できたと思う。続いて、RSA を解読するのが難しい理由を考えよう。この問題では、私有鍵を見つける問題が少なくとも整数の素因数分解と同程度に難しい事実を見る。暗号学コミュニティ (大規模な金融機関を説得できるほどの権威を持つ) では数百桁の整数の素因数分解には天文学的な計算資源が必要になると広く信じられているので、数百桁の RSA の私有鍵を見つけるのにも同様の途方もない労力が必要になることはまず間違いない。よって RSA の公開鍵から私有鍵が計算されることはないだろうと確信できる⁶。

この問題では \(p\), \(q\) は奇素数で \(n = p \cdot q\) と仮定する。RSA の公開鍵と私有鍵をそれぞれ \((e, n)\), \(d\) として、\(c ::= e \cdot d - 1\) と定める。

1. \(\phi(n)\) が \(c\) を割り切ると示せ。

2. \(4\) が \(c\) 割り切ると結論付けよ。

3. \(\operatorname{gcd}(r, n) = 1\) なら \(r^{c} \equiv 1 \ \ (\text{mod } n)\) だと示せ。

\(n\) を法とする合同算術における \(m\) の平方根 (square root) とは、\(s^{2} \equiv m \ \ (\text{mod } n)\) を満たす \(s \in [0..n)\) を言う。次の有用な性質は証明せずに使用する: \(n\) が二つの奇素数の積なら、\(\operatorname{gcd}(m, n) = 1\) を満たす任意の整数 \(m\) は \(n\) を法とする合同算術で平方根を \(4\) 個持つ。

特に、\(1\) には平方根が \(4\) 個ある。その \(2\) 個は \(1\) と \(n - 1\) (\(n\) を法として \(-1\) と合同) という自明なものである。これら以外の \(2\) 個の平方根を \(1\) の非自明な平方根 (nontrivial square root) と呼ぶ。

4. \(c\) が既知なら、任意の整数 \(r\) に対して \(r^{c/2}\) を \(n\) で割った剰余 \(y\) を計算できる。このとき \(y^{2} \equiv r^{c} \ \ (\text{mod } n)\) である。\(r\) が \(n\) と互いに素なら、\(\text{(c)}\) より \(y\) は \(n\) を法とする合同算術における \(1\) の平方根だと分かる。

   もし \(y\) が \(n\) を法とする合同算術における \(1\) の非自明な平方根なら、\(n\) を素因数分解できると示せ。

   ヒント: \(y^{2} - 1 = (y + 1)(y - 1)\) から、\(y + 1\) は \(q\) と \(p\) のいずれか一方でのみ割り切れると示す。

5. \(n\) と互いに素な正整数 \(r < n\) の少なくとも半分に対して \(\text{(d)}\) の \(y\) は \(1\) の非自明な平方根となる。この事実を使って、RSA の公開鍵 \((n, e)\) と私有鍵 \(d\) を知っているなら \(n\) の素因数分解が可能になる理由を説明せよ。

Alice と Bob が RSA 暗号で安全にメッセージをやりとりしている。二人は公開鍵を誰にでも見える形で公開し、私有鍵は自分以外の誰にも知らせない。その上で RSA の通常通りに使用すれば、機密メッセージを公開の通信経路上で送受信できる。

あるとき、Bob は受け取ったメッセージの送信者が本当に Alice だと確信できないことに気が付いた ── Alice と名乗る別人が送信者かもしれない。RSA を利用して偽造不可能な「署名 (signature)」をメッセージに加えると、この懸念を払拭できる。Alice がメッセージ \(m\) に偽造不可能な署名を付けて Bob に送信するには、RSA を使ってメッセージ \(m\) を暗号化するとき Bob の公開鍵ではなく自分の私有鍵で \(m\) を使用する。この結果 \(m_{1}\) を「署名付きメッセージ」として Bob に送信する。

1. Bob が Alice から受け取った署名付きメッセージ \(m_{1}\) を元のメッセージ \(m\) に復号する方法を説明せよ。\((n_{A}, e_{A})\) を Alice の公開鍵、\(d_{A}\) を Alice の私有鍵とすること。\(m \in [0..n_{A})\) を仮定してよい。

2. RSA が解読されないと信じるとき、Bob は \(m_{1}\) の送信者が Alice だと確信できる。その理由を説明せよ。

3. 署名付きメッセージ \(m_{1}\) から元のメッセージ \(m\) を復号する処理は Bob だけではなく Alice の公開鍵を知ってさえいれば誰でも実行できる。Alice が署名付き機密メッセージを公開の通信経路越しに送信するには、どうすればいいだろうか？