RSA の正当性

定理 6.1（「合同式とフェルマーの小定理」§6）・ ✓公理まで証明済み

$p \ne q$ を素数とし、 $n = pq$ 、 $\varphi(n) = (p-1)(q-1)$ とする。整数 $e, d$ が

ed \equiv 1 \pmod{\varphi(n)}, \qquad \gcd(e,\varphi(n)) = 1

を満たすとする。このときすべての整数 $m$ に対して

(m^{e})^{d} \equiv m \pmod n

が成り立つ。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 10 件、定義なども含めて 13 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義（直接 6 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

フェルマーの小定理✓定理 5.1・合同式とフェルマーの小定理
- ユークリッドの補題✓補題 2.3・合同式とフェルマーの小定理（上で展開済み）
- 消去法則✓命題 3.6・合同式とフェルマーの小定理
  - ユークリッドの補題✓補題 2.3・合同式とフェルマーの小定理（上で展開済み）
- 合同式の四則✓命題 3.3・合同式とフェルマーの小定理
合同式の四則✓命題 3.3・合同式とフェルマーの小定理
中国剰余定理✓定理 4.8・合同式とフェルマーの小定理
- 剰余環定義 4.1・合同式とフェルマーの小定理
- ユークリッドの補題✓補題 2.3・合同式とフェルマーの小定理（上で展開済み）
ユークリッドの補題✓補題 2.3・合同式とフェルマーの小定理
- ベズーの等式✓定理 2.2・合同式とフェルマーの小定理
  - 除法の原理✓定理 2.1・合同式とフェルマーの小定理
    整列性公理 3.1・証明の技術
オイラーの定理✓定理 5.3・合同式とフェルマーの小定理
- フェルマーの小定理✓定理 5.1・合同式とフェルマーの小定理（上で展開済み）
- オイラーのトーシェント関数定義 4.6・合同式とフェルマーの小定理
- 命題 4.4✓合同式とフェルマーの小定理
  - ベズーの等式✓定理 2.2・合同式とフェルマーの小定理（上で展開済み）
系 5.2✓合同式とフェルマーの小定理
- フェルマーの小定理✓定理 5.1・合同式とフェルマーの小定理（上で展開済み）
- 合同式の四則✓命題 3.3・合同式とフェルマーの小定理

これを使っている定理

証明で明示的に参照している定理は、まだありません。

RSA の正当性

閉包の状態

前提をたどる 証明が使う定理・定義（直接 6 件）

これを使っている定理

関連するノック 2 問

前提をたどる証明が使う定理・定義（直接 6 件）