폴라드 로 소인수분해 계산기

x ← x² + c (mod n) 으로 의사난수열을 만들고, 두 값의 차와 n의 최대공약수를 봅니다. 같은 수열을 소인수 p로 나눈 나머지로 보면 값이 p가지뿐이라 훨씬 짧은 고리를 돌고, 생일 문제로 √p 걸음이면 겹치는 두 값이 나옵니다. 그 차가 p의 배수라 gcd로 잡힙니다.

수열이 그리는 모양 때문입니다. 값이 유한하니 언젠가 반드시 지났던 값으로 돌아오는데, 처음 몇 걸음은 꼬리처럼 뻗다가 그 뒤로는 고리를 돕니다. 그려 보면 그리스 문자 ρ와 같습니다.

시행나눗셈은 √n번, 폴라드 로는 n^(1/4)번쯤입니다. 19자리 수라면 30억 번 대 5만 번쯤으로 갈립니다. 이 계산기는 실제 반복 횟수와 √n을 함께 내어 그 차이를 보여 줍니다.

아닙니다. gcd가 n 자체로 나오면(수열이 mod n에서도 겹친 경우) 아무것도 얻지 못합니다. 그때는 상수 c를 바꿔 다시 돌립니다. 그리고 n이 소수면 영원히 못 찾으므로 로를 돌리기 전에 반드시 소수 판정을 해야 합니다.

이 범위에서는 확정입니다. 밀러–라빈의 밑을 {2,3,5,7,11,13,17,19,23,29,31,37}로 잡으면 3.3×10²⁴ 미만에서 틀릴 수 없다는 것이 알려져 있고, 이 계산기가 다루는 10¹⁹ 이하는 그 안에 듭니다. 카마이클 수처럼 페르마 검정을 속이는 수도 정확히 걸러냅니다.

없습니다. n^(1/4)이라 20자리쯤까지가 실용적인 한계입니다. RSA-2048은 617자리라 이 방법으로는 우주의 나이보다 오래 걸립니다. 그런 크기는 수체 체(GNFS)를 쓰는데 그것도 아직 2048비트를 깨지 못했습니다.

두 가지로 확인합니다. 찾은 인수를 모두 곱해 원래 수가 되는지 보고, 각 인수가 밀러–라빈으로 정말 소수인지 봅니다. 작은 수에서는 시행나눗셈 결과와도 대조했습니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어집니다. 이 도구는 큰 수를 다루므로 입력값을 이 기기에도 저장하지 않습니다.