특수 수체 체

특수 수체 체(Special Number Field Sieve, SNFS)는 특수한 꼴의 자연수를 매우 빠르게 소인수분해할 수 있는 알고리즘이다. 이 알고리즘은 re ± s 꼴의 수를 빠르게 소인수분해할 수 있으며, 보통 지수가 작은 메르센 수를 소인수분해할 때 많이 쓰이는 알고리즘이다. 또한 수체 체는 특수 수체 체의 변형된 방법으로, 모든 자연수 n을 빠르게 소인수분해할 수 있는 알고리즘이지만 특수 수체 체보다는 느리다. 이 알고리즘의 실행 시간은 이며, 보통 r과 s가 작은 수일 때 잘 작동한다.

소인수 분해 알고리즘