試し割り法とは - わかりやすく解説 Weblio辞書

索引トップ用語の索引ランキングカテゴリー

試し割り法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/08/07 01:28 UTC 版)

試し割り法(ためしわりほう、英: trial division)は最も面倒ではあるが、最も理解しやすい素数判定（素因数分解）アルゴリズムである。基本的な考え方は、素因数分解しようとする整数nを小さい順に割ってみて、割り切れるかどうかを調べる手法である。例えば、12という整数は、1, 2, 3, 4, 6, 12で割り切ることが可能である。

方法

与えられた整数 n (n はこれから素因数分解する整数）に対して、nより小さい数で割り切れるかどうかを順番に確かめることで素数判定を行う。nが2で割り切れる確率は、nが3で割り切れる確率より高いため、小さい数から順に素因数の候補として割り切れるかを確かめると効率的である。また、nが2で割り切れない場合には4で割り切れないことは明らかであるため、4で割り切れるかを確かめる必要はない。同様に、既に確かめた数の倍数について確かめる必要はないため、素因数候補として確かめる数を素数のみとすることで、労力を削減できる。また、nが何らかの数pで割り切れる場合、n=pqであり、qがpより小さい場合には既にqもしくはqの約数で確かめた際に素因数が検出されているはずである。したがって、素因数候補として確かめるべきは ${\sqrt {n}}$ までで十分ある。

試すべき素因数の個数の上限は簡単に求められる。P_i をi番目の素数とすると、P₁ =2, P₂ =3, P₃ =5……となる。次に、最も運が悪い場合でも、P_i+1²>nを満たすP_iまで確かめれば良い。また、P_iまで試すことでP_i+1²未満のnまでの判定が可能である。したがって、2と3と5で確かめればn=48（25ではない）の判定が終了する。そして、次の素数7の平方である49からは7で確かめる必要があり（実際49は7×7である）、25未満までであれば2と3のみを確かめれば十分である。nの平方根が整数であればそれは約数であり、nは平方数である。

以下に、篩法を用いて素数を生成する試し割り法のPythonコードを示す。

def trial_division(n):
    """Return a list of the prime factors for a natural number."""
    if n < 2:
        return []
    prime_factors = []
    for p in prime_sieve(int(n**0.5)):
        if p*p > n: break
        while n % p == 0:
            prime_factors.append(p)
            n //= p
    if n > 1:
        prime_factors.append(n)
    return prime_factors

試し割り法はnが取りうる全ての素因数候補をチェックするため、確実にnの約数を見つけることができる。したがって、もし試し割り法でnの素因数が見つからなければ、nが素数であることの証明になる。逆に、もしnの約数を見つけた場合には、nは確実に合成数である。効率的に言えば、もしその平方がnを超えない素数のいずれかがnを割り切った場合、nは合成数であると判定できる。

計算速度

最悪計算量を考えると、試し割り法は非常に時間のかかるアルゴリズムである。2進法でのn桁の数aに対して、2から順にaの平方根まで試すアルゴリズムは

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

回の割り算を行う。

ここで、 $\pi (x)$ は素数計数関数であり、x未満の素数の数である。これは約数の候補として素数を取得する素数判定のオーバヘッドを説明しきるものではない。便利なテーブルはそこまで大きくなく、符号つき16ビット整数の範囲内の最大の素数であればP(3512)=32749、符号なし16ビット整数の範囲内での最大の素数であればP(6542)=65521である。

このテーブルを使うことによって、65537² =4,295,098,369までの素数判定が可能である。このようなテーブルはエラトステネスの篩でも用いられ、大規模な素数判定には有用であるが、その一方で単純に2とnの平方根以下の奇数のみで素数判定を行う手法も存在する。その場合には、n桁の数を判定するためにかかる計算はおよそ $2^{n/2}$ である。両者とも、計算時間は桁数に対して指数関数的に増加する。

このように試し割り法は非常に時間がかかるアルゴリズムではあるが、最も効率の良い手法でも計算時間が桁数に対して指数関数的に増加するため、十分満足できる手法である。与えられた範囲の整数に対して素数判定をする場合、2で割り切れる確率は50%であり、3で割り切れる確率は約33%であり、88%の自然数は100未満の約数を持つ、92%の自然数は1000未満の約数を持つ。したがって、大きな整数aの素数判定を行う場合小さな素数で割り切れるかを確かめることは有用である。

しかし、小さな素数を約数として持たない巨大な数の素数判定は数日もしくは数カ月もかかる場合がある。そのような場合には、二次ふるい法や一般数体ふるい法（GNFS）のような他の手法が用いられる。しかし、これらの方法の（時間）計算量も超多項式時間であるため、実用上の限界は比較的すぐにやってくる。この性質を利用して、解読に素因数分解が必要である公開鍵暗号方式で素数の積が用いられる。公開鍵暗号ではスーパーコンピュータやグリッド・コンピューティングを用いても既知の素因数分解アルゴリズムでは実用的な時間で素因数分解できない大きさの素数の積を用いている。今までに素因数分解された暗号の最大の桁数は RSA-768 の768ビットであり、数百台の計算機で一般数体ふるい法を用いて、およそ2年の計算の結果、素因数分解された。