소인수분해
정의
자연수 $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$ 이 반환된다.
줄리아
다음은 조금 더 효율적으로 구현된 줄리아 코드다.
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