ある自然数 n が素数であるかどうかを決定論的に調べるには、少なくとも まで調べないといけない。 しかし確率論的に素数である可能性が高いということであれば、 で計算することができる。これは速度と確度のトレードオフというわけでなく、確率論的な判定…