１：フェルマー法
アルゴリズム(フェルマー法): 予め決められた整数L と判定対象の整数p に対して以下を実行.
p = 素数の候補;
以下をL 回繰り返す{
1 < a < p なるa をランダムに生成;
if ( a p-1 mod p ≠ 1 ) p は素数でない;
};
p は多分素数;

２：ラビン法
アルゴリズム(ラビン法): 予め決められた整数L と判定対象の整数p に対して以下を実行.
p = 素数の候補;
p = 1 + 2kw を満たすk とw を計算（ただし, w は奇数）;
以下をL 回繰り返す{
1 < a < p なるa をランダムに生成;
y = aw mod p;
j = 0;
while ( ( j < k ) and ( y ≠ 1 ) and ( y ≠ p-1 ) ) {
y = y 2 mod p ;
j = j+1;
if ( ( j = k ) or (( j > 0 ) and ( y = 1 )) ) p は素数でない;
};
p は多分素数;