だいぶ以前、大学時代「数学科教育法」という授業に参加していたとき、公開鍵暗号として有名なRSA暗号というものについて、すこし知っていたことを発表しました。しかし、その暗号が具体的にどのように使われるのかいまいちピンと来ていなかったから、ちょっと整理するために書いてみます。教育法の講義だから、高校生に授業するときのネタとして覚えておきたいという動機だったのですが、そういう素材としてはちょっと難易度が高いものかも知れません。


―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*―*

たとえばインターネットで買い物をするときに、クレジットカードの番号を入力・送信するようなことがよくあるが、途中で情報が流出して、誰かにその番号を盗み見られるようだとまずい。そこでRSA暗号を使うと、次のようにカード番号を暗号化して送信することができる。

買い物をする人をA、注文を受ける側をB、Aさんのカード番号をxとする。Bはある数n,eを公開していて（ただしn>x）、Aさん側はx^e（xのe乗）を計算し、それをnで割った余りcを暗号文としてBに送信する。ここでeはxを暗号化しているから「公開鍵」と呼ばれる。で、cを受け取ったBは、Bだけが持っている「秘密鍵」dを使って、c^dを計算し、それをnで割ると余りがxとなって、カード番号を受け取ることに成功する（＊1）。

（実際のインターネットの商取引が全くこのままの形で行われているのかどうかは分からないが、ネットで使われる暗号は基本的にこのようなものではあるまいか。またアルファベットも数字で置き換えることが可能だから、「パスワード」の暗号化も同じ方法で出来る。）

で、その原理は、高校生にきちんと伝えるのは困難かもしれず、実際には適当にはしょりながら説明することになるだろうけど、だいたい以下の通り。

まず、記号の説明。
整数a, b, nがあって、a-bがnで割り切れるとき、
a ≡ b (mod n)
と書き、「aとbはnを法として合同である」と読む。これは、aをnで割ったときの余りと、bをnで割ったときの余りが同じである、といいかえてもよい。
また、aをnで割ったときの余りがcなら a ≡ c (mod n) で、とくにaがnで割り切れるなら a ≡ 0 (mod n).
ここで、a ≡ b, c ≡ d (mod n) のとき
a + c ≡ b + d (mod n),
a - c ≡ b - d (mod n),
ac ≡ bd (mod n)
のように、「≡」を「＝」のように思って和、差、積が計算できるということが重要で、以下この事実を暗に使う。

（高校のカリキュラムでは合同式は基本的にやらないようだ。ただ僕が高校生のときはやらされたし、今も合同式の話が出来る高校の教室があると信じたい。）

で、次の定理が必要になる。

■フェルマーの小定理:
pが素数、xが整数のとき、
x^p ≡ x (mod p).
とくにxがpで割り切れないなら
x^{ p-1} ≡ 1 (mod p). (証明は＊2)

つまり最初の式は、x^p-xがpで割り切れる、後の式はx^{ p-1} -1がpで割り切れるということ。。。
（あ、素数というのは、2,3,5,7,11,13のように、「1とそれ自身以外では割り切れない正の整数」のことです。ただし1は素数に含めません。）

で、カード番号の受け渡しの話で使われたRSA暗号は以下の原理に基づいている。

p,qを相異なる素数とし、n = pq, φ(n) = (p-1)(q-1) とする。
またeをφ(n)と互いに素な正の整数とする（つまりeとφ(n)の最大公約数が1ということ）。
こういう状況のとき、ed + φ(n)f = 1 となる整数d,fが存在することが知られていて、またここでd > 0としてよいことが分かる。このとき、
0≦x< n なら　x^{ ed} ≡ x (mod n).

