Lehman 소인수분해법은 $O(\sqrt{n})$인 기존의 소인수분해 법에서 정수론적 기법을 섞어서 $O(\sqrt[3]{n})$에 소인수분해를 하는 기법입니다.
크게 다음의 과정으로 나뉩니다.
0. 우선 $21 < n$이어야 한다. ($21$ 이하라면 직접 그냥 나눠서 하기, 혹은 미리 전처리를 해놓기)
1. $n^{\frac{1}{3}}$보다 작은 소인수가 있는지 일일이 확인한다. 있다면 그 수를 return 하고 종료한다.
2 - 1. $1 \leq k \leq \lceil n^{\frac{1}{3}} \rceil$인 모든 정수 $k$에 대하여 2 - 2를 반복한다.
2 - 2. $$ \left\lceil 2 \sqrt{kn} \right\rceil \leq a \leq \left\lfloor 2 \sqrt{kn} + \frac{n^{\frac{1}{6}}}{4\sqrt{k}} \right\rfloor $$ 인 모든 정수 $a$에 대해, $\sqrt{a^2 - 4kn}$이 정수라면 $\gcd(a + b, n)$을 return 하고 종료한다.
3. $n$을 return 하고 종료한다. ($n$은 소수 라는 뜻)
먼저, 2 - 1 과정까지 끝나고 나면 소인수가 2개만 있거나, 소수이거나 둘 중 하나입니다.
한 가지 경우를 날려버리기 위해 소수인 경우는 미리 밀러-라빈 소수 판별법 으로 날려버렸다는 가정을 하겠습니다.
2 - 2번의 과정은 페리수열과 관련되어 있습니다.
보통 여기서 더 나아가서 폴라드-로 소인수분해, 연분수 소인수분해 등 다양한 시간복잡도 줄이기 방법이 동원됩니다.