Comment utiliser PHP et GMP pour effectuer le test de primalité Lucas-Lehmer sur de grands entiers

Comment utiliser PHP et GMP pour effectuer le test de primalité de Lucas-Lehmer sur de grands entiers

Introduction :
En théorie des nombres, le test de primalité de Lucas-Lehmer est une méthode utilisée pour tester si un nombre de Mernessen (nombre de Mersenne) est premier, et est largement utilisé pour le jugement de grands entiers. Dans cet article, nous utiliserons le langage PHP et l'extension GMP (GNU Multiple Precision Arithmetic Library, GNU Multiple Precision Math Library) pour implémenter le test de primalité Lucas-Lehmer et fournir des exemples de code correspondants.

Qu'est-ce que le test de sexualité Lucas-Lehmer ?
Le test de primalité de Lucas-Lehmer est un algorithme efficace utilisé pour déterminer si un nombre de Mounissen de la forme M = 2^n − 1 est un nombre premier. Parmi eux, n est un entier positif supérieur à 1. Cette méthode de test est basée sur les propriétés de la séquence de Lucas-Lehmer. Elle détermine la primalité du nombre de Monessen en calculant de manière itérative l'élément suivant de la séquence, et enfin en jugeant si le dernier élément de la séquence est zéro.

Étapes pour effectuer le test de primalité Lucas-Lehmer à l'aide de PHP et GMP :
Étape 1 : Installer l'extension GMP
Lors de l'exécution d'opérations sur des entiers volumineux, les fonctions intégrées de PHP ne peuvent pas gérer des valeurs plus grandes. Nous devons donc utiliser les extensions GMP pour résoudre ce problème. Lors de l'installation de PHP, vous pouvez choisir d'installer une version avec les extensions GMP activées ou d'activer les extensions GMP dans un environnement PHP existant.

Étape 2 : Écrivez la fonction de test de primalité de Lucas-Lehmer
Voici un exemple de fonction utilisée pour effectuer le test de primalité de 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;
}

Analyse :

• $n : la partie exposant du nombre de Mernessen .
• $s : valeur initiale de la séquence Lucas-Lehmer.
• $m : numéro Monessen.

Dans la fonction, nous utilisons la fonction gmp_pow pour calculer 2 à la puissance $n$, puis soustrayons 1 pour obtenir $m$. Ensuite, nous effectuons des itérations de boucle $n-1$ pour calculer chaque élément de la séquence Lucas-Lehmer. Enfin, déterminez si le dernier élément de la séquence est zéro, déterminant ainsi la primalité du nombre de Monessen.

Étape 3 : Appelez la fonction de test de primalité de Lucas-Lehmer pour tester
Ce qui suit est un exemple d'appel de la fonction de test de primalité de 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.
";
    }
}

Analyse :
Nous définissons un tableau $exponents, qui contient des valeurs d'exposants. Utilisez ensuite une boucle foreach pour appeler la fonction de test de primalité de Lucas-Lehmer en séquence et affichez les informations de jugement correspondantes en fonction des résultats du test.

Résumé :
En utilisant les extensions PHP et GMP, nous pouvons facilement implémenter le test de primalité de Lucas-Lehmer et déterminer si un grand entier est premier. Pour les tests de primalité à grande échelle, l'algorithme de Lucas-Lehmer est très efficace et permet de déterminer rapidement la primalité des nombres de Mönisen. Cet article fournit des exemples de code correspondants, dans l'espoir d'aider les lecteurs à effectuer des tests de primalité de grands entiers dans la pratique.

Référence :

• "Test de primalité Lucas-Lehmer." Wikipedia, The Free Encyclopedia URL : https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
• "Manuel GMP PHP." . URL : https://www.php.net/manual/en/book.gmp.php

Ce qui précède est un article sur la façon d'utiliser PHP et GMP pour effectuer également des tests de primalité Lucas-Lehmer sur de grands entiers. comme exemple de code correspondant.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!