∵）k = -fとすれば ed = kφ(n)+1 = k(p-1)(q-1)+1となるが
i ) xがpの倍数でないとき
フェルマーの小定理から x^{ p-1} ≡ 1 (mod p) となるから、
x^{ ed} = x^{ 1+k(p-1)(q-1)} = x(x^{ k(p-1)(q-1)} )
= x(x^{ p-1} )^{ k(q-1)} ≡ x (mod p).
ii ) xがpの倍数のとき
x^{ ed} ≡ x ≡0 (mod p).
i ),ii )より、x^{ ed} -x はpの倍数。同様にして、x^{ ed} -x はqの倍数であることも分かる。
結局、x^{ ed} -x は n=pq の倍数となる（∵p,qは相異なる素数）。つまり
x^{ ed} ≡ x (mod n).　□

上のn,eは「公開」されており、p, q, d は「秘密」になっている。
もとのインターネットでの買い物の話に戻ると、Aさんはn,eを知らされているが、p, q, d はBの側しか知らない。
x^eをnで割った余りがcということは x^e ≡ c (mod n)で、cが暗号文としてBに送信されたが
c^d ≡ (x^e)^d = x^{ ed} ≡ x (mod n).
つまりカード番号xを、Aは公開鍵eで暗号化してBに送ったが、BはBだけが持っている秘密鍵dでそれを解読してxを知る、ということになる。

p,qは秘密、従ってφ(n)=(p-1)(q-1)もBしか知らないということが大事で、eとφ(n)を知っている者は秘密鍵も知ることが出来る。
実際、eとφ(n)は互いに素だったから、eu+φ(n)v = 1 となる整数u,vがある。このようなuを見つければ（それはそう難しくない）、dと一致はしないかもしれないが、秘密鍵としてdと全く同じように使え、暗号文を見破ることが出来る。

n = pqで、nは公開されているのだから、秘密のp,qを求めるのは難しくないようにも見える。nが小さな数なら実際難しくないが、ただ巨大な数になってくると、素因数p,qに分解するのは一般に難しいことと信じられている。
仮にnが100桁を超える数だとすると、p,qは同時に50桁を超える可能性があるが、例えば10^50までに存在する素数の個数は、素数定理によっておよそ(10^50)/log(10^50)≒8.7×10^47個。単純に考えると、pやqを知るには、これだけの素数について１つ１つnを割る計算をしなければならないが、１つの計算に1/10^10秒しかかからなかったとしても、最悪10^30年（100万年の1兆倍の1兆倍）以上かかることになる。
ただ因数分解や素数について得られている知識から、実際はそんなしらみつぶしの計算はやらなくてよい。事実、最近は数百台のコンピュータを連結して、効率的な方法で何ヶ月か計算させ続けることで、困難と思われていた百数十桁の数の分解に成功したりということも起きている。で、nの桁数を上げていくことで、現在も暗号の安全性を保つことが図られていると聞く。

つまり現在のところ電子化社会の秩序は、「大きな数の素因数分解の難しさ」に負う部分が非常に大きいといえる。


上の例はAからの暗号文をBが解く、という一方通行の暗号になっている。
双方向にするためには、上に現れたn, p, q, e, dのような数を二組用意する。
つまりn_1, p_1, q_1, e_1, d_1; n_2, p_2, q_2, e_2, d_2 を用意し、ここで n_1, e_1, n_2, e_2 は公開され、p_1, q_1, d_1 はAが所有する秘密、p_2, q_2, d_2 はBが所有する秘密とする。
このときAからBへ、またBからAへ暗号を送るのに、上と全く同じ方法でもやれるがそれだと面白くないから、次のようにする。
Aからxを暗号化してBに送るとき、まず秘密鍵d_1で暗号化して、
x^d_1 ≡ y (mod n_1)
となったとする。次にyを公開鍵e_2で暗号化して
y^e_2 ≡ z (mod n_2)
として、zをBに向けて送信する。Bは秘密鍵d_2でzを開錠できて
z^d_2 ≡ y (mod n_2).
yはまた公開鍵e_1で解読できて
y^e_1 ≡ x (mod n_1).
つまり、Bは元の文xを得られた。
BからAに暗号を送るときも同様にする。公開鍵e_1でyを解読できるということで、Bはそれが秘密鍵d_1で施錠されたものだとわかり、送信者がAであることが確かめられるという利点がある。つまりこれは「デジタル署名つき」の暗号となる。



