裁判部門

試行除法は、整数因数分解アルゴリズムの中で最も手間がかかるものの、理解しやすい方法です。試行除法の基本的な考え方は、因数分解対象の整数nが、 nの平方根以下の各数で割り切れるかどうかを順番にテストすることです。

例えば、 n = 70の素因数を求めるには、 70 を連続する素数で割ってみます。まず、70 ÷ 2 = 35。次に、2も3も35を割り切れません。最後に、35 ÷ 5 = 7となり、7 は素数です。したがって、70 = 2 × 5 × 7 となります。

試行分割は、フィボナッチが著書『算盤の書』（1202年）の中で初めて記述した。^{[ 1 ]}

整数n ( n は「因数分解する整数」を指す) が与えられたとき、試行除法は、n がそれより小さい数で割り切れるかどうかを体系的にテストすることから成ります。明らかに、nより小さい候補因数を、2 より小さい順にテストする価値があります。なぜなら、任意のnは 3 より 2 で割り切れる可能性よりも 3 で割り切れる可能性の方が高いからです。この順序では、数がすでに 2 で割り切れないと判断されている場合、4 で割り切れるかどうかをテストする意味はありません。3 や 3 の倍数などについても同様です。したがって、素数のみを候補因数として選択し、それらが割り切れなくなるまで繰り返しテストすれば、労力を削減できます。さらに、試行因数は、${\displaystyle \scriptstyle {\sqrt {n}}}$nが合成数である場合、少なくとも1つの因数≤${\displaystyle \scriptstyle {\sqrt {(}}n)}$より早期に検出されていたであろうすべての要因 >${\displaystyle \scriptstyle {\sqrt {(}}n)}$2つの積はnより大きいので、それは不可能です。

試行除算が成功した場合、その結果得られた商に対してそのプロセスが再帰的に適用されます。

素因数の上限を明確に定めることは可能です。P _{i を}i番目の素数とすると、P 1 = 2、P 2 = 3、P 3 = 5 などとなります。この_とき、 nの_因数としてテスト_する価値のある最後の素数はP _iで、 P ² _{i + 1} > nとなります。ここで等号が成り立つということは、 P _{i + 1}が因数であることを意味します。したがって、次の素数の平方が 49 であるため、n = 25 までだけでなく、n = 48 まで 2、3、5 でテストすれば十分であり、 n = 25 未満では 2 と 3 だけで十分です。nの平方根が整数であれば、それは因数であり、nは平方数です。    

擬似コードによる試行除算アルゴリズム：

アルゴリズム試行除法は、入力：因数分解する 整数n 、出力：nの素因数のリストF です。P ← すべての素数の集合≤${\displaystyle {\sqrt {n}}}$F ← 因子の空リスト Pの各素数pについて、 n mod pが 0 である間、以下を実行する。リストに 因数pを追加するF n ← n / pFが空の 場合（元のnは素数か？）、 因数nをリストFに追加する。

以下の素数を決定する${\displaystyle {\sqrt {n}}}$nが大きくなるにつれて、これは簡単な作業ではなくなるので、数を因数分解する最も単純なコンピュータプログラムは、2 から までの素数と合成数の連続する整数を試すだけです。${\displaystyle {\sqrt {n}}}$考えられる要因として。

最悪の場合、試行除算は面倒なアルゴリズムです。基数2のn桁の数aの場合、2から始めてaの平方根までしか計算しない場合、アルゴリズムは

${\displaystyle \pi (2^{n/2})\approx {2^{n/2} \over \left({\frac {n}{2}}\right)\ln 2}}$

裁判部門では、${\displaystyle \pi (x)}$は素数計数関数、つまりxより小さい素数の数を表します。これは、素数を候補因数として取得するための素数判定のオーバーヘッドを考慮していません。有用な表は大きくなくても構いません。P(3512) = 32749 は 16 ビット符号付き整数に収まる最後の素数であり、P(6542) = 65521 は符号なし 16 ビット整数に収まります。これで 65537 ² = 4,295,098,369 までの数の素数判定に十分です。このような表 (通常はエラトステネスの篩を使用) を作成するのは、多くの数をテストする必要がある場合にのみ価値があります。代わりに、素数判定を行わずに、2 進数n桁の数a (素数かそうでないか) の平方根より小さいすべての奇数で単純に割るバリアントを使用すると、約次の時間で済みます。

${\displaystyle 2^{n/2}}$

どちらの場合も、必要な時間は数値の桁数に応じて指数関数的に増加する。

それでも、最もよく知られているアルゴリズムでさえ時間の増加が指数関数的であることを考えると、これはかなり満足のいく方法です。与えられた長さの整数から一様にランダムに選択された a に対して、 2 がaの約数である確率は 50% 、3 がaの約数である確率は 33% などとなります。すべての正の整数の 88% は 100 未満の約数を持ち、92% は 1000 未満の約数を持つことが示されています。したがって、任意の大きなaに直面した場合、小さな素数による割り切れるかどうかをチェックする価値があります。なぜなら、${\displaystyle a=1000}$2進数で${\displaystyle n=10}$。

しかし、小さな素数に因数を持たない多桁の数を試行除法で因数分解するには、数日から数か月かかる場合があります。このような場合、二次篩法や一般数体篩法（GNFS）などの他の方法が用いられます。これらの方法も超多項式時間の増加を伴うため、 n桁の実用的限界に非常に早く達してしまいます。このため、公開鍵暗号では、aの値は、スーパーコンピュータやコンピュータグリッドなどの利用可能なコンピュータシステムやコンピュータクラスタで、既知の方法で実用的な時間内に因数分解できないように、同様の大きさの大きな素因数を持つように選択されます。因数分解された最大の暗号グレードの数は、 GNFSと複数のスーパーコンピュータのリソースを使用して因数分解された250桁の数であるRSA-250です。実行時間は2700コア年でした。

• チャイルズ、リンジー・N. (2009).高等代数学への具体的な入門.数学学部教科書（第3 版）. ニューヨーク、NY:シュプリンガー・フェルラーク. ISBN 978-0-387-74527-5. Zbl 1165.00002 . 
• クランドール、リチャード；ポメランス、カール（2005）。素数。計算機的視点（第2 版）。ニューヨーク、NY：シュプリンガー・フェルラーク。ISBN 0-387-25282-7. Zbl 1088.11001 . 

• Wikiversityでは、Pythonを使った試行除法による素因数分解のレッスンを提供しています。
• 試行除算を用いた高速JavaScript素因数分解計算機。約²⁵³までの数値を処理可能。
• Java、C、JavaScriptを用いた試験部門（ポルトガル語）