素数の研究はギリシア時代にかなり扱われているが、素数の研究が直接社会に使われるということは(私の理解では)あまりなかった。しかし、近年では非常に大きな数の素因数分解が容易にできないことが暗号技術に使われている。附属中で行っている選択授業「社会とつながる数学」で、この話題を取り上げてみた。(中学校3年9名が対象、45分1コマ)
前の授業では、エラトステネスのふるいで1000以下の素数を求める等、素数の話題を扱った。
まず、素数が暗号に利用されていることを説明し、暗号というものについて簡単に説明。説明の内容は以下の通り。
もとのメッセージに一定のルールで変更を加えることで暗号を作ることができ(暗号化)、メッセージを受け取った人が一定のルールで解読する(復号)ことで元のメッセージを読み取ることができる。たとえば、「元の数字に5を加える」というルールで暗号化し、「暗号から5を引く」というルールで復号すれば元の数字が伝わることになる。だが、基本的に暗号を作るルールがわかると暗号を解読するルールもわかってしまうため、暗号を作るルール(あるいは解読するルール)をお互いがどのように(他の人に知られずに)伝えるかが大きな課題となる。1970年代に開発されたRSA暗号という技術では、暗号を受け取る人が、暗号を作るルールを広く公開し、暗号を解読するルールは誰にも教えないということを(一応)可能にしている(公開鍵方式)。そこに素数の性質が使われている。
続いて、次の問題を扱った。生徒たちには電卓を与え、教員用PCではExcelをスクリーンに出している。
------------------------------
素因数分解してください。
(1) 4864
(2) 10080
(3) 1001
(4) 949
(5) 2231
(6) 146957
------------------------------
素因数分解すると、(1) 2^8・19、(2) 2^2・3^2・5・7、(3) 7・11・13、(4) 13・73、(5) 23・97、(6) 223・659 となる。電卓があるので(4)くらいまではそう苦労しないが、(5)以降は非常に困難である。途中で作業を打ち切らせ、Excelで、私がどのように素数の積を計算したかを見せた。1000までの素数表を作ってあるので、いくつかの素数の積を作ることは簡単だが、出された積を素因数分解することには(小さい素因数がない場合には)膨大な手間がかかることを確認する。積をつくることと素因数分解することとの間の、この手間の非対称性こそが、暗号(RSA暗号)で利用されている。
続いて、暗号のシミュレーションを行う。個々の生徒が私に暗号を送るということを行う。生徒全員に暗号の作り方を公開し、生徒から伝えられた暗号を私のPCのExcelのセルに入力すると、瞬時に元のメッセージが表示されるというもの。生徒に示した暗号の作り方は、以下の通り。
------------------------------
(1) 元のメッセージとして、15以下の自然数を決めてください。
(2) その数を3乗し、それを15で割った余りを計算してください。この数が、暗号です。
(3) 上で出た数を教えてください。
------------------------------
たとえば、暗号7をExcelに入れれば元の数13、暗号3を入れれば元の数12が出てくるという具合である。生徒9名全員の暗号を正確に解読することができた。
生徒たちには、上記(2)の手順で余りを出しており、余りから元の数を逆算することが困難である(すなわち逆算が容易に定義できない)ことを確認する。そして、解読する側では、上記(2)で使った15という数の素因数を知っていると逆算とは違う形で計算が可能であることを話す。ここは厳密な説明は断念し、手順を詳しく書いた以下のプリントを配布して短時間の説明をするにとどめた。
------------------------------
暗号づくりの手順
<暗号を受ける人(準備)>
(1) 素数を2つ決める。(p,qとする)ただし、pq>10とする。
(2) a=pq、d = n (p-1)(q-1)+1をそれぞれ計算する。ただし、この段階ではn =1とする。
(3) dの約数で1でもdでもないものを1つ決める。(bとする)
うまく約数が見つからないときには、nを2, 3, ...と変更して約数が見つかるnに変更する。
(4) a及びbの値を公表する。
<暗号を送る人(暗号化)>
(1) 送るメッセージとして、a以下の数を一つ決める。
(2) その数をb乗し、それをaで割った余りを計算する。出てきた数が暗号。
<暗号を受け取る人(復号)>
(1) 暗号の数をd /b乗し、それをaで割った余りを計算する。それが元の数。
------------------------------
この授業では、RSA暗号について厳密に扱うことを避けている。また、そもそも大きな2つの素数の積となる数を使う必要があり、15のような小さい数では実用性も低い。こうした限界のある授業である。