Prime95

Prime95는 메르센 소수를 찾는 프로그램으로, GIMPS에서 제공하고 있다. 이 프로그램은 사용 컴퓨터의 CPU를 풀가동 상태로 오랜 시간 돌리는데, 메르센 소수 찾기 외에도 오버클럭 테스트 용도로 유용하게 쓰이고 있다.

오버클럭 관련 내용은 나무위키:Prime95 문서를 참고. 여기서는 메르센 소수 프로젝트와 관련된 내용을 서술한다.

이곳(64비트 윈도우용)에서는 현재 빌드 중인 베타 버전과 공식 버전이 올라와 있다. 다른 운영체제 공식 버전은 여기에서 찾아볼 수 있다.

최신 공식 버전은 v30.8 빌드 17이다.

기능

자세한 내용은 Mathematics and Research Strategy 링크 참고.

Prime95에는 메르센 수의 소수 여부 판정과 소인수분해를 중심으로 기능이 구성되어 있다. 상단 메뉴의 "Test → Worker Windows" 창에 들어가면 어떤 계산 기능을 수행할 건지 고를 수 있다. "Type of work to get" 줄에 나열된 목록은 아래와 같다.

소수 찾기

현재 탐색 중인 메르센 수의 범위 현황은 GIMPS Milestones Report에서 확인할 수 있다. 아래 메뉴를 고르면 해당 범위 부근의 메르센 수를 불러와서 테스트를 진행한다.

• First time prime tests: 소수 찾기 프로젝트의 메인 기능이다. 아직 탐색하지 않은 메르센 수의 소수 여부를 테스트하는데, 페르마의 소정리의 합동식 만족 여부를 알아본다.
  • [math]\displaystyle{ M_p=2^p-1 }[/math]이 소수이면 [math]\displaystyle{ 3^{2^p} \equiv 9 \pmod{M_p} }[/math]이다. 이 합동식을 만족하면 소수 후보가 되고, 그렇지 않으면 탈락한다.
  • 이 과제는 현재 [math]\displaystyle{ p\gt 10^8 }[/math] 범위의 매우 큰 메르센 수를 대상으로 진행 중이다. 소요 시간은 최소 30일 이상
• Double-check prime tests: 이미 초검을 마친 메르센 수에 대해 재검을 시행한다. 이쪽은 뤼카-레머 소수판정법을 이용한다.
  • 이 과제는 현재 [math]\displaystyle{ p \gt 6 \times 10^7 }[/math] 범위로 상대적으로 작은 메르센 수를 대상으로 진행 중이다. 소요 시간은 11일 이상
• World record sized numbers to prime test: 지금껏 테스트를 한 것보다 큰 메르센 수를 대상으로 쓴다. 앞서 언급한 두 기능보다 훨씬 큰 수를 테스트하므로 소요 시간이 1년을 넘어간다. (권장하지 않는 기능)
• 100,000,000 digit numbers to prime test: 말 그대로 십진법으로 1억 자리 이상의 메르센 소수를 찾는다. 즉 [math]\displaystyle{ p\gt 3.16\times10^8 }[/math] 범위에서 소수판정을 시행하는데, 마찬가지로 시간이 굉장히 오래 걸리므로 권장하지 않는다. 다만 이 기능이 따로 마련된건 1억 자리 이상의 소수를 최초로 발견하면 상금 5만 달러가 주어지기에 관심 있는 사람더러 쓰라는 것이다. 물론 성공 확률은 극도로 희박하다.

기본적으로 소수 찾기 과제의 소요시간은 메르센 수의 지수의 제곱에 비례하여 증가한다. 이는 곱셈(제곱) 연산 횟수와 1회당 소요시간이 지수(즉 비트 수)에 비례하기 때문이다. 또, 소요시간이 한국인이 싫어할 정도로 매우 길기에, 이 프로그램은 악착같이 최적화된 곱셈 연산 알고리즘을 탑재하고 있다. 곱셈 시 고속 푸리에 변환을 이용하는데, 관련 내용은 쇤하게-슈트라센 곱셈법에서 살펴볼 수 있다.

참고로 GIMPS는 원래 초검과 재검 모두 뤼카-레머 소수판정법을 이용하였다. 하지만 2020년 9월 Prime95 v30.3부터는 페르마의 소정리로 초검을 하는 것으로 변경하였고, 2021년 4월부터는 뤼카-레머 초검 과제를 종료했다. 기존의 뤼카-레머 방식은 v30.3 이전 프로그램으로 이미 초검을 마친 메르센 수에 대해 재검 용도로만 쓰이고 있다.

