読者です 読者をやめる 読者になる 読者になる

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)

 

であることもわかる。xから 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 = m (mod n)

   を計算し、相手に送る。

 

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

 6.秘密の数 k を使って

     m' = C (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)  =  2(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

 

今年はこんな年。

広告を非表示にする