2008-02-26 Taoの仕事 CS math A remark on primality testing and the binary expansion « What’s new 論文の方を読む気はしないが面白い結果だなー. 十分大きなnについてnビットの素数pが存在し, i=0,...,n-1についてp \pm 2^iは全て合成数. 決定的な素数判定では全ビット読む必要があり, 計算量の下界としてo(log p)を得ると. 10進でも各桁を置き換えたときに素数じゃなくなる素数が存在するらしい.