ISEGORIA / 数学百科事典
数論：整数のパターン
合同式・素数・公開鍵の考え方を探ります。
前提知識: 代数と証明
予想してから操作し、計算例と問いで理解を確かめてください。グラフは数式の図示であり、証明ではありません。
1. 合同式の時計
整数を n 時間の時計に巻き付け、n 個ごとに螺旋を1周させます。2つの整数が n を法として合同なのは、同じ半直線上に来るときに限ります。右側では乗法を繰り返しの足し算として見ます。0 から大きさ a の歩幅で b 歩進むと a·b mod n の時刻に着き、a をその剰余に置き換えても着く場所は変わりません。
計算例. n=12では17と5は同じ剰余類です。
注意点. 合同は通常の等号ではなく同値関係です。
乗法が合同を保つのはなぜですか？
n が a − a′ を割り切るなら、ab − a′b = (a − a′)b も割り切るので ab ≡ a′b です。時計の上では、歩幅 a と歩幅 a mod n は同じ時刻に到達します。
2. エラトステネスの篩
1 から上限までの数を10個ずつ並べます。上限の平方根以下の各素数 p が、p² から始めて自分の倍数を自分の色で消していきます。1 を除いて残った数が素数です。再生を押すと素数ごとに篩が進みます。素数の個数 π(x) を x/ln x や対数積分 li(x) と比べてください。
計算例. 30 以下の素数は10個、100 以下は25個です。これに対し 100/ln 100 ≈ 21.7、li(100) ≈ 30.1 です。
注意点. 有限の x では π(x) は x/ln x とも li(x) とも一致しません。素数定理が述べるのは比が 1 に近づくことだけです。
消去を √x で止めてよいのはなぜですか？また各素数を p² から始めるのはなぜですか？
合成数には平方根以下の素因数があるからです。また k < p の倍数 kp はより小さな素因数をもつので、すでに消されています。
3. RSA鍵の直観
異なる2つの素数 p、q を選びます。公開鍵は N = pq と、φ(N) = (p − 1)(q − 1) と互いに素な指数 e です。秘密指数 d は φ(N) を法とする e の逆元です。左の図はすべてのメッセージの暗号化を同時に示し、剰余の置換になっています。右の図は復号がうまくいく理由を示します。m のべきは繰り返し、ed = 1 + t·φ(N) で m に戻ります。
計算例. p = 5、q = 11 なら N = 55、φ(N) = 40 です。e = 3 なら 3·27 = 81 ≡ 1 (mod 40) より d = 27 です。メッセージ 7 は 7³ mod 55 = 13 に暗号化され、13²⁷ mod 55 = 7 に戻ります。
注意点. 小さな例は安全ではありません。実際のRSAは巨大な素数とパディングを使います。
復号指数が特別なのはなぜですか？
φ(N) を法とする e の逆元なので、オイラーの定理により m^(ed) = m·(m^φ(N))^t ≡ m となります。N が平方因子をもたなければ、m が N と共通因数をもつ場合にも成り立ちます。