与えられた6つの文のうち、間違っているものをすべて選択します。

## 問題 (1) まとめ

1. 問題の内容

与えられた6つの文のうち、間違っているものをすべて選択します。

2. 解き方の手順

*

1. 素因数分解は、大きな数になるとコンピュータでも時間がかかるため、簡単に計算できるとは限りません。

*

2. RSA暗号は素因数分解の困難性を利用しています。

*

3. 誤り訂正符号の理論には線形代数が使われます。

*

4. RSA暗号では、公開鍵の一部として2つの巨大な素数の積が使われます。

*

5. 誤り訂正符号は、必ず誤りを訂正できるとは限りません。訂正能力を超える誤りがある場合は訂正できません。

*

6. 誤り訂正符号の理論は、情報通信や半導体の業界で広く使われています。

3. 最終的な答え

1, 5

## 問題 (2) RSA暗号

1. 問題の内容

$p = 11$, $q = 19$, $n = pq = 209$, $e = 7$とし、$c = 9$が暗号化された結果であるとき、元の数字（平文）$m$を求めます。ここで、暗号化は$c \equiv m^e \pmod{n}$で行われます。つまり、復号化は$m \equiv c^d \pmod{n}$で行われます。$d$は$ed \equiv 1 \pmod{\phi(n)}$を満たす数です。ここで、$\phi(n) = (p-1)(q-1)$です。

2. 解き方の手順

1. $\phi(n) = (p-1)(q-1) = (11-1)(19-1) = 10 \times 18 = 180$を計算します。

2. $ed \equiv 1 \pmod{\phi(n)}$より、$7d \equiv 1 \pmod{180}$となる$d$を求めます。拡張ユークリッドの互除法を用いると、$d = 103$となります。

3. $m \equiv c^d \pmod{n}$より、$m \equiv 9^{103} \pmod{209}$を計算します。

4. $9^{103} \pmod{209}$を手計算するのは大変なので、べき乗を小さくするために、繰り返し二乗法を使用します。

$9^2 \equiv 81 \pmod{209}$

$9^4 \equiv 81^2 \equiv 6561 \equiv 6561 - 31*209 \equiv 6561 - 6479 \equiv 82 \pmod{209}$

$9^8 \equiv 82^2 \equiv 6724 \equiv 6724 - 32*209 \equiv 6724 - 6688 \equiv 36 \pmod{209}$

$9^{16} \equiv 36^2 \equiv 1296 \equiv 1296 - 6*209 \equiv 1296 - 1254 \equiv 42 \pmod{209}$

$9^{32} \equiv 42^2 \equiv 1764 \equiv 1764 - 8*209 \equiv 1764 - 1672 \equiv 92 \pmod{209}$

$9^{64} \equiv 92^2 \equiv 8464 \equiv 8464 - 40*209 \equiv 8464 - 8360 \equiv 104 \pmod{209}$

$103 = 64 + 32 + 4 + 2 + 1$なので、

$9^{103} \equiv 9^{64} \times 9^{32} \times 9^4 \times 9^2 \times 9^1 \equiv 104 \times 92 \times 82 \times 81 \times 9 \pmod{209}$

$104 \times 92 \equiv 9568 \equiv 9568 - 45 * 209 \equiv 9568 - 9405 \equiv 163 \pmod{209}$

$82 \times 81 \equiv 6642 \equiv 6642 - 31 * 209 \equiv 6642 - 6479 \equiv 163 \pmod{209}$

$163 \times 163 \times 9 \equiv 26569 \times 9 \equiv (26569 - 127 * 209) \times 9 \equiv (26569 - 26543) \times 9 \equiv 26 \times 9 \equiv 234 \equiv 234 - 209 \equiv 25 \pmod{209}$

3. 最終的な答え

25

## 問題 (3) 誤り訂正符号

1. 問題の内容

動画内(p.15)の設定に基づき、Bさんが(1,1,0), (0,0,0), (1,1,1), (0,0,1), (1,0,0)を受信しました。Aさんが元々送信した5桁の0と1の列を、多数決に基づく誤り訂正によって推定します。

2. 解き方の手順

各桁ごとに、受信した信号の中で0と1の数を数え、多数決でAさんが送信した値を決定します。

* 1桁目: 1, 0, 1, 0, 1。1が3回、0が2回。よって、1と推定。

* 2桁目: 1, 0, 1, 0, 0。0が3回、1が2回。よって、0と推定。

* 3桁目: 0, 0, 1, 1, 0。0が3回、1が2回。よって、0と推定。

* 4桁目: 0, 0, 1, 1, 0。0が3回、1が2回。よって、0と推定。

* 5桁目: 0, 0, 1, 0, 0。0が4回、1が1回。よって、0と推定。

3. 最終的な答え

10000