소인수분해

Prime Factorization · 素因數分解

합성수를 소수들의 곱으로 나타내는 것을 말한다.[1] 소수를 처음 배우는 중학교부터 자주는 아니더라도 계속 쓰이는 기본적인 수학 도구. 모든 합성수가 소인수분해된 형태를 가지고 있다는 것은 산술의 기본정리로 증명된다.

'소인수분해'라는 명칭은 중학교에 가서야 언급되지만, 초등학교 때에도 약수와 배수를 구하기 위해 잠시 사용된다.

factordb - 이름 그대로 소인수분해 방법이 알려진 수들의 데이터베이스를 제공한다. 모르는 수의 소인수분해 방법이 궁금할 때 참조하면 좋은 자료.

울프람알파에서도 prime factorization 과 함께 숫자를 넣어주면 소인수분해 결과를 보여준다. 간단히 'factor 숫자' 로도 된다.
11111111111111111의 소인수분해

이 문단에서는 1보다 큰 어떤 정수 $N$이 주어졌을 때, 약수를 찾는 여러 가지 기술에 대해 소개한다. 먼저 가장 쉬운 방법은 아래의 배수 판정법을 이용하는 것이다.

또는 아래 정리를 사용할 수도 있다.

증명은 아래와 같다.

이 정리에 의해 어떤 큰 수를 소인수분해 할 때, 그 수의 제곱근 보다 큰 수로 나눌 필요는 없다는 사실을 알 수 있다. 이는 노가다를 통해 소인수분해를 하는 시간을 크게 단축시켜 준다.

프로그래밍으로 소인수를 구할 때는 위와 같은 자질구레한 규칙을 따질 필요 없이, 주어진 숫자 n의 소인수를 구한다고 할 경우 아래와 같은 순서로 진행하면 된다.

어차피 작은 소수에서 n%i == 0이 성립하지 못한다면 그보다 큰 합성수는 n%i == 0가 성립하지 못하므로 n%i == 0이 성립하는 첫번째 i는 소수라는 점을 이용한 알고리즘이다.
이 알고리즘으로 소인수를 구하면 천억이 넘는 숫자도 소인수가 순식간에 구해진다.

간단하게 파이썬으로 코딩 해보면 다음과 같다.

# -*- coding: utf-8 -*-
import os
import sys

def find_prime(input_num):
    if input_num <= 2:
        return [input_num,]
    for idx in range(2,input_num):
        if input_num % idx == 0:
            ret_list = []
            val_a    = find_prime(idx)
            val_b    = find_prime(int(input_num/idx))
            ret_list = val_a + val_b
            return ret_list
    return [input_num,]

def main():
    try:
        input_num  = int(sys.argv[1])
    except:
        print("usage: python main.py <number>")
        print(" ex>   python main.py 12345")
        quit()
    prime_list = find_prime(input_num)
    check_num  = 1
    for prime_at in prime_list:
        check_num *= prime_at
    print("[%s] input_num=%d, check_num=%d" % (input_num == check_num, input_num, check_num))
    print("%s" % prime_list)

main()

다만 위의 프로그램은 프로그래밍을 익히는 용도로는 유용할수 있으나, 실제 소인수분해 용으로 쓰기에는 적합하지 않다. 실제로 컴퓨터로 다루는 수는 1000억은 '겨우'라는 소리가 나올만큼 큰 수를 다룰 필요가 있기 때문이다.

가장 쉬운 방법은 다른 프로그램을 이용해서 미리 소수 테이블을 작성해 두고, 이를 활용하는 것이다. 예를 들어 2¹⁶ 보다 작은 소수는 6542개인데, 이를 미리 배열에 저장해 두면, 42억 (=2³² ) 보다 작은 수는 겨우 6542번 나누어 보기만 하면 소수인지 판정하거나, 1개 이상의 소인수를 구할 수 있다. 2³² 보다 작은 소수는 모두 약 2억개(203,280,221 개) 인데, 이를 미리 구해서 적절한 DB 에 저장해 두면 약 1000경 (= 2⁶⁴ = 18,446,744,073,709,551,616) 보다 작은 수의 소인수 분해를 쉽게 할 수 있다.

20 자리 정도 되는 이정도 수면 큰 수라고 생각할 수 있지만, RSA 암호화같은 암호학에서 기본 수백자리 수를 다뤄야 한다. RSA 넘버를 보면 가장 작은 것이 100자리 부터 시작하는데, 그마저 250자리 수 까지는 모두 소인수분해되었다. 가장 큰 RSA-2048 은 무려 617자리 수이다. 수의 단위 중 이름이 붙은 최고 단위인 구골이 101자리 수라는 것을 생각해보면, RSA 암호화에서 다루는 수는 사람에게는 어마어마하게 큰 수이다.

밑과 지수를 구하는 기본적인 파이썬 함수는 https://futureengineer.tistory.com/49?category=1181513 에 설명되어있다.