Die Funktion GMP_PROB_PRIME () in PHP ist eine Funktion, mit der festgestellt wird, ob eine Zahl eine Primzahl ist.

Was ist eine Primzahl

Primzahlen (Primzahlen) beziehen sich auf Zahlen, die nur durch 1 und sich selbst in natürlichen Zahlen von mehr als 1 teilbar sein können. Für Beispiel 2, 3, 5, 7 usw. Die Primzahlen haben breite Anwendungen in der Kryptographie- und Verschlüsselungsalgorithmen, insbesondere in der öffentlichen Schlüsselverschlüsselung, die Erzeugung und das Urteil der Primärzahlen sind besonders kritisch.

Genau zu bestimmen, ob eine Zahl eine Primzahl ist, ist die Grundlage für den Aufbau eines Sicherheitsalgorithmus. Mit der Entwicklung von Verschlüsselungsalgorithmen ist ein effizientes Urteil, ob große Ganzzahlen Primzahlen sind, zu einem wichtigen Bestandteil des Algorithmus -Designs.

Einführung in die Funktion GMP_PROB_PRIME ()

GMP_PROB_PRIME () ist eine von PHP bereitgestellte Funktion, um festzustellen, ob eine Zahl eine Primzahl ist, und hängt von der GMP -Erweiterung ab. Der Funktionsprototyp lautet wie folgt:

 
int gmp_prob_prime(GMP $a [, int $reps = 10])

Parameterbeschreibung:

• $ A : Die zu beurteilte Nummer (GMP -Typ)
• $ reps : Die Anzahl der Testwiederholungen, die Standardeinstellung beträgt 10

Rückgabewertbeschreibung:

• Rückgabe 0 : Es ist sicher keine Primzahl
• Rückgabe 1 : Wahrscheinlich eine Primzahl
• Rückgabe 2 : höchstwahrscheinlich eine Primzahl

Bitte beachten Sie, dass diese Funktion GMP -Erweiterungsunterstützung erfordert und durch Konfigurieren von Erweiterung = GMP in php.ini aktiviert werden kann.

Der zugrunde liegende Algorithmus für primitive Eigenschaften Test: Solovay-Strassen

Die zugrunde liegende Schicht der Funktion GMP_PROB_PRIME () von PHP basiert auf dem Solovay-Strassen-Primer-Testalgorithmus, der ein Wahrscheinlichkeitsalgorithmus ist. Seine Zeitkomplexität betrifft O (k log3 n) , wobei k die Anzahl der Tests und N die Anzahl ist, die beurteilt werden soll.

Analyse der Kernschritte des Algorithmus

1. Wählen Sie zufällig eine Nummer B aus, die sich gegen N gegen N ausschließt

 
$gmp_b = gmp_random_range(2, $gmp_n);

Generieren Sie eine Zufallszahl zwischen 2 und n über gmp_random_range () .

2. Berechnen Sie den größten gemeinsamen Divisor GCD

 
$gmp_gcd = gmp_gcd($gmp_b, $gmp_n);

Wenn GCD (B, N) ≠ 1 ist , bedeutet dies, dass die beiden nicht gegenseitig kompatibel sind und N keine Primzahl sein darf.

3. Berechnen Sie den quadratischen Rest und überprüfen Sie das Jacobi -Symbol

 
$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>

Der quadratische Rest wird durch die Diskriminierungsmethode von Euler verifiziert. Wenn der Zustand nicht erfüllt ist, ist N keine Primzahl.

4. Wiederholungstest der Zufälligkeit von B

Die obigen Schritte werden in einer bestimmten Anzahl von Male ausgeführt (bestimmt durch den Parameter $ reps ):

 
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_PROB_PRIME () Funktionsnutzung Beispiel

 
$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.";
}

Im Beispiel wird 101 als "sehr wahrscheinlich eine Primzahl" anerkannt.

Zusammenfassen

GMP_PROB_PRIME () ist eine wichtige Funktion in PHP für die Verarbeitung von Tests mit großen Zahlen. In Kombination mit dem Wahrscheinlichkeitsalgorithmus Solovay-Strassen kann es effizient bestimmen, ob eine Zahl eine Primzahl ist. Diese Funktion eignet sich besonders für Anwendungsszenarien, in denen große Primzahlen generiert oder verifiziert werden müssen, z. B. Verschlüsselungsalgorithmen, digitale Signaturen, Blockchains usw.