＊1：ただcを傍受した者がいたら、n,eが公開されていてx^e-cがnで割り切れることから、もしxが小さな数なら実行可能な計算の範囲内でxを推測できてしまうかも知れない。だからxはカード番号でも16桁に限らず、もっと大きな数でもよいことにして、その下16桁をカード番号と読むことにすれば、暗号文cの傍受者もxを特定するのがより困難になるのではないか（xをカード番号そのままにしても暗号は充分実用にたえる、と言っている本も見たので、実際は16桁のままやっているのかも知れない）。


＊2:
pが素数、xをpで割り切れない整数とする。
x, 2x, 3x, ... ,(p-1)x をそれぞれpで割ったときの余りは全て異なっている。
（∵ 相異なるs,t(0< s< t< p) について、sx,txをpで割ったときの余りが等しいとすると、tx-sx = (t-s)x はpで割り切れる。pは素数だからt-s かxのどちらかはpで割り切れることになるが、仮定からxはpで割れず、また 0< t-s< p よりt-sもpで割れないから矛盾する。）
そこでxをpで割ったときの余りをr_1、 2xをpで割ったときの余りをr_2、 3xをpで割ったときの余りをr_3,...などとする。
上で述べたことから、r_1, r_2, ... ,r_{ p-1} は全て異なっていて、0を含まないこともすぐ分かるから、これらは1,2, ... ,p-1を並べ替えたものである。これと
x≡r_1、 2x≡r_2、 ... 、(p-1)x≡r_{ p-1} (mod p)
であることを合わせると、上の合同式に関する注意から
1・2・3・...・(p-1)・x^{ p-1} = x・2x・3x・...・(p-1)x
≡ r_1・r_2・r_3・...・r_{ p-1} = 1・2・3・...・(p-1) (mod p).
よって、
1・2・3・...・(p-1)・x^{ p-1} - 1・2・3・...・(p-1) = 1・2・3・...・(p-1)・(x^{ p-1} -1)
はpで割り切れる。素数pは 1・2・3・...・(p-1)を割り切らないから、x^{ p-1}-1がpで割り切れる。
よって
x^{ p-1} ≡ 1 (mod p).
xがpで割り切れるときは、x^p-x = x(x^{ p-1} -1)がpで割り切れるのは明らかだから
x^p ≡ x (mod p). □


(c) 2009 ntr ,all rights reserved.

整数論をあまり勉強したことがないが、次のような問題をときおりいじくりまわして遊んでいる。

自然数nに対して、n自身を除くその約数の全ての和をS(n)と書くことにする。
ただしS(1)は定義しない。

例えば8のそれ自身を除く約数は1,2,4だから、S(8)=1+2+4=7。
また6のそれ自身を除く約数は1,2,3だから、S(6)=1+2+3=6。
また12のそれ自身を除く約数は1,2,3,4,6だから、S(12)=1+2+3+4+6=16。

8の場合のように、S(n)＜nとなるnを輸数とよび、
6の場合のように、S(n)＝nとなるnを完全数とよび、
12の場合のように、S(n)＞nとなるnを豊数とよぶ。

1でない自然数nに対して、S(n)= mとなる自然数mがただ一つ存在する。このとき「n → m」（または「m ← n」）と書くことにする。

(注1)
n に対してS(n)= mとなる m はただ一つだから、相異なる m,m' に対し「n → m かつ n → m'」となることはない。
一方、S(64)=1+2+4+8+16+32=63,S(177)=1+3+59=63だから、
64→63,177→63。
つまり、相異なるn,n' に対し「n → mかつn' → m」となることはある。□

このようにして、全ての自然数を「点」とし、→を「辺」とする「無限有向グラフ」が作られる。
つまり、平面に全ての自然数が散らばっていて、自然数相互が→でつながっているイメージ。

