何かにおいて、２人のうちどちらが先にするかを決めたいとき、よくやるのはジャンケンである。サッカーの試合のときは、コイントス（開始前に審判の投げたコインの表裏で、場所や先行を決める）が行なわれる。
　２人が同じ場にいなくて、どちらが先にするかを電話で決めたいときは、どうしたらいいだろう。ジャンケンを言葉でやるという方法もあるが、同時に発しては聞き取りにくいし、遅出しした、しないでもめる。コイントスは、相手がコインを投げた場合、自分が「表」と言えば、「残念でした、裏でした」と言われるに違いない。
　というわけで、電話ではジャンケンもコイントスも使えない。何かいい方法があるだろうか、ということが今回の話題である。

　この問題について、Ｂｌｕｍ（ブラム）という人の考え出した方法があり、「暗号がわかる本」（イオタゼミ著：オーム社）という本で紹介されている。「法による素因数分解」という、ちょっとした数学を使うのである。少々面倒ですぐには理解できないが、これがおもしろい原理である。受け売りであるが、他人に話せずにはおられない。

　太郎と花子が、電話でコイントス（太郎がコインを投げて、花子が表か裏を言い当てれば花子の勝ち、はずれれば太郎の勝ち）をしたいのであるが、先に述べたようにこれは電話ではできない。そこで、コイントスと同じことを、別な方法でやろうというのである。
　話をわかり易くするために、先に要点となる状況を述べておきたい。

　○　花子が、ある問題を解けたら花子の勝ち、解けなかったら太郎の勝ち、とする。
　○　この問題は、２つの数 ａ と ｂ を知っていれば解けるが、１つしか知らないと解けないものである。 花子は ａ、ｂ のどちらか１つしか知らないので、問題が解けない。 太郎は ａ、ｂ の両方を知っていて、花子にどちらかを教えなければならないのだが、花子がどちらの数を知っているのかは知らない。
　○　だから、太郎が花子の知らない数を教えてしまうと、花子は問題が解けるので花子の勝ち、花子が既に知っている数を教えたら、花子は問題が解けないので太郎の勝ち、となる。

　花子に出される問題とは、太郎が勝手に決めた２つの素数の積 ｎ を、逆に２つの整数の積にせよ（素因数分解するという）というものであるが、上のような状況をどのようにして作るか、ということになる。
　理解を助けるために、わかりやすい小さな数値を用いて具体例で行うが、一般論を右枠に示しておく。

	具体例	一般論
