한국어
한국어
소수 (소수)는 1보다 큰 자연 숫자로 만 나눌 수있는 숫자를 나타냅니다. 예를 들어 2, 3, 5, 7 등. 소수는 암호화 및 암호화 알고리즘, 특히 공개 키 암호화에서 광범위한 응용 프로그램을 가지고 있습니다. 특히 소수의 생성 및 판단은 특히 중요합니다.
숫자가 소수인지 정확하게 결정하는 것이 보안 알고리즘을 구축하기위한 기초입니다. 암호화 알고리즘의 개발로 인해 큰 정수가 프라임인지에 대한 효율적인 판단은 알고리즘 설계의 중요한 부분이되었습니다.
GMP_PROB_PRIME () 는 PHP가 제공하는 함수이며 숫자가 소수인지를 결정하고 GMP 확장에 따라 다릅니다. 기능 프로토 타입은 다음과 같습니다.
int gmp_prob_prime(GMP $a [, int $reps = 10])
매개 변수 설명 :
반환 값 설명 :
이 기능에는 GMP 확장 지원이 필요하며 php.ini 에서 확장자 = gmp를 구성하여 활성화 할 수 있습니다.
PHP의 GMP_PROB_PRIME () 함수의 기본 계층은 확률 알고리즘 인 Solovay-Strassen 프라이머 테스트 알고리즘을 기반으로합니다. 시간 복잡성은 O (k log3 n) 에 관한 것이며, 여기서 k는 테스트 수이고 n은 판단 할 수입니다.
$gmp_b = gmp_random_range(2, $gmp_n);
gmp_random_range ()을 통해 2와 n 사이의 난수를 생성하십시오.
$gmp_gcd = gmp_gcd($gmp_b, $gmp_n);
GCD (B, N) ≠ 1 인 경우, 이는 두 가지가 상호 호환되지 않으며 N이 소수가되어서는 안된다는 것을 의미합니다.
$gmp_r = gmp_powm($gmp_b, gmp_div_q($gmp_n, 2), $gmp_n);
$gmp_jacobi = gmp_jacobi($gmp_b, $gmp_n);
<p>if ($gmp_jacobi == 0 || $gmp_r != $gmp_jacobi) {<br>
return 0;<br>
}<br>
2 차 잔차는 Euler의 차별 방법으로 확인됩니다. 조건이 충족되지 않으면 N은 소수가 아닙니다.
위의 단계는 지정된 횟수로 실행됩니다 (매개 변수 $ reps 에 의해 결정됨) :
for ($i = 0; $i < $reps; $i++) {
$gmp_b = gmp_random_range(2, $gmp_n);
if (gmp_gcd($gmp_b, $gmp_n) != 1) return 0;
$gmp_jacobi = gmp_jacobi($gmp_b, $gmp_n);
$gmp_r = gmp_powm($gmp_b, gmp_div_q(gmp_sub($gmp_n, 1), 2), $gmp_n);
if ($gmp_jacobi == 0 || $gmp_r != $gmp_jacobi) return 0;
}
return 1;
$gmp_n = gmp_init('101');
$prob = gmp_prob_prime($gmp_n);
if ($prob == 2) {
echo "It is likely to be a prime.";
} elseif ($prob == 0) {
echo "It is not prime.";
} else {
echo "It might be a prime.";
}
이 예에서 101은 "소수 일 가능성이 매우 높다"고 인식된다.
GMP_PROB_PRIME () 는 대규모 원칙 테스트를 처리하기위한 PHP에서 중요한 기능입니다. 확률 알고리즘 Solovay-strassen과 결합하여 숫자가 소수인지 효율적으로 결정할 수 있습니다. 이 기능은 암호화 알고리즘, 디지털 서명, 블록 체인 등과 같이 큰 소수를 생성하거나 검증 해야하는 응용 프로그램 시나리오에 특히 적합합니다.