여인수의 소수 여부

위 문단은 소인수를 전혀 모르는 메르센 수가 소수인지 여부를 확인하는 기능이다. GIMPS에서는 부가 프로젝트로 소인수분해 및 여인수의 소수 판정도 진행하고 있다.

여인수(cofactor)란 어떤 메르센 수의 비자명한 약수가 알려져 있을 때, 이들 약수로 나눈 몫을 말한다. 가령 [math]\displaystyle{ M_{37} }[/math]의 약수 223을 알고 있다 하면, 약수로 나눈 몫인 616318177이 여인수이다.

이쪽은 이미 합성수라는 사실이 판명나 있기에 소수 찾기와는 하등 상관이 없지만, GIMPS에서는 어떤 메르센 수의 약수들을 발굴하는 목표도 있으며, 소인수분해와 관련이 있다.

어떤 메르센 수[math]\displaystyle{ M_p }[/math]에 대해 소인수[math]\displaystyle{ q_1, q_2, \cdots q_k }[/math]가 알려져 있을 때, [math]\displaystyle{ \frac{M_p}{q_1 q_2 \cdots q_k} }[/math]가 소수인지 여부를 확인한다. 이때 위 문단에서와 마찬가지로 페르마의 소정리를 기준으로 테스트한다. 여기서 여인수가 소수이면 해당 메르센 수는 소인수분해가 완료되었음을 알게 된다. 그렇지 않으면 여인수 내에 또다른 비자명한 약수가 숨어있다는 뜻이므로, 완료 선언 없이 보류한다.

물론 페르마의 소정리는 테스트할 수가 소수이기 위한 필요조건이지 충분조건은 아니다. 단지 이 테스트를 통과하면 "높은 확률로 소수"라는 정보를 얻을 뿐이다. 위에서 살핀 여인수가 소수라는 사실을 증명하려면 타원곡선 소수판정법과 같은 방법이 따로 필요하다.

• First time PRP on Mersenne cofactors: 소인수들을 발견한 메르센 수의 여인수가 소수인지 여부를 확인한다. 여기서 PRP란 유력 소수를 의미한다. 작동 방식은 위 문단의 First time prime tests와 동일하지만 이쪽은 보통 [math]\displaystyle{ p\lt 2\times 10^7 }[/math] 범위에서 많이 시행하기에 소요시간은 24시간을 넘지 않는다.
• Double-check PRP on Mersenne cofactors: 바로 위 기능과 똑같지만 현재 잘 사용하지 않는다. v30.3부터는 재검 없이 초검으로 끝낼 수 있기 때문이다. (권장하지 않는 기능)

소인수분해

메르센 수가 소수이기 위한 필요조건은 2의 지수가 소수라는 것이다. 따라서 지수가 소수인 메르센 수에 대해 소수 여부를 전수조사하는데, 위 소수 찾기 문단의 방법으로 모두 검사하기에는 막대한 연산량이 요구된다. 사실 어떤 메르센 수의 비자명한 약수를 알고 있다면 그 수는 합성수라는 뜻이므로, 별도의 소수판정법이 필요하지 않다. 아래는 연산량이 상대적으로 적은 소인수분해 방법들이다.

