Signatur
Beschreibung
gmp_prob_prime() testet eine beliebig große ganze Zahl darauf, ob sie wahrscheinlich eine Primzahl ist. Dazu wird der Miller-Rabin-Primzahltest verwendet, ein probabilistischer Algorithmus, der mit steigender Anzahl von Wiederholungen eine höhere Zuverlässigkeit bietet.
Der Rückgabewert ist eine Ganzzahl mit drei möglichen Bedeutungen: 0 bedeutet, die Zahl ist definitiv zusammengesetzt (keine Primzahl); 1 bedeutet, die Zahl ist wahrscheinlich eine Primzahl; 2 bedeutet, die Zahl ist definitiv eine Primzahl. Das Ergebnis 2 wird nur für kleine Zahlen zurückgegeben, die intern exakt geprüft werden können.
Der Parameter $repetitions steuert, wie viele Runden des Miller-Rabin-Tests durchgeführt werden. Mit mehr Runden sinkt die Wahrscheinlichkeit eines falsch-positiven Ergebnisses exponentiell: Nach k Runden beträgt die Fehlerwahrscheinlichkeit höchstens 4−k. Für kryptografische Anwendungen sollten mindestens 15–25 Runden verwendet werden.
Die Funktion ist Teil der GMP-Erweiterung und erfordert, dass diese kompiliert und aktiviert ist. Seit PHP 5.6 werden GMP-Objekte direkt unterstützt; in älteren Versionen werden GMP-Ressourcen übergeben.
Parameter
| Name | Typ | Default | Beschreibung |
|---|---|---|---|
| $num Pflicht | GMP|int|string | Die zu testende Zahl als GMP-Objekt, Integer oder numerischer String. |
|
| $repetitions | int | 10 | Anzahl der Miller-Rabin-Testrunden. Höhere Werte erhöhen die Zuverlässigkeit des Ergebnisses, erfordern aber mehr Rechenzeit. Empfohlen: mindestens 15 für kryptografische Zwecke. |
Rückgabewert
0 zurück, wenn die Zahl definitiv keine Primzahl ist; 1, wenn sie wahrscheinlich eine Primzahl ist; 2, wenn sie definitiv eine Primzahl ist (nur bei kleinen Zahlen möglich).Beispiele
Grundlegende Primzahl-Tests
<?php
$zahlen = [2, 7, 15, 97, 100, 104729];
foreach ($zahlen as $z) {
$ergebnis = gmp_prob_prime($z);
$status = match($ergebnis) {
0 => 'keine Primzahl',
1 => 'wahrscheinlich Primzahl',
2 => 'definitiv Primzahl',
};
echo "$z: $status\n";
}Test einer großen Zahl mit erhöhter Wiederholungsanzahl
<?php
// Große Mersenne-Primzahlkandidaten testen
$kandidat = gmp_init('2305843009213693951'); // 2^61 - 1, bekannte Mersenne-Primzahl
$ergebnis = gmp_prob_prime($kandidat, 25);
if ($ergebnis > 0) {
echo "Die Zahl ist" . ($ergebnis === 2 ? ' definitiv' : ' wahrscheinlich') . " eine Primzahl.\n";
} else {
echo "Die Zahl ist keine Primzahl.\n";
}Primzahlgenerierung für kryptografische Schlüssel
<?php
// Zufällige wahrscheinliche Primzahl in einem bestimmten Bereich finden
function findePrimzahl(int $bits = 128): GMP {
do {
// Zufällige ungerade Zahl der gewünschten Bitlänge erzeugen
$bytes = random_bytes((int)ceil($bits / 8));
$hex = bin2hex($bytes);
$zahl = gmp_init($hex, 16);
// Sicherstellen, dass die Zahl ungerade ist
$zahl = gmp_or($zahl, gmp_init(1));
} while (gmp_prob_prime($zahl, 20) === 0);
return $zahl;
}
$primzahl = findePrimzahl(64);
echo "Gefundene wahrscheinliche Primzahl: " . gmp_strval($primzahl) . "\n";// Wichtig · Fallstricke
Sicherheitshinweis: Für kryptografische Anwendungen (z. B. RSA-Schlüsselgenerierung) sollte $repetitions auf mindestens 15–25 gesetzt werden. Der Standardwert 10 ist für allgemeine Zwecke ausreichend, aber für sicherheitskritische Anwendungen zu niedrig.
Falsch-Positive: Ein Rückgabewert von 1 bedeutet wahrscheinlich eine Primzahl — es besteht eine sehr geringe Restwahrscheinlichkeit, dass es sich um eine zusammengesetzte Zahl (Carmichael-Zahl) handelt. Diese Wahrscheinlichkeit beträgt nach k Runden höchstens 4−k.
Performance: Bei sehr großen Zahlen (z. B. 2048-Bit-Zahlen) steigt die Laufzeit erheblich. Ein guter Kompromiss aus Sicherheit und Performance liegt bei 15–20 Runden.
Die Funktion erfordert die PHP-GMP-Erweiterung (ext/gmp). Ist diese nicht verfügbar, wird ein fataler Fehler ausgelöst.