정수 이론에서 Lucas-Lehmer 소수성 테스트는 메르센 수가 소수인지 여부를 결정하는 효율적인 방법입니다. 이 기사에서는 PHP 언어와 GMP 확장(GNU 다중 정밀도 산술 라이브러리, GNU 다중 정밀도 수학 라이브러리)을 결합하여 Lucas-Lehmer 소수성 테스트를 구현하고 완전한 코드 예제를 제공합니다.
Lucas-Lehmer 소수성 테스트는 M = 2^n - 1 형식의 메르센 수가 소수(여기서 n은 1보다 큰 양의 정수)인지 여부를 감지하기 위해 특별히 설계된 알고리즘입니다. 이 테스트는 Lucas-Lehmer 수열을 기반으로 합니다. 수열의 각 요소를 반복적으로 계산한 후 최종적으로 수열의 마지막 요소가 0인지 여부를 판단하여 메르센 수의 소수성을 결정합니다.
PHP의 내장 함수는 매우 큰 정수 연산을 처리할 수 없으므로 GMP 확장이 필요합니다. PHP를 설치할 때 GMP 확장이 활성화된 버전을 선택하거나 기존 환경에서 GMP 확장을 활성화할 수 있습니다.
함수 lucasLehmerTest($n) { $s = '4'; $m = gmp_pow('2', $n) - '1'; for ($i = 1; $i < $n - 1; $i++) { $s = gmp_mod(gmp_pow($s, 2) - 2, $m); } if ($s == '0') { 사실을 반환; } 거짓을 반환; }
분석:
함수에서 gmp_pow는 2의 $n$ 빼기 1제곱을 계산하여 $m$를 얻은 다음 $n-1$ 번 반복하여 Lucas-Lehmer 수열을 계산하고 마지막으로 수열의 마지막 요소가 0인지 확인하여 소수를 결정합니다.
$지수 = [2, 3, 5, 7, 13, 17]; foreach($지수를 $지수로) { $결과 = 루카스레머테스트($지수); 만약 ($결과) { echo "2^$지수 - 1은 소수입니다."; } 또 다른 { echo "2^$expont - 1은 소수가 아닙니다."; } }
분석:
여러 지수 값을 포함하는 $exComponents 배열을 정의한 다음 foreach 루프를 사용하여 Lucas-Lehmer 소수 테스트 함수를 호출하여 테스트 결과에 따른 판단 정보를 출력합니다.
PHP 및 GMP 확장을 통해 Lucas-Lehmer 소수 테스트를 쉽게 구현하고 큰 정수가 소수인지 여부를 확인할 수 있습니다. 큰 메르센 수의 소수 판단에는 Lucas-Lehmer 알고리즘이 더 효율적이고 결과를 빠르게 얻을 수 있습니다. 이 문서에 제공된 코드 예제는 실제 참조로 사용할 수 있습니다.