• Trial factoring: 직접 나누기 방법이다. 이 프로그램에 마련된 기능 중 RAM카드나 하드디스크 메모리를 가장 적게 사용한다. 조사 범위는 2의 거듭제곱 단위로 쪼갠다. 즉 [math]\displaystyle{ 2^n\lt q\lt 2^{n+1} }[/math] 범위에서 약수가 존재하는지 여부를 살핀다. 만약 약수를 하나라도 발견하면, 그 메르센 수는 소수 후보에서 탈락한다. 소요시간은 대략 [math]\displaystyle{ 2^n }[/math]의 크기에 비례하고 [math]\displaystyle{ M_p }[/math]의 지수, 즉 [math]\displaystyle{ p }[/math]에 반비례한다.
• Trial factoring to low limits: 마찬가지로 직접 나누기를 시행하지만 이쪽은 특정 상한선까지 모두 조사한다. [math]\displaystyle{ q\lt 2^N }[/math] 범위에서 소인수 유무를 확인하며, 이때 상한 지수 [math]\displaystyle{ N }[/math]의 값은 [math]\displaystyle{ p }[/math]의 값에 달려 있다.
• P-1 factoring: 폴라드 p-1 소인수분해법을 이용한다. 이 기능을 고르면 [math]\displaystyle{ p\gt 1.1\times10^8 }[/math] 영역의 메르센 수를 대상으로 계산에 들어간다. 이 과정은 위의 직접 나누기 방법에서 소인수를 찾지 못할 때 실행한다. 폴라드의 방법에서 필요한 설정값은 [math]\displaystyle{ B_1, B_2 }[/math]인데, 사용자의 컴퓨터가 제공하는 메모리에 따라 프로그램이 결정한다. 구체적인 계산 방법은 폴라드 p-1 소인수분해법 문서의 '두 단계 분할' 문단 참고. 이 단계에서 소인수를 발견하면, 이 메르센 수는 소수 후보에서 탈락한다.
• ECM for first factors of Mersenne numbers: 비자명한 약수를 모르는 메르센 수를 렌스트라 타원곡선 소인수분해법(ECM)으로 약수 찾기를 시도한다. 이 알고리즘은 앞서 언급한 p-1 소인수분해법보다 계산 방식이 복잡하며, 소수 후보 거르기 용도로 쓰지는 않는다. 본 프로그램에서는 [math]\displaystyle{ p\lt 5 \times 10^6 }[/math] 범위를 대상으로 쓴다. 이 기능을 고르면 과제 하나당 2시간도 채 걸리지 않는다.
• ECM on Mersenne cofactors: 이쪽은 약수를 알고 있는 메르센 수에 대해 다른 약수를 찾는 용도로 쓰인다.
• ECM on Fermat numbers: 번외 기능. 메르센 수 대신 페르마 수의 소인수를 찾는다.

사용 방법

아래 설명은 프로그램에 첨부되어 있는 "readme.txt" 파일도 참고.

이 프로그램을 처음 실행할 때, 소수 찾기 프로젝트에 참여할 지를 묻는 대화상자가 뜬다. 오버클럭 테스트 목적이라면 "Torture test" 버튼을 누르고, 본 프로젝트에 참여한다면 다른 버튼을 누른다.

사용자가 PrimeNet에 계정을 신설하고 싶다면, Getting Started on GIMPS에서 "Create a new user account" 버튼을 누르고 아이디 및 닉네임을 만들면 된다. 이때 타 사용자에게는 닉네임만 출력되고 아이디는 본인만 알 수 있다.

다음 화면에서 계정 로그인을 묻는 대화상자가 나온다. 이는 "Test → PrimeNet" 메뉴의 대화창이다. 앞서 등록한 계정으로 첫째 칸에 아이디를 입력하면 해당 계정이 서버와 연동이 되고, 그렇지 않으면 서버에는 '-Anonymous-' 표시로 기록이 된다. 둘째 칸은 사용자의 컴퓨터(CPU)의 이름을 붙이는 것이다. 필수는 아니며, 사용자가 여러 컴퓨터를 동원할 때 기기 구분을 위한 용도라 보면 된다. 이때 맨 윗줄의 "Use PrimeNet to get work and report results" 표시는 체크하는 것이 좋다.

다음으로 "Worker Windows" 대화창이 뜰 것이다. 이때 설정은 앞서 소개한 기능 고르기 말고는 특별히 건드릴 필요는 없다. 만약 초검이나 재검 구분 없이 소수 찾기에 직접 참여하고싶다면, 디폴트인 Whatever makes the most sense를 두면 된다. 디폴트 관련 내용은 아래 '과제 제공 규칙' 문단 참고.

ECM, P-1 소인수분해

이들 소인수분해법은 크게 두 단계로 나눠서 알고리즘을 실행한다. 그 중 2단계 부분에서 신경쓸 부분이 있다. ECM, P-1 기능을 쓰고 있을 경우, "Options → Resource Limits"에서 둘째 칸인 "Memory resources"의 설정값을 확인해야 한다.

설정값은 2단계 시행 시 낮과 밤 시간에 RAM카드에 메모리를 Prime95에게 얼마까지 할당할 건지를 뜻한다. 특별히 낮밤을 구분하지 않는다면, 두 칸에 각각 1(GB) 이상의 동일한 실수 값을 입력하면 된다. 만약 할당량이 1GB에 못 미치면, 프로그램은 2단계를 건너뛰어서 계산 효율이 본래 목표보다 떨어지므로 주의를 요한다.

