Français
Français
Les nombres premiers (nombres premiers) se réfèrent à des nombres qui ne peuvent être divisibles que par 1 et en lui-même en nombres naturels supérieurs à 1. Par exemple 2, 3, 5, 7, etc. Les nombres premiers ont de larges applications dans les algorithmes de cryptographie et de cryptage, en particulier dans le cryptage des clés publics, la génération et le jugement des nombres premiers sont particulièrement critiques.
Déterminer avec précision si un nombre est un nombre premier est la base de la construction d'un algorithme de sécurité. Avec le développement d'algorithmes de chiffrement, un jugement efficace sur la question de savoir si les grands entiers sont des nombres premiers sont devenus une partie importante de la conception des algorithmes.
GMP_PROB_PRIME () est une fonction fournie par PHP pour déterminer si un nombre est un nombre premier et dépend de l'extension GMP. Le prototype de fonction est le suivant:
int gmp_prob_prime(GMP $a [, int $reps = 10])
Description du paramètre:
Description de la valeur de retour:
Veuillez noter que cette fonction nécessite une prise en charge de l'extension GMP et peut être activée en configurant l'extension = GMP dans php.ini .
La couche sous-jacente de la fonction GMP_PROB_PRIME () de PHP est basée sur l'algorithme de test d'amorce Solovay-Strassen, qui est un algorithme de probabilité. Sa complexité temporelle est d'environ O (k log3 n) , où K est le nombre de tests et n est le nombre à juger.
$gmp_b = gmp_random_range(2, $gmp_n);
Générez un nombre aléatoire entre 2 et n via GMP_Random_Range () .
$gmp_gcd = gmp_gcd($gmp_b, $gmp_n);
Si GCD (B, N) ≠ 1 , cela signifie que les deux ne sont pas mutuellement compatibles et que n ne doit pas être un nombre premier.
$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>
Le résidu quadratique est vérifié par la méthode de discrimination d'Euler. Si la condition n'est pas remplie, N n'est pas un nombre premier.
Les étapes ci-dessus sont exécutées dans un nombre spécifié de fois (déterminé par le paramètre $ répétitions ):
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.";
}
Dans l'exemple, 101 est reconnu comme "très susceptible d'être un nombre premier".
GMP_PROB_PRIME () est une fonction importante en PHP pour traiter les tests de primabilité à grand nombre. Combiné avec l'algorithme de probabilité Solovay-Strassen, il peut déterminer efficacement si un nombre est un nombre premier. Cette fonction est particulièrement adaptée aux scénarios d'application où de grands nombres premiers doivent être générés ou vérifiés, tels que les algorithmes de chiffrement, les signatures numériques, les blockchains, etc.
