57.2つの素数
すぐに忘れてしまうので、備忘しておこうと思う。
フェルマーの定理は有名で、
xn + yn = zn を満足するような自然数の組、x、y、zは、自然数n が3以上の時に
は存在しない
と表される。これ以外に、「フェルマーの小定理」なるものがある。
p を素数として、p と互いに素(1以外に共通の約数を持たない)である x に
対して
xp = x (mod p)
ここで、x (mod p) というのは、pで割った余りが x になるということ。たとえば、p=5 として、x=2 としてみると
21 = 2 = 2 (mod 5 )
22 = 4 = 4 (mod 5 )
23 = 8 = 3 (mod 5 ) (8を5で割ったら、1余り3だから、余りの3を書く)
24 =16 = 1 (mod 5 ) (16を5で割ったら、3余り1だから、余りの1を書く)
25 = 32 = 2 (mod 5 )
たしかに、x=2、p=5 でxp = 25 = 2 (mod 5) = x (mod p=5) になっている。もう一つ。たとえば、p=7、x=3。
31 = 3 = 3 (mod 7 )
32 = 9 = 2 (mod 7 )
33 = 27 = 6 (mod 7 ) (27を7で割ったら、3余り6だから、余りは6)
34 =81 = 4 (mod 7 ) (81を7で割ったら、11余り4だから、余りは4)
35 = 243 = 5 (mod 7 ) (243を7で割ったら、34余り5だから、余りは5)
36 =729 =1 (mod 7 ) (729を7で割ったら、104余り1だから、余りは1)
37 = 2187 = 3 (mod 7 ) (2187を7で割ったら、312余り3だから、余りは3)
やっぱり、x=3、p=7 でxp = 37 =3 (mod 7) = x (mod p) になっている。一般的な証明は良いことにしておこう。
上の表を眺めると、ついでに
xp-1 = 1 (mod p)
であることもわかる。x1 から xp-1 を、mod p で表すと、1 から p-1 までの数が 1 回ずつ現れている。必ず 1 回だ。
さて、こんな数学が、web での暗号化に使われている。公開鍵暗号と呼ばれるものだ。
どうするかというと、
1.2つの(大きな)素数 p、q を考え、その積
n = p×q
を作る。
2.p-1、q-1 の最小公倍数を求め、これを L とする。L より小さい数から、L と
互いに素となる数 r をとる。
3.n と r は公開する。
4.r×k を L で割ると、余りが 1 になる数 k を探す。k は秘密にする
r×k = 1 (mod L)
ここからはメッセージを送る人の作業。
5.送りたいメッセージを整数化し(例えばアルファベットに整数を割り振って並べ
ればよい)、これをm とする。公開されている r を使って
C = mr (mod n)
を計算し、相手に送る。
今度は、受け手。受け取った数字 C からもとのメッセージ m を復元したい。
6.秘密の数 k を使って
m' = Ck (mod n)
を計算すると
m' = m
と、もとのメッセージが復元される。
実際、n = p×q なので、とりあえず送られてきた C を代入し、秘密の k を使って
m ' = Ck (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 ' = Ck (mod n) = m(r×k) (mod n)
= m×(m(p-1)(q-1))N (mod p×q)
= m (mod n)
最後に、xp = x (mod p) のフェルマーの小定理から派生していたxp-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 つ素数を見つけるのは難しい。小さい素数だったら簡単だが、大きな素数の積ではお手上げだ。(1.)で「2つの(大きな)素数p、q・・・」としたのはその為だ。例えば、n=5086067897 と見せられて、
5086067897 = 62753 × 81049
と素因数分解できまい(ちなみに右辺は0から9までのすべての数を使った)。もっと小さな
58493
という数を見せられても2つの素数の積にするのは面倒だ(これは小さいので頑張ればすぐにできるが)。
大きい素数を使うと電卓で計算できないので、例として
p = 3 、q = 5
でやってみよう。(1.)2つの素数だ。積 n は
n = p q = 15
さらに(2.)p-1、q-1を計算して、最小公倍数 L を求めるのだった。
p-1 = 3-1 = 2、
q-1 = 5-1 = 4
L ( = 2 と 4 の最小公倍数) = 4
L と共通の約数を持たない L より小さい数 r を考えるのだった。 r =3 としよう。(3.)n = 15 と r = 3 は公開。次に秘密の k を作る。(4.)r×k = 1 (mod L ) だったので、
3×k = 1 (mod 4)
なので、ここでは
k = 7
ととってみよう。3×7 = 21 を4で割ると5余り1だからOK。(5.)メッセージ m を送ってもらおう。電卓でできる範囲の数として、
m = 8
としてみる。こうして、
C = mr (mod n) = 83 (mod 15) = 2 (mod 15)
83 = 512 なので、15 で割ると 34 余り 2。この数 2 を受け取る。さて、復元。(6.)m'=Ck (mod n) とするのだった。秘密の鍵 k は 7 だった。
m ' = Ck (mod n) = 27 (mod 15) = 8
27 =128 なので、15 で割ると、8 余り 8。たしかに、メッセージ m = 8 が再現された。
さて、前述の数、58493。これも2つの素数の積に分解できる。
58493 = 2017 × 29
今年は、西暦2017年で、平成29年だ。2017 も 29 も素数。ちなみに、この 2 つの素数を掛けた数 58493 の各桁の数をばらして足すと
5 + 8 + 4 + 9 + 3 = 29
と、平成になる。また、次の関係があることを知った。
21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 210
=2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024
( = 211 - 2 = 2×(210 - 1) )
= 2046
= 2017 + 29
今年はこんな年。