今日は仕事始め。まったくやる気が出なかった。はあ。能力は低いし心はボロボロだしもうだめだ。

フェルマー数

$p - 1$ 法がうまくいく素数なんてほんの少しなんじゃないか。 しかも探索するパラメータによって試し割り法より早い時も遅い時もある。

• フェルマー数の非自明な約数を見つけるまでの時間

素数	$p - 1$ 法(秒)	試し割り(秒)
$F_{10}$	3.083962	4.255898
$F_{11}$	5.491471	4.255898
$F_{12}$	10 秒以内に終わらない	0.037492

$F_{12}$ に対してお手上げだ。

しかし次のようにパラメータを変えてみたところ早くなった。

初期値の範囲: range(2, 10)
lcm の範囲と間隔: range(1, 2000000, 2000)

これは次のようなロジックを意味する:

# 初期値の範囲
for a in range(2, 10):
    # lcm の範囲
    for b in range(1, 2000000, 2000):
        # p - 1 法で gcd を計算
        d = p_minus_1(n, a, b)

lcm の範囲とは、次のように 3 つ以上の lcm を計算するために指定している:

# k = LCM(1, 2, ..., b) を計算
k = reduce(lcm, range(1, b + 1))

このパラメータで再計算していみる。

素数	$p - 1$ 法(秒)	試し割り(秒)
$F_{10}$	0.065141	4.255898
$F_{11}$	0.090319	4.255898
$F_{12}$	3.679174	0.037492

ものすごく早くなった。