５７．２つの素数

　すぐに忘れてしまうので、備忘しておこうと思う。

　フェルマーの定理は有名で、

　　　xⁿ + yⁿ = zⁿ を満足するような自然数の組、x、y、zは、自然数n が3以上の時に

　　　は存在しない

と表される。これ以外に、「フェルマーの小定理」なるものがある。

　　　p を素数として、p と互いに素（1以外に共通の約数を持たない）である x に

　　　対して

　　　　　x^p = x (mod p)

ここで、x (mod p) というのは、pで割った余りが x になるということ。たとえば、p=5 として、x=2 としてみると

　　　2¹ = 2 = 2 (mod 5 )

　　　2² = 4 = 4 (mod 5 )

　　　2³ = 8 = 3 (mod 5 )  （8を5で割ったら、1余り3だから、余りの3を書く）

　　　2⁴ =16 = 1 (mod 5 ) （16を5で割ったら、3余り1だから、余りの1を書く）

　　　2⁵ = 32 = 2 (mod 5 )

たしかに、x=2、p=5 でx^p = 2⁵ = 2 (mod 5) = x (mod p=5) になっている。もう一つ。たとえば、p=7、x=3。

　　　3¹ = 3 = 3 (mod 7 )

　　　3² = 9 = 2 (mod 7 )

　　　3³ = 27 = 6 (mod 7 )  （27を7で割ったら、3余り6だから、余りは6）

　　　3⁴ =81 = 4 (mod 7 )  （81を7で割ったら、11余り4だから、余りは4）

　　　3⁵ = 243 = 5 (mod 7 ) （243を7で割ったら、34余り5だから、余りは5）

　　　3⁶ =729 =1 (mod 7 )    (729を7で割ったら、104余り1だから、余りは1）

　　　3⁷ = 2187 = 3 (mod 7 ) （2187を7で割ったら、312余り3だから、余りは3）

やっぱり、x=3、p=7 でx^p = 3⁷ =3 (mod 7) = x (mod p) になっている。一般的な証明は良いことにしておこう。

　上の表を眺めると、ついでに

　　　　x^p－1 = 1 (mod p)

であることもわかる。x¹ から x^p－1 を、mod p で表すと、1 から p－1 までの数が 1 回ずつ現れている。必ず 1 回だ。

　さて、こんな数学が、web での暗号化に使われている。公開鍵暗号と呼ばれるものだ。

　どうするかというと、

　１．2つの（大きな）素数 p、q を考え、その積

　　　　　n = p×q

　　　を作る。

　２．p－1、q－1 の最小公倍数を求め、これを L とする。L より小さい数から、L と

　　　互いに素となる数 r をとる。

　３．n と r は公開する。

　４．r×k を L で割ると、余りが 1 になる数  k を探す。k は秘密にする

　　　　　r×k = 1 (mod L)

ここからはメッセージを送る人の作業。

　５．送りたいメッセージを整数化し（例えばアルファベットに整数を割り振って並べ

　　　ればよい）、これをm とする。公開されている r を使って

　　　　　C = m^r  (mod n)

　　　を計算し、相手に送る。

今度は、受け手。受け取った数字　C からもとのメッセージ m を復元したい。

　６．秘密の数 k を使って

　　　　　m' = C^k  (mod n)

　　　を計算すると

　　　　　m' = m

　　　と、もとのメッセージが復元される。

実際、n = p×q なので、とりあえず送られてきた C を代入し、秘密の k を使って

　　　　m ' = C^k (mod n) = m^(r×k)  (mod n)

と、m ' を計算する。ここで、r×k は L で割ると余りが1だったので、ある整数をN 'として

　　　　r×k = 1 + L×N　

と書けるはず。L は p－1 と q－1の最小公倍数なので、p－1 でも q－1でも割れるので、ある整数を N として、

　　　　r×k = 1 + (p－1)×(q－1)×N　

とも書ける。こうして、

　　　　m ' = C^k (mod n) = m^(r×k)  (mod n)

　　　　　　= m×(m^{(p－1)(q－1)})^N  (mod p×q)

　　　　　　= m (mod n)

最後に、x^p = x (mod p) のフェルマーの小定理から派生していたx^p－1 = 1 (mod p) を用いた。正確にはフェルマーの小定理から派生するオイラーの定理

　　　　M^{(p－1)(q－1)} = 1 (mod p×q)

を用いる。こうやって、秘密の数 k を用いてメッセージは復元できる。

　n とr を公開しても、k は秘密で、秘密の k がバレナイ限り、n と r を知っていただけではメッセージは復元できない。k を知るには最初の数 p と q が解ればよいが、2つの素数の積から素因数分解でもとの 2 つ素数を見つけるのは難しい。小さい素数だったら簡単だが、大きな素数の積ではお手上げだ。（１．）で「2つの（大きな）素数p、q・・・」としたのはその為だ。例えば、n=5086067897 と見せられて、

　　　　5086067897 = 62753 × 81049

と素因数分解できまい（ちなみに右辺は0から9までのすべての数を使った）。もっと小さな

　　　　58493

という数を見せられても2つの素数の積にするのは面倒だ（これは小さいので頑張ればすぐにできるが）。

　大きい素数を使うと電卓で計算できないので、例として

　　　　p = 3 、q = 5

でやってみよう。（１．）2つの素数だ。積 n は

　　　　n = p q = 15

さらに（２．）p－1、q－1を計算して、最小公倍数 L を求めるのだった。

　　　　p－1 = 3－1 = 2、　

　　　　q－1 = 5－1 = 4

　　　　L  ( =  2 と 4 の最小公倍数) = 4

L と共通の約数を持たない L より小さい数 r を考えるのだった。 r =3 としよう。（３．）n = 15 と r = 3 は公開。次に秘密の k を作る。（４．）r×k = 1 (mod L ) だったので、

　　　　3×k = 1 (mod 4)

なので、ここでは

　　　　k = 7

ととってみよう。3×7 = 21 を4で割ると5余り1だからOK。（５．）メッセージ m を送ってもらおう。電卓でできる範囲の数として、

　　　　m = 8

としてみる。こうして、

　　　　C = m^r (mod n) = 8³ (mod 15) = 2 (mod 15)

8³ = 512 なので、15 で割ると 34 余り 2。この数 2 を受け取る。さて、復元。（６．）m'=C^k (mod n) とするのだった。秘密の鍵 k は 7 だった。

　　　　m ' = C^k (mod n)  =  2⁷  (mod 15) = 8

2⁷ =128 なので、15 で割ると、8 余り 8。たしかに、メッセージ m = 8 が再現された。

　さて、前述の数、58493。これも2つの素数の積に分解できる。

　　　　　58493 = 2017 × 29

今年は、西暦2017年で、平成29年だ。2017 も 29 も素数。ちなみに、この 2 つの素数を掛けた数 58493 の各桁の数をばらして足すと

　　　　　5 + 8 + 4 + 9 + 3 = 29

と、平成になる。また、次の関係があることを知った。

　　　　2¹ + 2² + 2³ + 2⁴ + 2⁵ + 2⁶ + 2⁷ + 2⁸ + 2⁹ + 2¹⁰

　　　＝2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024  

　　　( = 2¹¹ － 2 = 2×(2¹⁰ － 1) )

 　　　＝ 2046  　　　

　　　＝ 2017 + 29

今年はこんな年。