今までの検証でわかったことをまとめる。

$p - 1$ 法とは

素因数分解のアルゴリズム。合成数 $n$ の素因数の 1 つを $p$ とするとき、$p - 1$ が小さな素数たちの積であるとき高速に $p$ を見つけることができる。

アルゴリズム

$n$ を合成数とする。正の整数 $a,\ k$ を選び、最大公約数

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

を計算する。$1 \lt d \lt n$ のとき、$n$ の非自明な約数を得ることができたため成功、$d = 1$ または $d = n$ のとき失敗である。

例

• $n = 15$

$a = 2,\ k = 1$ のとき

$$d = \gcd(2^1 - 1,\ 15) = 1$$

結果: 失敗

>>> from math import gcd
>>> gcd(2 ** 1 - 1, 15)
1

$a = 2,\ k = 2$ のとき

$$d = \gcd(2^2 - 1,\ 15) = 3$$

結果: 成功

>>> from math import gcd
>>> gcd(2 ** 2 - 1, 15)
3

$a = 2,\ k = 3$ のとき

$$d = \gcd(2^3 - 1,\ 15) = 1$$

結果: 失敗

>>> from math import gcd
>>> gcd(2 ** 3 - 1, 15)
1

$a = 2,\ k = 4$ のとき

$$d = \gcd(2^4 - 1,\ 15) = 15$$

結果: 失敗

>>> from math import gcd
>>> gcd(2 ** 4 - 1, 15)
15

$a$	$k$	$d$	結果
$2$	$1$	$1$	失敗
$2$	$2$	$3$	成功
$2$	$3$	$1$	失敗
$2$	$4$	$15$	失敗

解説

$p - 1$ 法で素因数を見つけることができる理由を解説する。そのために実際に素因数が見つかった場合に着目する。

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

とする。このとき $a^k\equiv 1\pmod{p}$ である。一方フェルマーの小定理により $p$ が整数 $a$ を割らなければ $a^{p - 1} \equiv 1\pmod{p}$ である。フェルマーの小定理の逆は成り立たないため、この合同式から $p - 1\mid k$ かどうかはわからない。しかし $k$ を大きくしていけば、そのうち $p - 1\mid k$ となる。

ただし $k$ が大きくなりすぎると、$n$ のほかの素因数 $q$ に対しても $q - 1\mid k$ となる場合がある。もし $n = pq$ の場合、$a^k \equiv 1\pmod{p}$ かつ $a^k \equiv 1\pmod{q}$ となり、$n = \gcd(a^k - 1,\ n)$ となってしまい失敗する。この場合、$k$ を大きくする速さを緩やかにするか、$a$ を取り換える。

$\gcd(a^k - 1,\ n) = 1$ となる場合、$p$ が $a^k - 1$ を割ることができるほど $k$ が大きくないため $k$ を大きくする必要がある。

:::note warn 注意 $a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^\times$ の位数が小さい場合、$p - 1\mid k$ でなくても $a^k \equiv 1\pmod{p}$ が成り立つため、必ずしも $p - 1\mid k$ が必要であるわけではない。例えば $49981 = 151 \times 331$ に対して $150$ は $15$ を割らないが $\gcd(2^{15} - 1,\ 49981) = 151$ となる。

>>> from math import gcd
>>> gcd(2 ** 15 - 1, 49981)
151

:::

$n$ との最大公約数を取ればよいため、$a^k - 1$ は常に $\textrm{mod}\ n$ で計算する。こうすることで繰り返し二乗法が使えるので高速になる。

$1\lt d\lt n$ となっても、$d$ が素数であるとは限らない。例えば、$n = 105$ とすると $\gcd(2^4,\ 105) =15$ となる。

>>> from math import gcd
>>> gcd(2 ** 4 - 1, 105)
15

参考

楕円曲線論入門