한국어
한국어
Lucas-Lehmer 1 차 테스트는 Mersenne의 수를 판단하는 데 일반적으로 사용되는 알고리즘이며 숫자 이론 및 암호화에 널리 사용됩니다. Mersenne 숫자는 양식 2 N -1의 정수이며, 여기서 N은 양의 정수입니다. 이 기사는 PHP 및 GMP 라이브러리를 사용 하여이 주요 테스트를 구현하여 Mersenne 번호가 소수인지 여부를 결정하는 방법을 보여줍니다.
먼저 PHP 환경에 GMP 라이브러리가 설치되어 있는지 확인하십시오. phpinfo () 명령을 사용하여 GMP 라이브러리가 설치되어 있는지 확인할 수 있습니다. 설치되지 않은 경우 PHP를 컴파일 할 때 GMP 옵션을 활성화하거나 Linux 시스템의 패키지 관리자를 통해 설치할 수 있습니다.
PHP에서는 GMP 라이브러리를 사용하여 대규모 작업을 수행 할 수 있습니다. 다음은 Lucas-Lehmer 원시 테스트를 구현하는 PHP 기능의 예입니다.
function lucasLehmerTest($n) {
$s = gmp_init(4);
$m = gmp_sub(gmp_pow(2, $n), 1);
for ($i = 0; $i < $n - 2; $i++) {
$s = gmp_mod(gmp_sub(gmp_mul($s, $s), 2), $m);
}
return gmp_cmp($s, 0) == 0;
}
이 함수는 Mersenne 번호의 지수를 나타내는 매개 변수 n을 허용합니다. 함수는 Lucas-Lehmer 시퀀스에서 각 항목을 계산하고 마지막 항목이 0인지 확인합니다. True가 반환되면 Mersenne 번호가 소수임을 의미합니다. False가 반환되면 Mersenne 번호가 소수가 아님을 의미합니다.
다음으로, 위의 함수는 Mersenne 번호의 속성 테스트를 수행하는 데 사용될 수 있습니다. 다음은 Mersenne 번호가 소수인지 여부를 감지하는 예입니다.
$n = 29; // 적절한 색인을 선택하십시오，여기29예로
$isPrime = lucasLehmerTest($n);
if ($isPrime) {
echo "2^{$n} - 1 소수입니다";
} else {
echo "2^{$n} - 1 不소수입니다";
}
이 예에서는 테스트를 위해 29 인덱스를 선택한 다음 Mersenne 번호가 반환 값을 기준으로 소수인지 판단했습니다.
Lucas-Lehmer 1 차 테스트는 대량으로 계산되므로 더 큰 N 값의 경우 오랜 시간이 걸릴 수 있습니다. 성능을 향상시키기 위해 다음과 같은 최적화 전략을 고려할 수 있습니다.
이러한 최적화를 통해 특히 더 큰 Mersenne 수를 다룰 때 알고리즘의 실행 속도가 크게 향상 될 수 있습니다.
이 기사에서는 PHP 및 GMP 라이브러리를 사용하여 Lucas-Lehmer Primeness 테스트를 구현하는 방법을 소개합니다. 대규모 작업에 GMP를 사용하면 Mersenne 번호가 소수인지 효과적으로 결정할 수 있습니다. 또한 계산 속도를 높이기 위해 일부 성능 최적화 제안이 제공됩니다. 이 기사 가이 알고리즘을 이해하는 데 관심이있는 독자에게 도움이되기를 바랍니다.
