試し割り法のソースを表示

'''試し割り法'''(ためしわりほう、{{lang-en-short|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''の約数で確かめた際に素因数が検出されているはずである。したがって、素因数候補として確かめるべきは<math>\sqrt{n}</math>までで十分ある。

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

以下に、[[篩法]]を用いて素数を生成する試し割り法のPythonコードを示す。
<syntaxhighlight lang="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
</syntaxhighlight>試し割り法は''n''が取りうる全ての素因数候補をチェックするため、確実に''n''の約数を見つけることができる。したがって、もし試し割り法で''n''の素因数が見つからなければ、''n''が素数であることの証明になる。逆に、もし''n''の約数を見つけた場合には、''n''は確実に[[合成数]]である。効率的に言えば、もしその平方が''n''を超えない素数のいずれかが''n''を割り切った場合、''n''は合成数であると判定できる。

== 計算速度 ==
[[多項式時間|最悪計算量]]を考えると、試し割り法は非常に時間のかかるアルゴリズムである。2進法でのn桁の数aに対して、2から順にaの平方根まで試すアルゴリズムは
:<math>\pi(2^{n/2}) \approx {2^{n/2} \over \left(\frac{n}{2}\right)  \ln 2}  </math>
回の割り算を行う。

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

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

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

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

== 参考文献 ==
* {{Cite book|last=Childs|first=Lindsay N.|title=A concrete introduction to higher algebra|edition=3rd|series=[[Undergraduate Texts in Mathematics]]|year=2009|publisher=[[Springer-Verlag]]|ISBN=978-0-387-74527-5|location=New York, NY|zbl=1165.00002}}
* {{Cite book|last=Crandall|first=Richard|title=Prime numbers. A computational perspective|edition=2nd|year=2005|publisher=[[Springer-Verlag]]|ISBN=0-387-25282-7|author-link=Richard Crandall|location=New York, NY|last1=Crandall|last2=Pomerance|first1=Richard|first2=Carl|authorlink2=Carl Pomerance|author1-link=Richard Crandall|author2-link=Carl Pomerance|zbl=1088.11001}}

== 外部リンク ==
* [http://www.se16.info/js/factor.htm Javascript Prime Factor Calculator using trial division]. Can handle numbers up to about 9×10<sup>15</sup>

{{DEFAULTSORT:ためしわりほう}}
[[Category:数論アルゴリズム]]
[[Category:数学に関する記事]]