PHP와 GMP를 사용하여 대량의 Miller-Rabin 소수성 테스트를 구현하는 방법

PHP와 GMP를 사용하여 큰 숫자의 Miller-Rabin 소수성 테스트를 구현하는 방법

소개:
소수는 암호화 및 컴퓨터 과학에서 중요한 역할을 합니다. 밀러-라빈 소수성 테스트(Miller-Rabin primality test)는 숫자가 소수인지 테스트하는 데 사용되는 확률론적 알고리즘으로 높은 확률로 정답을 제공합니다. 이 기사에서는 PHP 언어와 GMP 라이브러리(GNU Multiple Precision Arithmetic Library)를 사용하여 큰 수에 대한 Miller-Rabin 소수성 테스트 알고리즘을 구현하는 방법을 소개합니다.

GMP 라이브러리 소개:
GMP 라이브러리는 고정밀 계산을 위한 오픈 소스 라이브러리로, 큰 정수를 지원합니다. GMP 라이브러리를 사용하여 큰 수 덧셈, 뺄셈, 곱셈, 나눗셈 및 기타 연산을 포함한 큰 수 계산을 처리할 수 있습니다.

알고리즘 원리:
밀러-라빈 소수성 검정 알고리즘은 페르마의 작은 정리(Fermat's Little Theorem)의 확장을 기반으로 합니다. 정리에 따르면 소수 p와 정수 a가 상대적으로 소수이고 a^(p-1) ñ 1(mod p)이면 a는 p의 밑이고 p는 그 밑의 절반 이상을 가집니다.

밀러-라빈 소수 검정 알고리즘에 따르면, 서로 다른 밑수를 여러 번 선택하여 특정 확률로 숫자가 소수인지 여부를 확인할 수 있습니다. 알고리즘의 아이디어는 테스트된 각 숫자 n에 대해 임의의 베이스 b를 선택한 다음 a^d = 1 (mod n) 및 a^(2^r*d) = -1 (mod n)을 계산하는 것입니다. ) 그것이 사실이든, 그것이 사실이라면 n은 소수일 수 있고, 그렇지 않으면 n이 합성수라고 확신할 수 있습니다.

코드 예:

<?php

// 导入GMP库
if (!extension_loaded('gmp')) {
    dl('gmp.so');
}

function millerRabinTest($n, $k = 20) {
    if ($n <= 1 || $n == 4) {
        return false;
    }
    if ($n <= 3) {
        return true;
    }

    // 将$n-1表示为(2^r) * d的形式
    $r = 0;
    $d = $n - 1;
    while (gmp_mod($d, 2) == 0) {
        $d >>= 1;
        $r++;
    }

    for ($i = 0; $i < $k; $i++) {
        $a = gmp_random_range(2, $n - 2);
        $x = gmp_powm($a, $d, $n);

        if ($x == 1 || $x == $n - 1) {
            continue;
        }

        $continueLoop = false;
        for ($j = 0; $j < $r - 1; $j++) {
            $x = gmp_powm($x, 2, $n);
            if ($x == 1) {
                return false;
            }
            if ($x == $n - 1) {
                $continueLoop = true;
                break;
            }
        }

        if (!$continueLoop) {
            return false;
        }
    }

    return true;
}

// 测试示例
$numbers = [
    gmp_init('2'),
    gmp_init('3'),
    gmp_init('4'),
    gmp_init('17'),
    gmp_init('7919'),
    gmp_init('999999999999999993')
];

foreach ($numbers as $number) {
    echo gmp_strval($number) . ' is ' . (millerRabinTest($number) ? 'prime' : 'composite') . PHP_EOL;
}

이 예에서는 millerRabinTest() 함수를 사용하여 숫자가 소수인지 테스트합니다. 매개변수 $k는 테스트 반복 횟수를 나타냅니다. 테스트 예에서는 일부 숫자를 별도로 테스트하고 테스트 결과를 인쇄했습니다.

요약:
Miller-Rabin 소수성 테스트 알고리즘은 효율적인 소수성 탐지 알고리즘으로, 특히 큰 숫자에 적합합니다. PHP 언어와 GMP 라이브러리를 사용하면 이 알고리즘을 쉽게 구현할 수 있습니다. Miller-Rabin 소수 테스트를 통해 숫자가 소수인지 여부를 효과적으로 확인할 수 있으므로 암호화, 보안 및 기타 분야에서 강력한 도구를 제공합니다.

위 내용은 PHP와 GMP를 사용하여 대량의 Miller-Rabin 소수성 테스트를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!