電話で2人がコイン投げの賭けをやります。A君、B君としましょう。2人で１万円を賭けてコイン投げをやっているのです。A君が表、B君が裏に賭けました。A君がコインを投げて、表が出ました。A君は自分が勝ったことをB君に話しますが、B君は信用してくれません。B君にしてみれば「ホントか！？」とでも言いたいところでしょう。コイン投げでなくてもよいのです。何か2人ともインチキのしようがない、電話越しのよい賭けはありませんか……？
たまたま2人の家では同じ新聞をとっていました。そこでB君は「先週の月曜の新聞の、3ページの最初の単語の字数が奇数か偶数か、で賭けないか？」と提案しましたが、A君は「おまえ、手元に新聞があって知ってるんだろ？」。だめですね。コインの裏表をＢ君に選ばせ、A君がコインを投げる様子をｗｅｂカメラで撮ってＢ君に送るのは？ これもだめ。Ａ君が動画に細工するかも知れないし、いくつも撮っておいて都合のいいものを送るかも知れません。
いい方法があります。Ａ君は大きな素数ｐ，ｑを用意します（素数というのは１と自分自身以外に約数のない数。例えば5は素数だが、6は素数ではない）。ｐもｑも大きな数、1000桁とか2000桁の数です。Ａ君はＢ君にｐとｑの積を伝えておきます（ｒ＝ｐｑとし、ｒを伝える。ｐとｑはB君にはナイショ）。ｑ＜ｐとしておきましょう。A君はＢ君に「小さい方、ｑの４桁目が奇数か偶数かを当ててくれ」と言います。当たればＢ君の勝ちです。勝敗をＢ君に確認させたければ、Ａ君が用意したｐ，ｑをＢ君に教えてやればよいのです。ｑの4桁目がＢ君の予想と一致しているか調べ、ｐ，ｑをかけ算すれば確かにｒになることを確認させることができます。5000桁でも10000桁でも、パソコンがあればかけ算など一瞬です。
ここで大事な問題がありますね。「積ｒをあらかじめＢ君に教えてしまったら、素因数分解されてｐ，ｑが分かってしまい、賭けにならないのではないか？」ということです。でもその心配はいりません。ｐ，ｑが大きな素数（1000桁とか）だったら、積ｒをＢ君に教えても素因数分解されることはないのです。素因数分解は非常に難しいということになっています。簡単だと思う人は、せいぜい2桁か3桁くらいの数しか相手にしていないからです（試しに4桁の数、1031を素因数分解してみてください。結構大変です。電卓を使ってもよいです。実は素数）。「非常に難しいということになっています」と書いたのは、そう証明されているわけではないからです。今のところ例えば「1000桁の数の素因数分解はこういう条件のコンピュータで×××万年かかる」みたいな証明がないのです。でも、素因数分解は困難であるという数学的な経験則を利用した暗号が実用になっています。例えば前にも書いたRSA暗号です。
このコイン投げの話は多分『情報セキュリティの科学―マジック・プロトコルへの招待』（太田和夫、渡辺治、黒沢 馨1995講談社ブルーバックス）にあったと思うのですが、今手元になく、はっきりしません。面白い話だなあ、と思った覚えがあります。こうした分野も面白そうで勉強してみたいのですが、難しそうです。がんばります。
