[Algorithm] 소인수 분해(Prime/Integer Factorization)

소인수 분해(Prime/Integer Factorization)

개념

• 특정 자연수를 1보다 큰 자연수인 소인수(소수인 인수)들만의 곱으로 표현하는 것
• 합성수를 소수의 곱으로 나타내는 방법
• 소인수 분해를 일의적으로 결정하는 공식은 아직 발견되지 않았다.
• 현대 암호학에서 소인수 분해는 암호 처리를 하는데 중요하게 사용된다.
• 모든 합성수는 소인수 분해된 형태를 가지고 있다.
  • 산술의 기본 정리(Fundamental Theorem of Arithmetic)로 증명된다.

소인수 분해 하는 법

 

알고리즘

기본 알고리즘

• 소인수는 1이라는 값이 아닌 2부터 시작하는 것이 핵심이며, 2로 나누지 못할 경우 2에서 하나씩 증가시켜주면서 나누어지는지 체크하면 된다.

void factorize(int n) {
    int factor = 2;    // 시작 값

    while (factor <= n) {
        if (n % factor == 0) {
            cout << factor << '\n';
            n /= factor;
        }
        else {
            factor++;
        }
    }
}

 

사용 예

#include <iostream>
using namespace std;

void factorize(int n) {
    int factor = 2;    // 시작 값

    while (factor <= n) {
        if (n % factor == 0) {
            cout << factor << '\n';
            n /= factor;
        }
        else {
            factor++;
        }
    }
}

int main() {
    factorize(72);
}

2
2
2
3
3

 

고전적 알고리즘

고전적인 소인수 분해 알고리즘은 대부분 페르마 소정리(Fermat's Little Theorem)를 확장한 것을 이용한다.

그 중, 자주 사용되는 알고리즘은 아래와 같다.

• 윌리엄의 p+1 알고리즘
• 폴라드의 p-1 알고리즘
• 폴라드 로 알고리즘
• 페르마의 알고리즘

 

참고 사이트

• https://ko.wikipedia.org/wiki/%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4
• https://namu.wiki/w/%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4
• http://factordb.com/
• https://www.calculatorsoup.com/calculators/math/prime-factors.php
• https://www.wolframalpha.com/