>>291
従来の素数判定法は↓の本に色々載ってる。
ttp://www.amazon.co.jp/exec/obidos/ASIN/4431709444/qid=1029050483/sr=1-1/ref=sr_1_2_1/249-5846017-4760349

実際に行われてる素数判定は、Miller-Rabin とかの
基本的な判定法を組み合わせた形で行われてる。
確率的な手法ゆえに、より効率的により正確に判定する
アルゴリズムが必要になり、その為に色々な素数判定法を
組み合わせてるわけだけど、この辺の話がすごくややこしい。
ある判定法で合成数と見抜けない合成数はどんな性質のもので、
それはどうすれば合成数と見抜けるかって話とかね。
ただ、一つ一つの素数判定法はそんなに難しい事を
やってるわけじゃない。RSAの仕組みが理解できる程度の
知識があれば十分理解可能。
ま、deterministic な方法が見つかった今となっては
さほど興味深い話ではないだろうけど。