わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

確率的手法により素数と判定しても実際には合成数の場合がある~結果解釈の非対称性

「それでは,素数判定の『確率的手法』と『確定的手法』について,整理したいと思います.
 『確率的手法』では,そのアルゴリズムの実行において,乱数を使用します.『乱択アルゴリズム』とも呼ばれます.
 そして,そのアルゴリズムが,与えられた入力に対して『素数でない』と判定したら,必ず素数でないのですが,もし『素数である』と判定したとき,実は,素数でなく,合成数であるという,可能性があるのです.
 フェルマーテストでも,ミラー-ラビンの素数判定法でも,そしてJavaのBigIntegerクラスのisProbablePrimeメソッド*1でも,言えることなのです」
 上記は,本日の授業で,学生に向けて言ったことの一部です.
 ところで,事前に学生自治会からメールで相談がありまして(毎年のことなのでOKしまして),授業のはじめに,自治会役員の信任投票の用紙と,学生自治会のアンケート用紙を配付していました.ともにA4サイズです.そして投票とアンケートの提出用に,自治会の役員の方は,記入したものを提出してもらう,色付きのボックス(受け皿)を用意していました.学生の机の最前列に,置くことになりました.
 授業終了時には,毎回書いてもらっている,A4を四分割したサイズの「授業メモ」は,こちらより毎回持参している,透明のプラスチックのボックス(受け皿)に提出してもらいます.
 受講生にとっては,2種類の提出先となります.
 用紙のサイズが異なるので,こちらのボックスに,A4の自治会関連の用紙が入ることはありません.
 しかし,あちらさんの色付きのボックスに…
 授業メモが紛れ込んでしまうと,それを見つけるのは(そしてこの教室の中では)ちょっと簡単ではありません.
 そんなことを思案していると,素数判定の確率的手法における結果解釈の非対称性と,つながってくるように,思えたのでした.

*1:https://docs.oracle.com/javase/jp/11/docs/api/java.base/java/math/BigInteger.html#isProbablePrime(int).去年の授業ではJava SE 8のドキュメントを参照していました.「必ず合成数である場合はfalse」が,分かりにくいなあ,原文ではどうなっているのかなと,調べてみると,https://www.tutorialspoint.com/java/math/biginteger_isprobableprime.htmに"false if it's definitely composite"と書かれていました.