(p-1)/2が素数かも一応調べといてな。

素数判定はミラー・ラビン判定が主流。
ぐぐってみな。