剰余算術(モジュラー算術)
数が法(modulus)で折り返される、余りの算術。古典暗号から現代暗号まで、ほぼすべての土台となる。
26を法とする算術では27は1に等しい。シーザー暗号が文字をアルファベットの端で折り返してずらすとき、使っているのはまさにこれである。アフィン暗号はこれを一般化して ax + b mod 26 とするが、暗号として復号できるためには、aが26と互いに素でなければならない。
同じ原理を、数百桁の数で行うのがRSAだ。大きな素数を使った冪剰余は、順方向には簡単に計算できるが、逆方向には秘密鍵が要る。つまり落とし戸関数である。暗号方式が余りの計算という地味なものに支えられているというのは、この分野のなかでも不思議な事実のひとつだ。