당연하지만 RAM카드가 컴퓨터에 몇 GB 장착되어 있는지에 따라 할당 가능 선도 달라진다. 메모리 할당량이 많을수록 계산 효율도 올라간다.

• ECM: 1GB 이상 할당하되, 컴퓨터 내 다른 프로그램이 방해 받지 않을 정도로만 제공한다.
• P-1: 컴퓨터가 감당할 수 있는 선에서 가급적 많이 할당할 것. ECM과는 달리 P-1은 사용 메모리가 많아짐에 따라 계산 효율이 급격히 향상되도록 프로그램이 설계되어 있다.
• 가령 컴퓨터에 8GB 장착되어 있고 프로그램에다 6GB를 할당하면, 2단계 시행 시 타 프로그램이 버벅거린다. 따라서 P-1을 사용 중일 때에는 프로그램을 틀어놓은 채 컴퓨터에서 손을 떼고 다른 일을 하는 것이 좋다.

참고로 v30.7까지는 P-1도 ECM처럼 백그라운드 프로세스에 방해되지 않을 만큼만 할당하라고 안내하였지만, v30.8부터는 P-1 알고리즘이 크게 개선되어서 할당량을 공격적으로 올릴 것을 권장하고 있다.

과제 등록 및 제출 방법

위에서 "Use PrimeNet to get work and report results" 표시를 해두었다면 서버에서 자동으로 과제를 제공할 것이다. 그리고 사용자는 이 프로그램을 틀어놓은 채 컴퓨터로 다른 일을 하거나, 컴퓨터에서 손을 떼고 기다리기만 하면 된다.

어떤 과제가 완료에 임박하면, 서버는 다음 과제를 미리 제공한다. 이는 서버 연결이 잠깐 끊기더라도 프로그램이 연속해서 다음 과제를 시행할 수 있도록 하기 위함이다. 어떤 과제를 받고 실행할 건지는 "worktodo.txt"에서 확인할 수 있다.

만약 해당 과제를 완수하지 못할 것 같거나 하고 싶지 않다면, "Advanced → Unreserve Exponent"에 들어가서 취소할 과제의 지수를 입력한다. 그러면 이 값에 해당하는 과제가 목록에서 빠진다. 이때 과제 종류는 신경 쓰지 않는다.

프로젝트에서 빠지기

"Advanced → Quit GIMPS"에 들어가서 예 또는 아니오 버튼을 누른다.

• "예"를 누르면 더이상 서버로부터 과제를 받지 않으며, 이미 제공 받은 과제들을 마저 마무리하고 나면 프로그램은 작동을 멈춘다.
• "아니오"를 누르면 현재 진행 중이거나 앞으로 할 과제들을 즉시 전부 취소하고 프로그램이 멈춘다.

만약 취소를 신고하지 않고 프로그램 사용을 중단하면, 서버는 사용자가 프로젝트를 그만둔다는 사실을 알지 못한다. 특히 소수 찾기 기능을 사용 중이었다면 서버 및 타 사용자들에게 민폐가 될 수 있으므로, 반드시 이 메뉴를 거치도록 한다.

과제 제공 규칙

관련 내용은 PrimeNet Assignment Rules에 설명되어 있다.

"Worker Windows" 창에서 디폴트 기능을 고를 때, 컴퓨터 사양에 따라 제공 방식이 달라진다. 상술했듯이 소수 찾기 과정은 수백 시간이 걸리기 때문이다.

• 해당 컴퓨터가 좀 느리다고 판단될 때에는 ECM을 먼저 제공한다. ECM은 Prime95에서 시행하는 과제들 중 소요 시간이 가장 짧다. 물론 이것도 과제 하나당 1시간 정도로 절대적으로는 길다. 이는 사용자가 프로그램을 틀어서 긴 시간을 충분히 감당할 수 있는지를 확인하기 위함이다. 만약 일정 기간 내에 하루 컴퓨터 실행 시간이 충분하다고 판단되면, 그때부터 소수 찾기 재검 과제를 제공한다.
• 상대적으로 빠른 컴퓨터에서는 처음에는 소수 찾기 재검을 제공하고, 위와 마찬가지로 프로그램 실행 시간이 충분하다고 판단되면 초검 과제를 준다.

같이 보기

• GIMPS
• 메르센 소수