試し割り法
与えられた整数 n (n はこれから素因数分解する整数)に対して、nより小さい数で割り切れるかどうかを順番に確かめることで素数判定を行う。nが2で割り切れる確率は、nが3で割り切れる確率より高いため、小さい数から順に素因数の候補として割り切れるかを確かめると効率的である。また、nが2で割り切れない場合には4で割り切れないことは明らかであるため、4で割り切れるかを確かめる必要はない。同様に、既に確かめた数の倍数について確かめる必要はないため、素因数候補として確かめる数を素数のみとすることで、労力を削減できる。また、nが何らかの数pで割り切れる場合、n=pqであり、qがpより小さい場合には既にqもしくはqの約数で確かめた際に素因数が検出されているはずである。したがって、素因数候補として確かめるべきは n {\displaystyle {\sqrt {n}}} までで十分ある。
試すべき素因数の個数の上限は簡単に求められる。Pi をi番目の素数とすると、P1=2, P2=3, P3=5.
両者とも、計算時間は桁数に対して指数関数的に増加する。
このように試し割り法は非常に時間がかかるアルゴリズムではあるが、最も効率の良い手法でも計算時間が桁数に対して指数関数的に増加するため、十分満足できる手法である。与えられた範囲の整数に対して素数判定をする場合、2で割り切れる確率は50%であり、3で割り切れる確率は約33%であり、88%の自然数は100未満の約数を持つ、92%の自然数は1000未満の約数を持つ。したがって、大きな整数aの素数判定を行う場合小さな素数で割り切れるかを確かめることは有用である。
しかし、小さな素数を約数として持たない巨大な数の素数判定は数日もしくは数カ月もかかる場合がある。そのような場合には、二次ふるい法や一般数体ふるい法(GNFS)のような他の手法が用いられる。しかし、これらの方法の(時間)計算量も超多項式時間であるため、実用上の限界は比較的すぐにやってくる。この性質を利用して、解読に素因数分解が必要である公開鍵暗号方式で素数の積が用いられる。公開鍵暗号ではスーパーコンピュータやグリッド・コンピューティングを用いても既知の素因数分解アルゴリズムでは実用的な時間で素因数分解できない大きさの素数の積を用いている。今までに素因数分解された暗号の最大の桁数は RSA-768 の768ビットであり、数百台の計算機で一般数体ふるい法を用いて、およそ2年の計算の結果、素因数分解された。