Wie man mit PHP und GMP einen Lucas-Lehmer-Primalitätstest für große ganze Zahlen durchführt

So verwenden Sie PHP und GMP, um den Lucas-Lehmer-Primalitätstest für große ganze Zahlen durchzuführen

Einführung:
In der Zahlentheorie ist der Lucas-Lehmer-Primalitätstest eine Methode, mit der getestet wird, ob eine Mernessen-Zahl (Mersenne-Zahl) eine Primzahl ist. Es wird häufig zur Beurteilung großer ganzer Zahlen verwendet. In diesem Artikel werden wir die PHP-Sprache und die GMP-Erweiterung (GNU Multiple Precision Arithmetic Library, GNU Multiple Precision Math Library) verwenden, um den Lucas-Lehmer-Primalitätstest zu implementieren und entsprechende Codebeispiele bereitzustellen.

Was ist der Lucas-Lehmer-Sexualitätstest?
Der Lucas-Lehmer-Primalitätstest ist ein effizienter Algorithmus zur Bestimmung, ob eine Mounissen-Zahl der Form M = 2^n − 1 eine Primzahl ist. Unter diesen ist n eine positive ganze Zahl größer als 1. Diese Testmethode basiert auf den Eigenschaften der Lucas-Lehmer-Folge. Sie bestimmt die Primalität der Monessen-Zahl, indem sie iterativ das nächste Element der Folge berechnet und schließlich beurteilt, ob das letzte Element der Folge Null ist.

Schritte zur Durchführung des Lucas-Lehmer-Primalitätstests mit PHP und GMP:
Schritt 1: GMP-Erweiterung installieren
Bei der Durchführung großer Ganzzahloperationen können die integrierten Funktionen von PHP keine größeren Werte verarbeiten. Daher müssen wir GMP-Erweiterungen verwenden, um dieses Problem zu lösen. Bei der Installation von PHP können Sie wählen, ob Sie eine Version mit aktivierten GMP-Erweiterungen installieren oder GMP-Erweiterungen in einer vorhandenen PHP-Umgebung aktivieren möchten.

Schritt 2: Schreiben Sie die Lucas-Lehmer-Primzahltestfunktion
Das Folgende ist ein Beispiel einer Funktion, die zur Durchführung des Lucas-Lehmer-Primzahltests verwendet wird:

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: der Exponententeil der Mernessen-Zahl .
• $s: Anfangswert der Lucas-Lehmer-Folge.
• $m: Monessen-Zahl.

In der Funktion verwenden wir die Funktion gmp_pow, um 2 hoch $n$ zu berechnen und subtrahieren dann 1, um $m$ zu erhalten. Anschließend führen wir $n-1$-Schleifeniterationen durch, um jedes Element der Lucas-Lehmer-Folge zu berechnen. Bestimmen Sie abschließend, ob das letzte Element der Folge Null ist, und bestimmen Sie so die Primalität der Monessen-Zahl.

Schritt 3: Aufrufen der Lucas-Lehmer-Primzahltestfunktion zum Testen
Das Folgende ist ein Beispiel für den Aufruf der Lucas-Lehmer-Primzahltestfunktion:

$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:
Wir definieren ein Array $exponents, das einige Exponentenwerte enthält. Verwenden Sie dann eine foreach-Schleife, um die Lucas-Lehmer-Primalitätstestfunktion nacheinander aufzurufen und die entsprechenden Beurteilungsinformationen basierend auf den Testergebnissen auszugeben.

Zusammenfassung:
Durch die Verwendung von PHP- und GMP-Erweiterungen können wir den Lucas-Lehmer-Primalitätstest einfach implementieren und bestimmen, ob eine große ganze Zahl eine Primzahl ist. Für groß angelegte Primalitätstests ist der Lucas-Lehmer-Algorithmus sehr effizient und kann schnell die Primalität von Mönisen-Zahlen bestimmen. Dieser Artikel enthält entsprechende Codebeispiele und hofft, den Lesern dabei zu helfen, große ganzzahlige Primzahltests in der Praxis durchzuführen.

Referenz:

• „Lucas-Lehmer-Primalitätstest.“ Wikipedia, Die freie Enzyklopädie URL: https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
• „GMP-Handbuch.“ . URL: https://www.php.net/manual/en/book.gmp.php

Der obige Artikel zeigt, wie man mit PHP und GMP auch Lucas-Lehmer-Primalitätstests für große ganze Zahlen durchführt als entsprechendes Codebeispiel.

Das obige ist der detaillierte Inhalt vonWie man mit PHP und GMP einen Lucas-Lehmer-Primalitätstest für große ganze Zahlen durchführt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!