PHP combiné avec GMP pour implémenter un didacticiel de test de primalité Lucas-Lehmer sur de grands entiers

introduction

En théorie des nombres, le test de primalité de Lucas-Lehmer est une méthode efficace pour déterminer si un nombre de Mersenne est premier. Dans cet article, nous combinerons 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 un exemple de code complet.

Qu'est-ce que le test primordial de Lucas-Lehmer ?

Le test de primalité de Lucas-Lehmer est un algorithme spécialement conçu pour détecter si un nombre de Mersenne de la forme M = 2^n - 1 est premier, où n est un entier positif supérieur à 1. Le test est basé sur la séquence de Lucas-Lehmer. Il calcule de manière itérative chaque élément de la séquence, et détermine enfin si le dernier élément de la séquence est zéro, déterminant ainsi la primalité du nombre de Mersenne.

Tests Lucas-Lehmer utilisant PHP et GMP

Installer l'extension GMP

Les fonctions intégrées de PHP ne peuvent pas gérer de très grandes opérations sur des entiers, l'extension GMP est donc requise. Lors de l'installation de PHP, vous pouvez choisir une version avec les extensions GMP activées ou activer les extensions GMP dans votre environnement existant.

Écriture d'une fonction de test de primalité de Lucas-Lehmer

 fonction lucasLehmerTest($n)
{
    $s = '4';
    $m = gmp_pow('2', $n) - '1';

    pour ($i = 1; $i < $n - 1; $i++) {
        $s = gmp_mod(gmp_pow($s, 2) - 2, $m);
    }

    si ($s == &#39;0&#39;) {
        renvoie vrai ;
    }

    renvoie faux ;
}

Analyse:

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

Dans la fonction, gmp_pow est utilisé pour calculer 2 à la puissance $n$ moins 1 pour obtenir $m$, puis itère $n-1$ fois pour calculer la séquence de Lucas-Lehmer, et enfin détermine si le dernier élément de la séquence est nul pour déterminer la primalité.

Appelez la fonction de test de primalité de Lucas-Lehmer

 $exposants = [2, 3, 5, 7, 13, 17];

foreach ($exposants comme $exposant) {
    $result = lucasLehmerTest($exposant);

    si ($résultat) {
        echo "2^$exposant - 1 est un nombre premier.";
    } autre {
        echo "2^$exposant - 1 n'est pas un nombre premier.";
    }
}

Analyse:

Nous définissons un tableau $exposants, contenant plusieurs valeurs d'exposants, puis utilisons une boucle foreach pour appeler la fonction de test de primalité de Lucas-Lehmer afin de générer des informations de jugement basées sur les résultats du test.

Résumer

Grâce aux extensions PHP et GMP, vous pouvez facilement implémenter le test de primalité de Lucas-Lehmer et déterminer si un grand entier est premier. Pour le jugement de primalité des grands nombres de Mersenne, l'algorithme de Lucas-Lehmer est plus efficace et permet d'obtenir des résultats rapidement. Les exemples de code fournis dans cet article peuvent être utilisés comme référence pratique.

Références

• Test de primalité de Lucas-Lehmer. Wikipédia, l'encyclopédie libre. URL : https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
• Manuel BPF. PHP. URL : https://www.php.net/manual/en/book.gmp.php