この記事は FUJITSU Advent Calender 2021 の1日目の記事です。
本記事を含む一連の記事では, 合成数の素因数分解について紹介していきます.
- はじめに
- 準備
- 素朴な素因数分解法
3.1 試し割り法
3.2 Fermat法 - 一次合同式を用いた素因数分解法
- 二次合同式を用いた素因数分解法
3. 古典的な素因数分解法
本章から具体的な素因数分解方法を紹介していきます. 本章で紹介する試し割り法と Fermat 法は古典的な素因数分解法として有名で, いずれも処理が単純で実装しやすいという特徴を持ちます.家庭用の計算機でも 20 $\sim$ 30 桁程度の合成数の素因数分解が可能ですが, 残念ながらそれより大きな合成数の素因数分解には向いていません. しかしほとんどの合成数は小さい素因数を持つので1, 性質が不明な合成数を素因数分解する場合, まず試し割り法や Fermat 法によって小さい素因数を見つけ, 残りの部分に別の素因数分解法を適用するという手順をとります. このため,
試し割り法や Fermat 法を理解することは理論的にも実践的にも重要です.
3.1 試し割り法
最も素朴な素因数分解法は, 与えられた自然数が素数で割り切れるかを小さい順に確認していく (実際に割ってみる) 方法です. この素因数分解法を 試し割り法 (ためしわりほう, trial division method) と呼びます. 試し割り法は, 与えられた自然数が合成数の場合には素因数を発見し, 素数の場合には素数であることを判定します. 処理内容がとても単純で理解しやすく, 古くから素因数分解や素数判定に使用されてきました2.
家庭用の計算機を使用した場合, 試し割り法は 20 $\sim$ 30 桁程度の合成数を素因数分解することができますので, 多くの場合には十分な性能を持っています. しかし時間計算量は指数関数的に増大するため, これより大きな合成数の素因数分解には向いていません. 試し割り法は素因数分解だけでなく素数判定にも利用できますが, 素数判定が目的なら他に効率の良いアルゴリズムが知られており, (特に巨大な)自然数の素数判定にも向いていません.
3.1.1 処理の内容
素因数分解したい合成数 $n$ に対し, 試し割り法は $n$ 以下の素数を小さい順に生成してその素数で割りきれるか試し割りします. 割り切れる場合にはその素数を素因数として出力し, 割り切れなければ次の素数で試し割りします. この処理により, 与えられた合成数 $n$ の素因数は必ず出力されます. また $n$ が素数の場合には $n$ 自身が出力されます.
しかし, 素数を生成する処理は複雑であり, 特に大きな素数を生成するには処理時間がかかってしまいます. そこで処理を単純にするために 2 以上 $n$ 以下の自然数で試し割りします.
プログラム
上記の処理を Python で実装するとプログラム trial_division1 のようになります. 入力された自然数 $n$ が合成数のときは最小の素因数を, $n$ が素数のときは $n$ 自身を出力します. 2 行目で試し割りする自然数をあらわす変数 $a$ を 2 に設定した後, 3 行目で while 文の繰り返し条件 $a \le n$ を設定し, 4 行目で $n$ が $a$ で割り切れるかを試し割りし, 割り切れれば 5 行目で $a$ を出力して終了します. 割り切れなければ 6 行目で $a$ を 1 増加させ, 3 行目に戻ります.
なお, 自然数 $a$ は小さい順に検証しているので, プログラム trial_division1 が合成数を出力することはありません. 例えば合成数 $n$ が 15 で割り切れる場合,
15 で試し割りする前に(15の約数である) 3 で試し割りするので, 出力値は必ず素数となります.
def trial_division1(n):
a = 2
while a <= n:
if n%a == 0:
return a
a += 1
実験
プログラム trial_division1 の性能を評価するために, 何個かの合成数を実際に素因数分解してみましょう. ここでは プログラム trial_division1 に 4 $\sim$ 10 桁のいくつかの自然数 (小さな素因数を持つ合成数, 比較的大きな素因数を持つ合成数, 素数の 3 種類) を入力し, 結果が出力されるまでに要した時間を表にまとめました.
処理時間の単位は秒で, 0.001 秒未満の場合は 0.000 と表しています. なお処理時間は使用する計算機によって異なりますので, 処理時間の値そのものではなく, 他の処理時間との比率に注目して下さい. 自然数の名称に使用している C' は合成数, P' は素数, 数字は桁数をあらわします. これら名称の自然数は本資料の他の実験でも使用します.
実験結果からわかる通り, 合成数 $n$ が小さな素因数を持つ場合, プログラム trial_division1 はほとんど一瞬で結果を出力しています. しかし自然数 $n$ が素数の場合, P10 (10 桁) の処理に約 300 秒を要しており, 計算時間の長さ目立っています.
| 名称 | $n$ | 素因数分解 | 処理時間(秒) |
|---|---|---|---|
| C04a | $2787$ | $3 \times 929$ | 0.000 |
| C04b | $3869$ | $53 \times 73$ | 0.000 |
| P04 | $5261$ | $5261$ | 0.000 |
| C06a | $439979$ | $223 \times 1973$ | 0.000 |
| P06 | $537739$ | $537739$ | 0.065$ & 0.000 |
| C06b | $979669$ | $43 \times 22783$ | 0.000 |
| C08a | $29949323$ | $2531 \times 11833$ | 0.000 |
| P08 | $30859637$ | $30859637$ | 2.712 |
| C08b | $46183933$ | $137 \times 277 \times 1217$ | 0.000 |
| C10a | $2433460811$ | $293 \times 8305327$ | 0.000 |
| P10 | $1976233741$ | $1976233741$ | 298.5 |
| C10b | $2349758009$ | $29009 \times 31001$ | 0.004 |
計算量
プログラム trial_division1 の計算量を考えます. 入力された合成数 $n$ の一番小さい素因数を $p$ とすると, プログラム trial_division1 における while 文の繰り返し回数は $p-1$ 回なので, 時間計算量は ${\cal O}(p)$ となり, 素因数 $p$ の指数関数になっています. 最悪な場合, 素因数 $p$ は $n$ に等しくなる, つまり $p=n$ となるので, プログラム trial_division1 の最悪の時間計算量は ${\cal O}(n)$ となります. 他方でプログラム trial_division1 は記憶容量をほとんど使用しないので, 空間計算量は ${\cal O}(1)$ となります.
試し割り法を高速化するために, 以下では 2 種類の改良法を紹介します. 1 つ目は繰り返し回数を減らす改良で, 特に $n$ が素数の時に効果的です. もう 1 つは試し割りする自然数の個数を削減する改良で, 全ての場合に効果を発揮します.