PHP와 GMP를 사용하여 큰 정수에 대한 Lucas-Lehmer 소수 테스트를 수행하는 방법

PHP와 GMP를 사용하여 큰 정수의 루카스-레머 소수성 테스트를 수행하는 방법

소개:
수론에서 루카스-레머 소수성 테스트는 메르네센 수(Mersenne number)가 소수인지 테스트하는 데 사용되는 방법입니다. 큰 정수의 판단에 적용되어 널리 사용됩니다. 이 기사에서는 PHP 언어와 GMP 확장(GNU 다중 정밀도 산술 라이브러리, GNU 다중 정밀도 수학 라이브러리)을 사용하여 Lucas-Lehmer 소수성 테스트를 구현하고 해당 코드 예제를 제공합니다.

루카스-레머 성적 테스트란 무엇인가요?
루카스-레머 소수성 테스트는 M = 2^n − 1 형식의 무니센 수가 소수인지 여부를 결정하는 데 사용되는 효율적인 알고리즘입니다. 그 중 n은 1보다 큰 양의 정수이다. 이 테스트 방법은 Lucas-Lehmer 수열의 특성을 기반으로 수열의 다음 요소를 반복적으로 계산하고 최종적으로 수열의 마지막 요소가 0인지 판단하여 모네센 수의 소수성을 결정합니다.

PHP 및 GMP를 사용하여 Lucas-Lehmer 소수성 테스트를 수행하는 단계:
1단계: GMP 확장 설치
큰 정수 연산을 수행할 때 PHP의 내장 함수는 더 큰 값을 처리할 수 없습니다. 따라서 이 문제를 해결하려면 GMP 확장을 사용해야 합니다. PHP를 설치할 때 GMP 확장이 활성화된 버전을 설치하거나 기존 PHP 환경에서 GMP 확장을 활성화하도록 선택할 수 있습니다.

2단계: Lucas-Lehmer 소수성 검정 함수 작성
다음은 Lucas-Lehmer 소수성 검정을 수행하는 데 사용되는 함수의 예입니다.

function 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') {
        return true;
    }
    
    return false;
}

분석:

• $n: Mernessen 수의 지수 부분 .
• $s: Lucas-Lehmer 수열의 초기 값.
• $m: 모네센 번호.

함수에서는 gmp_pow 함수를 사용하여 2의 $n$ 거듭제곱을 계산한 다음 1을 빼서 $m$를 얻습니다. 그런 다음 $n-1$ 루프 반복을 수행하여 Lucas-Lehmer 수열의 각 요소를 계산합니다. 마지막으로 시퀀스의 마지막 요소가 0인지 확인하여 모네센 수의 소수를 결정합니다.

3단계: 테스트를 위해 Lucas-Lehmer 소수성 테스트 함수 호출
다음은 Lucas-Lehmer 소수성 테스트 함수를 호출하는 예입니다.

$exponents = [2, 3, 5, 7, 13, 17];
foreach ($exponents as $exponent) {
    $result = lucasLehmerTest($exponent);
    
    if ($result) {
        echo "2^$exponent - 1 is a prime number.
";
    } else {
        echo "2^$exponent - 1 is not a prime number.
";
    }
}

분석:
우리는 몇 가지 지수 값을 포함하는 $exComponents 배열을 정의합니다. 그런 다음 foreach 루프를 사용하여 Lucas-Lehmer 소수성 테스트 함수를 순서대로 호출하고 테스트 결과에 따라 해당 판단 정보를 출력합니다.

요약:
PHP 및 GMP 확장을 사용하면 Lucas-Lehmer 소수 테스트를 쉽게 구현하고 큰 정수가 소수인지 확인할 수 있습니다. 대규모 소수성 테스트의 경우 Lucas-Lehmer 알고리즘은 매우 효율적이며 Mönisen 수의 소수성을 빠르게 결정할 수 있습니다. 이 기사에서는 독자가 실제로 큰 정수 소수성 테스트를 수행하는 데 도움이 되기를 바라며 해당 코드 예제를 제공합니다.

참조:

• "Lucas–Lehmer 소수성 테스트." Wikipedia, 무료 백과사전 URL: https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
• "GMP 매뉴얼." URL: https://www.php.net/manual/en/book.gmp.php

위는 PHP와 GMP를 사용하여 큰 정수에 대한 Lucas-Lehmer 소수성 테스트를 수행하는 방법에 대한 기사입니다. 해당 코드 예제로.

위 내용은 PHP와 GMP를 사용하여 큰 정수에 대한 Lucas-Lehmer 소수 테스트를 수행하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!