公開鍵暗号(RSA)をわかる２

（続き）
割り算の余りの世界は四則計算が自由に行える世界であったが，累乗でパワー炸裂．
暗号化には累乗の計算をする．

たとえば，昨日の
　0= 7=14=21=28=35=42=49=56=63=70=77=…
　1= 8=15=22=29=36=43=50=57=64=71=78=…
　2= 9=16=23=30=37=44=51=58=65=72=79=…
　3=10=17=24=31=38=45=52=59=66=73=80=…
　4=11=18=25=32=39=46=53=60=67=74=81=…
　5=12=19=26=33=40=47=54=61=68=75=82=…
　6=13=20=27=34=41=48=55=62=69=76=83=…
の世界で，
　4^2 = 4×4 = 16 = 2
　4^3 = 4^2×4 = 2×4 = 8 = 1　　　← 4^2=2 を使う．
　4^4 = 4^3×4 = 1×4 = 4　　　　　← 4^3=1 を使う．
　4^5 = 4^3×4^2 = 1×2 = 2　　　　← 4^3=1 と 4^2=2 を使う．
　4^6 = 4^3×4^3 = 1×1 = 1　　　　← 4^3=1 を使う．
4^6 をまともに計算すると，4096 だが，そんな大きな計算をするまでも無く，「7で割った余りが 1」といえる．
つまり，今日（木曜日）の 4^6＝4096 日目は「金曜日」といえる．（1余るから）

(4^3)^5 = 4^3×4^3×4^3×4^3×4^3 = 4^15 = 4^(3×5) という性質と，今求めた4^3=1 を使うと，もっと巨大な指数でも
　4^2007 = 4^(3×669) = (4^3)^669 = 1^669 = 1
4^2007 をまともに計算すると，1209桁の巨大数だが，それを計算するまでも無く，「7で割った余りが 1」といえる．
つまり，「累乗でパワー炸裂」

7で割った余り 0,1,2,3,4,5,6 の累乗はこうなる．
0 や 1 は何乗してもかわらない．

　2^1 = 2
　2^2 = 4
　2^3 = 4×2 = 8 = 1
この先，2,4,1 の繰り返し．

　3^1 = 3
　3^2 = 9 = 2
　3^3 = 3^2×3 = 2×3 = 6
　3^4 = 3^3×3 = 6×3 = 18 = 4
　3^5 = 3^4×3 = 4×3 = 12 = 5
　3^6 = 3^5×3 = 5×3 = 15 = 1
この先，3,2,6,4,5,1 の繰り返し．

　4^1 = 4
　4^2 = 16 = 2
　4^3 = 4^2×4 = 2×4 = 8 = 1
この先，4,2,1 の繰り返し．

　5^1 = 5
　5^2 = 25 = 4
　5^3 = 5^2×5 = 4×5 = 20 = 6
　5^4 = 5^3×5 = 6×5 = 30 = 2
　5^5 = 5^4×5 = 2×5 = 10 = 3
　5^6 = 5^5×5 = 3×5 = 15 = 1
この先，5,4,6,2,3,1 の繰り返し．

　6^1 = 6
　6^2 = 36 = 1
この先，6,1 の繰り返し．

どれも累乗の計算では，同じ数字の繰り返しになる．
同じ数字の繰り返しになるから，累乗の計算はきわめて高速に実現する．
たとえば
　5^1000000 = 5^999996×5^4 = (5^6)^1165×2 = 1^1165×2 = 1×2 = 2

さて，7で割った余りの累乗の周期は，
　1, 2, 3, 6
の4通りあるが，
すべての数が元に戻るのは，周期が6の
　7乗，13乗，19乗，25乗，31乗，37乗，43乗，49乗，55乗，・・・
である．
この「元に戻る」性質を暗号と復号に使う．

RSA は Rivest Shamir Adleman 3人の頭文字だが，これを暗号に使うことを思いついたのはすごいなー

さて，暗号化には「累乗」を使うのだが，解読されない理由は
　「累乗の逆算ができない」
ことによる．確実に「元に戻す」には累乗を繰り返すしかないのだ．

たとえば，3乗で暗号化したとする．
ある数を3乗で暗号化したら，「6」になったとして，そのある数はなんだろうか．
上の計算表を見ると，
　3^3 = 6
　5^3 = 6
の2通りあって，決まらない．つまり
　「何を3乗して6になったのか確定しない」
のである．

古典的な暗号化では
　「暗号化の逆操作が復号」
なのだが，公開鍵暗号のポイントがこの
　「逆操作が不可能」
な点といえる．

（つづく）