선행지식

• 정수론의 기본 개념 이해
  • 최대공약수(GCD)와 모듈러 연산
  • 소수와 합성수의 개념
• 확률론적 알고리즘의 이해
  • 랜덤성과 결정론적 함수의 차이
• 그래프 이론의 기초
  • 순환(cycle) 개념
  • 플로이드의 순환 찾기 알고리즘
• 비둘기집 원리의 이해

기본 개념

폴라드-로 알고리즘은 존 폴라드가 1975년에 고안한 정수 인수분해 알고리즘이다. 순환고리 형태의 그래프가 로마자 문자 'ρ'와 비슷한 모양을 만들어내어 이러한 이름이 붙었다. 이는 합성수의 인수를 효율적으로 찾아내는 데 사용되는 확률적 알고리즘이다.

설명

폴라드 로 알고리즘은 2부터 N 사이의 랜덤한 수 x를 선택하여 N과의 공통 인수를 찾는 방법으로, $gcd(x,N) \not\equiv 1(mod\ N)$인 성질을 활용한다.

이 알고리즘이 효과적으로 작동하기 위해서는 두 가지 전제 조건이 필요하다:

1. N이 짝수가 아닐 것. N이 짝수라면 소인수 2가 존재하므로 알고리즘을 사용할 필요 없이 2를 반환하면 된다.
2. N이 소수가 아닐 것. N이 소수인 경우 모든 x에 대해 $gcd(x,N) \equiv 1(mod\ n)$이 성립한다.

따라서 밀러-라빈 알고리즘을 사용하여 N이 소수인 경우를 먼저 확인한다.

단순히 2부터 N 사이의 무작위 수를 선택하면 편향이 발생하거나 약수를 찾기 어려울 수 있다.

이러한 문제를 해결하기 위해 $f(x) = x^2 + c\ mod\ N$를 사용하여 x값을 결정한다.

<aside> 💡

왜 $f(x) = x^2 + c\ mod\ N$를 사용하는가?

1. 꼭 $f(x) = x^2 + c\ mod\ N$만 사용해야 하는 것은 아니다. $f(x) = x^2 + x + c\ mod\ N$도 가능하다. 하지만 $f(x) = x^2 + c\ mod\ N$를 선호하는 이유는 다음과 같다:
   1. 계산이 가장 단순함
   2. 제곱 연산과 상수항 c로 인해 결정론적 함수이면서도 충분한 랜덤 효과를 낼 수 있음
2. 왜 1차함수는 안되는가?
   1. 주기가 너무 규칙적이게 됨
   2. 랜덤성이 약해짐
3. 그냥 랜덤을 사용하면 안되는가?
   1. 이러한 f(x)를 사용하면 mod N의 값이 고르게 분포되며, 값은 무작위적이지만 일정한 규칙성을 가진다. 따라서 이미 확인한 경우를 다시 확인할 확률이 낮아진다. </aside>

<aside> 💡

추가적인 정보(1) 비둘기집 원리

만약 비둘기집이 23개 있고 비둘기가 24마리라면, 두 마리가 들어간 집이 반드시 존재할까?

답은 "반드시 존재한다"이다. 비둘기를 집당 한 마리씩 배정해도 한 마리가 남기 때문에, 그 비둘기는 어느 한 집에 들어갈 수밖에 없다.

이는 자명해 보이지만, 확률론에서 매우 중요한 원리이다.

</aside>

<aside> 💡

추가적인 정보(2) 모듈러 산술의 기본 성질

모듈러 산술에서는 다음과 같은 성질이 있음.

$$ if\ N|d \\ a \equiv b(mod\ N) \to a \equiv b(mod\ d) $$

</aside>

이제 $f(x) = x^2 + c\ mod\ N$가 훌륭한 유사 난수 수열 생성기임을 알 수 있다. 비둘기집 원리에 따라 N의 약수 d에 대해 $a_n$ mod d는 반드시 사이클을 가지게 된다. 쉽게 말해 f(x) mod N 안에 f(x) mod d의 사이클도 돌고 있는것이다.

따라서 $a_n\ mod\ d \to a_{n+1}\ mod\ d$로 향하는 화살표를 그리면 아래와 같은 그래프가 형성된다.