0Pricing
Cryptology Academy · レッスン

剰余算の基礎

時計算と、それが暗号技術の中心となる理由を理解します。

「剰余算の基礎」はCoddyKit上の無料Cryptology Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCryptology Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Cryptology Academyコースには全4レッスンが含まれています。

ようこそ

モジュラー算術は「時計算」と呼ばれることもあり、AES、RSA、Diffie-Hellman、そしてほぼすべての現代暗号方式の数学的基盤です。

剰余とは

a mod mは、aをmで割ったときの余りです。17 mod 5 = 2です（17 = 3×5 + 2だからです）。Pythonでは、17 % 5 == 2となります。

時計算の直感的な理解

12時間時計では、10 + 5 = 3です（15ではありません）。これはmod 12の算術です。モジュラー算術では法の値で「一周して戻る」ため、暗号の計算にぴったりです。

モジュラー加算と減算

(a + b) mod m = ((a mod m) + (b mod m)) mod m 例：(19 + 23) mod 7 = (5 + 2) mod 7 = 7 mod 7 = 0

モジュラー乗算

(a × b) mod m = ((a mod m) × (b mod m)) mod m 例：(13 × 17) mod 11 = (2 × 6) mod 11 = 12 mod 11 = 1

モジュラーべき乗

RSAではa^b mod mを使います。大きな指数には、反復二乗法を使います。 2^10 mod 13: 2^2=4, 4^2=16≡3, 3^2=9, 9×2^2=9×4=36≡10。 Python: pow(2, 10, 13) → 10

モジュラー逆元

a^(-1) mod mは、a×x ≡ 1 (mod m)を満たす値xです。例：3^(-1) mod 7 = 5です。3×5=15≡1 (mod 7)だからです。RSAやアフィン暗号の復号で使われます。

拡張ユークリッドの互除法

拡張ユークリッドの互除法は、モジュラー逆元を効率よく計算します。Pythonでは、pow(3, -1, 7) == 5となります（Python 3.8以降では、powが負の指数をサポートします）。

フェルマーの小定理

pが素数なら、a^p ≡ a (mod p)なので、a^(p-1) ≡ 1 (mod p)です。 したがって、a^(-1) ≡ a^(p-2) (mod p)となります。 RSAの鍵生成や素数判定で使われます。

中国剰余定理（CRT）

CRTを使うと、複数の合同方程式を同時に解けます。RSAの復号では、pとqを法とする計算を別々に行ってから結果を組み合わせることで、計算を高速化します。

AESにおけるモジュラー算術

AESはGF(2^8)上で動作します。これは加算がXORで、乗算が既約多項式を法とする多項式演算になるガロア体です。AESのすべての算術演算はモジュラー演算です。

確認問題

Pythonでpow(2, 10, 7)を実行すると、いくつになりますか？

まとめ

モジュラー算術を習得しました！次は素数について学びます。素数がなぜ特別なのか、そして素因数分解がなぜRSAの安全性を支えているのかを見ていきます。

よくある質問

「剰余算の基礎」レッスンは無料ですか？

はい。「剰余算の基礎」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Cryptology Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Cryptology Academyコースには全4レッスンが含まれています。

「剰余算の基礎」で何を学びますか？

時計算と、それが暗号技術の中心となる理由を理解します。 ブラウザで直接実行するハンズオンコードでCryptology Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Cryptology Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCryptology Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「剰余算の基礎」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCryptology Academyレッスンでコードを書いて実行できますか？

はい。すべてのCryptology Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 2進数と16進数の基礎
  2. 剰余算の基礎
  3. 素数と素因数分解
  4. GCD、Eulerのトーシェント関数と数論入門
← Cryptology Academyに戻る