素因数分解
定義
自然数$N$に対して$N = p_{1}^{r_{1}} \cdots p_{n}^{r_{n}}$を満たす素数$p_{1} , \cdots , p_{n}$と自然数$r_{1} , \cdots , r_{n}$を見つけることを素因数分解という。
説明
歴史的に素数は常に探究の対象であったが、それにもかかわらず未だ分からないことが多い。
フェルマー判定法、コーセルト判定法、ミラー・ラビン判定法のような初等的な道具はもちろん、素数定理をはじめとする解析的アプローチは人間の知性の偉大な産物である。完璧ではなくとも、比較的効率的に素数を見つける方法には有意義な進歩があった。しかし、依然として素数の一般項を求める方法は知られていない。
多少の誇張を交えて言えば、人類は未だにエラトステネスの篩に留まっている。正確さにおいてエラトステネスの篩を本質的に凌駕する方法はなく、紹介されてから2000年が経った今でも、素数を見つける最も確実な方法として残っている。
一方、エラトステネスの篩が実は素因数分解を利用した方法であることに注目してみよう。$n = 120$以下で$2$の倍数をすべて消すということは、$2$で割り切れるかどうかの判定を$120$個の数に対して同時に行うということに他ならない。アニメーションで見るとこの方法は非常に効率的に見えるかもしれないが、$n$が大きくなるほど大変な作業になる。言ってしまえば、素数を判定する際に素因数分解を利用するというのは「力仕事」をするということである。直接計算してみて約数がなければ素数だと判定するのだが、これは我々が望む水準の数学と呼ぶにはあまりにも低劣である。
エラトステネスの篩が有用に見える理由は、素数を見つけるたびに「候補」を速いスピードで減らしてくれ、$n$まで判定する間にそれより小さい素数もついでに見つけてくれるからである。かける労力に比べれば成果物も豊富に見えるが、結局、素因数分解したい大きな自然数$n=N$一つに対しては正直に時間がかかるしかない。
コンピュータの発達により掛け算は非常に簡単なことになってしまったが、その凄まじい計算能力をもってしても素因数分解は難しい問題として残っている。しかし、このような素因数分解問題の特徴は同時に暗号の必須的な性質となり、離散対数問題の弱点を克服して我々の生活を豊かにしてくれた。
素因数分解を高速に行う方法としては、量子コンピュータを基盤としたショアのアルゴリズムShor algorithmがあるが、量子コンピュータの実用化は遠い先の話であるため、素因数分解問題の難しさを利用した暗号体系は当分の間現役に留まると見られる。
コード
R
次はエラトステネスの篩をRコードで実装したものである。自然数$n$が与えられると、エラトステネスの篩と同じ方法で素数かどうかを判別してくれる。$n$と同じ数が返されれば素数であり、$n$より小さい数が返されれば、それは$n$の約数の中で最も小さい数を意味する。
eratosthenes<-function(n){
residue<-2:n
while(n %in% residue){
p<-residue[1]
residue<-residue[as.logical(residue%%p)]
}
return(p)
}
eratosthenes(101)
eratosthenes(1517)
例として、$101$は素数なので$101$がそのまま返され、$1517=37 \times 41$なので$37$が返される。
Julia
次はもう少し効率的に実装されたJuliaコードである。
function factorize(n)
factors = []
while n > 1
for k in 2:n
if n % k == 0
n ÷= k
push!(factors, k)
end
end
end
return factors
end
function eratosthenes(n::Integer)
if n == 1 return [[1]] end
if n == 2 return [[1], [2]] end
primes = [2]
factorized = [[1], [2]]
for k ∈ 3:n
m = k
for p ∈ primes
if m % p == 0
m ÷= p
temp = [p; factorized[m]]
push!(factorized, temp)
break
end
end
if length(factorized) != k
push!(primes, k)
push!(factorized, [k])
end
end
return factorized, primes
end
F, P = eratosthenes(20)
F
P