自然数m,nに対し、m = m_0,m_1,m_2,...,m_k = n (k≧0)なる自然数の列があって、各i= 1,...,k に対し、m_{i-1}とm_iが→または←でつながっている状態のとき、「m～n」と書くことにする。
m～nであるというのは、mから矢印の列をたどっていくとnに到達する、というイメージ。
m～nの「～」という関係は同値関係である。すなわち

1)任意の自然数mに対してm～m,
2)m～nならばn～m,
3)k～mかつm～nならば、k～n。

従って関係「～」で自然数全体を同値類別できる。1つの同値類に属する自然数が形作っているグラフを「連結成分」とよぶことにする。点nの属する連結成分は、nから「→,←」という辺をたどって到達できる点（自然数）全体のなす塊り、というイメージ。つまり異なる連結成分どうしは辺でつながっておらず、自然数全体が連結成分によってきれいに区分けされている。

■問題1
連結成分は無数に存在するか。□


m=m_0→ m_1 → m_2 →...→ m_k = m (k≧1)
（ただし「i＞0またはk＞j」でi≠jのとき、m_i ≠ m_j）

となっているとき、m_0, m_1,...,m_kは、長さkのループをなすという（つまりmから始まって→でk回進むと、またmに戻るということ）。
mが長さ1のループをなすということは、m = m_0 → m_1 = m だからm → m,すなわちS(m)=mで、mが完全数であることを意味している。
m,nが長さ2のループをなしているとき（つまりm → n → m）、m,nは友愛数とよばれる。
つまりm,nが友愛数であるとは、m ≠ nであって「S(m)=nかつS(n)=m」がなりたつことである。
例えば、S(220)=1+2+4+5+10+11+20+22+44+55+110=284, S(284)=1+2+4+71+142=220,よって「220と284」は友愛数である。
（長さ3以上のループをなす自然数たちを「社交数」とよぶこともあるらしいが、あまり一般的なネーミングではないようだ。）

■命題1
1つの連結成分の中に、ループがあるとすればただ1つ。

(∵)　1つの連結成分の中にループが2つあったとし、m,nをその各々のループに属する自然数とする。m～nだから、
m = m_0, m_1, m_2, ..., m_k = n (k≧0)
なる自然数の列があって、各i=1,...,kに対し、m_{i-1}とm_iが→または←でつながっていなければならない。今k>1とすると、m_1,...,m_{k-1}はループに属さない点としてよい。mはループに属する点m' に対してm → m'だから、上の(注1)によりm ← m_1でなければならない。同様に、n←m_{k-1}でなければならない。これより1≦i≦k-1なるあるiに対して、m_{i-1}← m_i → m_{i+1}となっていなければならないが、これは(注1)からありえない。同様にk=0,1の場合も矛盾する。□

この命題1から、ループが無限個存在すれば、連結成分も無限個存在することになり、問題1は解決する。
そこで次のような問題も考えられる。

■問題2
任意の自然数kに対して、長さkのループは存在するか。
存在するとすれば、いくつあるか（無限個存在するか）。□

長さ1のループ（すなわち完全数）が無数に存在するかどうかはまだ知られていない（と思う。たとえばメルセンヌ数が無数に存在することがわかれば解決する）。
長さ2のループ（すなわち友愛数）が無数に存在するかどうかもまだ知られていない（と思う）。
長さ3以上のループに関しても、同様に未知ではないだろうか。


■問題3
m_0 → m_1 → m_2 → m_3 →... (ただしi≠jならm_i≠m_j)
なる無限列は存在するか。□


与えられたnに対し、S(m)=nとなるようなmは、複数存在することもあり、また存在しないこともある。
例えば、S(m)=2となるようなmや、 S(m)=5となるようなmは存在しない。

■問題4
与えられたnに対し、S(m)=nとなるようなmをすべて求める一般的な方法は？　□


