はじめに
先日、ツイッターでおもしろそうな理論(素数を使った合否発表システム)を発見しました。
受験番号をあらかじめ素数だけにしておけば、合否発表は1つの巨大な合成数を掲示するだけで済み、受験生はその合成数を自分の受験番号で割りきれるか否かで合否を知れるって仕組み、まじで使えそう
— 思垢くん (@everyday0utput) January 20, 2020
ネタのようにつぶやかれていましたが、個人的に結構使えるのでは?と思ったので試しに遊んでみました。
仕組みの簡単な説明
素数とは
1 より大きい自然数で正の約数が 1 と自分自身のみであるもののこと。
で例えば、「7」とかが該当します。逆に「6」は「2や3」で割り切れるから素数ではない。
素数と素数を掛け算すると素数ではなくなりますが、その合成数は素数と素数に一意に分解できます。
これが素因数分解で、素数である7と素数である11は、かけると77で分解すると7と11。
要は素数は掛け合わせても分解すれば一意に戻すことができるので、「受験番号をあらかじめ素数だけにしておけば、合否発表は1つの巨大な合成数を掲示するだけで済み、受験生はその合成数を自分の受験番号で割りきれるか否かで合否を知れる」ってなわけですね。
受験生が10人の場合
2,3,5,7,11,13,17,19,23,29
各位は上記の番号を振られます。
で、その中で「2」「13」「23」の3人が合格なのだとすればそれらの積「598」を合否発表として提示します。
すると受験生は自分の番号で割り算をします。
例えば受験番号11の人は「54.36363...」と割り切れないので不合格。受験番号13の人は「46」と割り切れるので合格。
実際に運用するとして
素因数分解が試験の出題範囲に入ってそうな、IPAの「応用情報技術者」の合格発表に使うと仮定します。
受験者は約5万人なので計5万の素数が必要ですが、素数は飛び飛びになっているので2から約60万までの間にある素数が必要なんですよね。例えば「599999」は素数なので受験番号になりえますがこのあたりは結構間が空いてしまいます。
... 599959 599983 599993 599999 ...
しかし、6桁の受験番号はざらなのでそれを各自に割り振るのは問題なさそう。
が、やばいのはこの合成数。
応用情報技術者は約1万人が合格するので例えば2から60万までの素数の中央値である「281381」あたりが1万回掛け算になるとすると10の「54492」乗になります。ちなみに無量大数は68乗。
割り算を電卓に入力するのも一苦労(5万桁を間違えずに入力する必要あり)ですし、そもそもそこまでの桁数を入力できるマシーンなさそう。
終わりに
素数を使ったおもしろい話ですが、実際問題で参加者が20人以下くらいであればなんとか使えそう。
ちなみにこの仕組みのいいところとして、他人の合否が分かりづらいというメリットもあるのでプライバシーの観点でもイケている気がしました。
以上です。