フェルマー数 $F_{10} = 2^{2^{10}} + 1$ が素数でないことを示すには、$p - 1$ 法と試し割り法ではどちらが早いか。

• $p - 1$ 法

n = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217
非自明な約数: 6487031809
実行時間: 0.015044 秒

• 試し割り法

n = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217
最も小さな素因数: 45592577
実行時間: 4.262128 秒

圧倒的に $p - 1$ 法が早い。これはどういうことなのだろう。

$p - 1$ 法とは

適当な $a,\ k \in \mathbb{N}$ を与えて

$$\gcd(a^k - 1,\ n)$$

を計算する。

$$1 \lt \gcd(a^k - 1,\ n) \lt n$$

のとき、$n$ の非自明な約数を得る。

計算例

$n = F_{10}$ に対して次のように $a,\ k$ をとると

$$a = 3, \\ k = \textrm{lcm}(1,\ 2,\ \cdots,\ 4100)$$

$\gcd(a^k - 1,\ n) = 6487031809$ となった。ここで $6487031809$ は素数であり、

$$6487031809 - 1 = 2^{14} \times 3^2 \times 29 \times 37 \times 41$$

と素因数分解される。

疑問

なぜ $a,\ k$ を適当にとって $\gcd(a^k - 1,\ n) = 6487031809$ のように素因数が現れるのだろうか。

考察

速度比較のとき、最初から $a,\ k$ を与えてしまっていた。$a,\ k$ は探索しなければならないパラメータである。そこで $a,\ k$ をパラメータ化して計測した結果:

| a = 3 | b = 4100 | d = 6487031809 成功
実行時間: 3.109131 秒

a は小さい範囲 $2 \le a \le 10$ を動き、$b$ は $p - 1$ が $5000$ までの素因数を含むことを許容した。

def find_factor():
    isSuccess = False

    for a in range(2, 10):
        for b in range(10, 5000, 10):
            d = p_minus_1(n, a, b)
            # 判定
            if 1 < d < n:
                print(f'| a = {a} | b = {b} | d = {d} 成功')
                isSuccess = True
                break
            elif d == 1:
                # b を大きくする必要あり
                print(f'| a = {a} | b = {b} | d = 1 失敗')
            elif d == n:
                # これ以上 b を大きくしても無駄なので a をインクリメントする必要あり
                print(f'| a = {a} | b = {b} | d = n 失敗')
                break
        else:
            continue
        if isSuccess:
            break

試し割り法より早かった。

いろいろな整数で速度比較

比較的小さな数

$8226679 = 127 \times 211 \times 307$

• $p - 1$ 法

n = 8226679
| a = 2 | b = 10 | d = 26797 成功
実行時間: 0.000306 秒

※ $26797$ は合成数。

• 試し割り法

n = 8226679
最も小さな素因数: 127
実行時間: 0.000010 秒

比較的大きな数

$99230305792491364911811 = 814432939613 \times 121839750047$

両者ともに 10 秒以内に終わらない。