(注2)
n=p_1^r_1×p_2^r_2×...×p_k^r_k
のように素因数分解されているとき（ただしp_1,...,p_kは相異なる素数）、
S(n)=(1+p_1+p_1^2+...+p_1^r_1)(1+p_2+p_2^2+...+p_2^r_2)...(1+p_k+p_k^2+...+p_k^r_k)-n
と書ける。□

(注3）
pが素数ならば、S(p)=1。従って全ての素数pに対し、p → 1。つまり1に向かって、無限個の辺が伸びている。
そして無限個の辺が集まっている点は1のみ。実際、与えられたn(≠1)に対して、n → mなるmはただ1つで、n ← kなるkがいくつありえるかを考えてみると、kのそれ自身をのぞく約数の和がnだから、逆に見れば、nを相異なる自然数の和に分割するある仕方に（ただ1つの）kが対応している。ところがnを相異なる自然数の和に分割する仕方は有限個しかない。従ってn ← kなるkは有限個しかない。□

(c) 2009 ntr ,all rights reserved.

「孫の手」があるなら「祖父の背中」も売られていていいはずだと思うのだが、しかしそれがどんな用途のものなのかよく分からない。たとえば「猫の爪とぎ」のようなものか。

猿、猫、象などは人のあだ名として使えるようである。しかし犬、豚などは罵倒の言葉として使われる。「犬」が下劣な人間を指すのはどこから来ているのだろう。「豚」が罵倒語なのは、その太った姿、何でも食うところからだろうし、こちらは分かりやすい気がする。
たとえば「プロゴルファー猿」はありえても「プロゴルファー豚」はありえないだろう。

英語の名詞の「単複同型」は面白い。羊 sheep が単複同型なのは、羊は群れているのが当たり前だからだろうか。羊の群れは雲にも似ていて、不可算のもののようにも見える。しかし鹿 deer も単複同型だが、鹿は群れていない姿もよく見かける。鯉 carp はどうだろうか。ただ鯉が百歩譲って数えられない存在だとしても、広島カープの選手は明らかに数えることができる。

外国人になじみのない人は、外国人がみな同じに見えたりする。猫になじみのない人にとっては、どの猫も同じ顔をしているように見える。しかし猫を飼うようになったり、注意して見るようになると、どの猫の顔も違って見えるようになってくる。では単細胞生物を研究している人は、どのゾウリムシも違って見えたりするのだろうか。ゾウリムシに個性はあるのだろうか。

プログラマをしていたころ、先輩たちはよくコンピュータを擬人化し、「この人」「この子」などと呼んだ。僕の職場ではとくに女性のプログラマにその傾向が強く、コンピュータのメモリ、CPUなどの部品をも擬人化し、あたかも劇のようにコンピュータの原理を説明するのだった。これは一種の「女性らしさ」なのか、ずっと疑問に思っていたが、他の職場ではどうなのだろう。

コアラはカンガルーと同じく「有袋類」で、お腹にポケットがついている。ただカンガルーとはポケットの向きが逆で、コアラの赤ちゃんが顔を出すとそこは親の股間である。コアラの赤ちゃんはそれでいいと思っているのだろうか。

美男美女であったり高学歴であったりということは、他人がうらやみもするが、本人たちには負担に感じることもある。たとえば高学歴なのに無能であると、必要以上に罵倒されるものである。それと同じように、グレートデンやボルゾイのような立派な外見の犬が野良犬だと、明らかに変な印象を受ける。彼らも内心は大変なはずである。

このあいだ学校の近くで、忙しくのたうつ蛇を見たのだが、つくづく思ったのは、こんな手も足もない姿では決して人間のようには文明を築けないだろう、ということだった。蛇は、この世に生れたときからそう決まっていたようなものである。文明を発展させようという欲求も、もとからないのだろう。しかしほとんどの動物はそうではなかろうか。してみると人間が今日の文明を築いてきたのは、別に優れていたとかそういうことではなく、ただちょっと変わっていたから、と捉えるべきではなかろうか。


(c) 2009 ntr ,all rights reserved.