（１）	まず、太郎が勝手に２つの素数 13 と 29 を選ぶ。そして、その積 13×29＝377 を花子に伝える。	まず、太郎が勝手に２つの素数 ｐ と ｑ を選ぶ。そして、その積 ｐ×ｑ＝ｎ を花子に伝える。
（２）	このままでは、花子は素因数分解できない。そこで、花子は好きな数 120 を決め、1202＝14400 を 377 で割ると、商は 38 で、余りは 74 を得るが、余り 74 を太郎に伝える。	一般には、ｎ は大きな数なので、花子は素因数分解できない。そこで、花子は好きな数 ａ を決め、ａ2 を ｎ で割ったっときの余りを ｒ とするとき、ｒ を太郎に伝える。
（３）	太郎は、74 に最初の 377 の何倍かを加えた数が、正の整数の２乗になるものを、次のように計算機で調べる。 　ｘ2＝74+0×377　より　x＝ 8.6… ダメ 　ｘ2＝74+1×377　より　x＝21.2… ダメ 　ｘ2＝74+2×377　より　x＝28.7… ダメ 　ｘ2＝74+3×377　より　x＝34.7… ダメ 　　　　… 　ｘ2＝74+10×377　より　x＝62　　　◎ 　　　　… 　ｘ2＝74+38×377　より　x＝120　　◎ 　ここで得られる２つの数 62 と 120 のうち、どちらか１つを花子に教える。	太郎は、ｒ に最初の ｎ の何倍かを加えた数が、正の整数の２乗になるものを、計算機で調べる。 　ｘ2＝ｒ＋０×ｎ 　ｘ2＝ｒ＋１×ｎ 　ｘ2＝ｒ＋２×ｎ 　ｘ2＝ｒ＋３×ｎ 　　　　… 　ｘ2＝ｒ＋ｋ1×ｎ　より　x＝ｂ 　　　　… 　ｘ2＝ｒ＋ｋ2×ｎ　より　x＝ｃ 　ｎ が２つの素数の積のときは、このような正の整数が２つ存在するのだそうである（なぜだ？ → ３つ以上あるわけがない。なぜなら、ｎ の約数が １、ｎ を除くと ２つしかないから）。 　ここで得られる２つの正の整数 ｂ、ｃ のうちの１つは花子が使った ａ である。太郎には、どちらが ａ に等しいのかはわからない。 ｂ を花子に教えるとする。
（４）	もし、太郎が教えた数が 62 であれば、花子が先に用いた 120 の数とを用いて 　　120+62=182 と 377 の最大公約数 あるいは、 　　120-62=58 と 377 の最大公約数 を求める。この場合、 　182＝2×7×13、　58＝と2×29 なので、これらと 377 の最大公約数より、それぞれ 13、29 を得る。よって、花子は 　　377=13×29 のように素因数分解でき、花子の勝ちとなる。 　もし、太郎が教えた数が 120 であれば、花子は上のようなことができない。よって、377 の素因数分解ができないので、太郎の勝ちとなる。	もし、太郎が教えた数 ｂ が ａ でなければ、花子は 　　ａ＋ｂ と ｎ の最大公約数 あるいは、 　　ａ−ｂ と ｎ の最大公約数 を求めると、それらが最初太郎が選んだ素数 ｐ か ｑ になるので、花子は ｎ の素因数分解ができ、花子の勝ちになる。 　もし、太郎が教えた数が ａ であれば、花子は上のようなことができない。よって、ｎ の素因数分解ができないので、太郎の勝ちとなる。

　最後の （４）のところを詳しく述べる。
　ａ² も ｂ² も ｎ で割ったとき、余りが同じ ｒ である
ということは、
　ａ²−ｒ も ｂ²−ｒ も ｎ で割りきれる
ということである。だから、これらの差
　（ａ²−ｒ）−（ｂ²−ｒ）＝ ａ²−ｂ² は ｎ で割りきれる
でなくてはならないが、
　ａ²−ｂ²＝ (ａ＋ｂ)(ａ−ｂ)
なので、 　(ａ＋ｂ)(ａ−ｂ) は ｎ で割り切れる。
　ところが、(ａ＋ｂ) および (ａ−ｂ) は ｎ で割り切れないので、(ａ＋ｂ) および (ａ−ｂ) が ｎ の約数で割り切れなくてはならない。したがって、
　　ａ＋ｂ と ｎ の最大公約数、および　 ａ−ｂ と ｎ の最大公約数
が ｎ の約数である ｐ か ｑ のどちらかになる、というわけである。

　実際にこれを行うには、太郎は（３）の手順で計算機を使わないと大変である（離散対数問題の困難性）。出された問題を解く花子の方は電卓程度でよいだろう。いずれにしても、２つの素数 ｐ と ｑ を相当大きな数に選ばなくてはならないだろうという気がするが、Ｂｌｕｍ（ブラム）氏の方法の理屈はとてもおもしろい。

(2005. 1.30)

　素因数分解の困難性：　「ｎ＝840036709 は２つの素数の積であるが、その２つの素数を見つけよ」 といわれたらどうするか。 いずれにしても計算機（パソコン）を使わなくてはならないが、私なら ｎの平方根以下の素数をすべて求めるプログラムでも作って、片っ端から求めた素数で ｎ を割ってみるだろう。 ｎ がこの程度の大きさなら、なんとかできる。だが、ｎ が 300 桁くらいのものを与えられたら、現在のどんな計算機を用いても不可能（少なくとも地球が消滅してしまわない時間内には）で、このことが、現代の暗号の原理とされている。