Signatur
Beschreibung
Das Jacobi-Symbol ist ein zahlentheoretisches Konzept, das hauptsächlich in der Primzahltesttheorie und Kryptographie verwendet wird. Es ist eine Verallgemeinerung des Legendre-Symbols und wird für einen ganzzahligen Zähler num und einen ungeraden positiven Nenner p berechnet. Das Ergebnis ist immer -1, 0 oder 1.
Wenn p eine ungerade Primzahl ist, entspricht das Jacobi-Symbol dem Legendre-Symbol: Es gibt an, ob num ein quadratischer Rest modulo p ist. Ein Rückgabewert von 1 bedeutet, dass num ein quadratischer Rest modulo p sein könnte (oder gleich 1 ist), -1 bedeutet, dass dies nicht der Fall ist, und 0 bedeutet, dass num und p einen gemeinsamen Teiler größer als 1 haben.
Wichtig: Wenn p keine Primzahl ist, kann gmp_jacobi trotzdem 1 zurückgeben, obwohl num kein quadratischer Rest modulo p ist. Das Jacobi-Symbol ist daher kein verlässlicher Primzahltest, wird aber als Bestandteil von Algorithmen wie dem Solovay-Strassen-Primzahltest eingesetzt.
Die Funktion erwartet, dass p eine ungerade positive ganze Zahl ist. Die Argumente können als GMP-Objekte, native PHP-Integer oder numerische Strings übergeben werden.
Parameter
| Name | Typ | Default | Beschreibung |
|---|---|---|---|
| $num Pflicht | GMP|int|string | Der Zähler des Jacobi-Symbols. Kann ein GMP-Objekt, ein PHP-Integer oder ein numerischer String sein. |
|
| $p Pflicht | GMP|int|string | Der Nenner des Jacobi-Symbols. Muss eine ungerade positive ganze Zahl sein. Kann als GMP-Objekt, PHP-Integer oder numerischer String übergeben werden. |
Rückgabewert
-1, 0 oder 1 zurück: 0 bedeutet, dass num und p einen gemeinsamen Faktor haben; 1 bedeutet, dass num ein möglicher quadratischer Rest modulo p ist; -1 bedeutet, dass num kein quadratischer Rest modulo p ist.Beispiele
Einfache Berechnung des Jacobi-Symbols
<?php
// Jacobi-Symbol (1/3) — 1 ist immer ein quadratischer Rest
$result1 = gmp_jacobi(1, 3);
echo "Jacobi(1, 3) = $result1\n";
// Jacobi-Symbol (2/3) — 2 ist kein quadratischer Rest mod 3
$result2 = gmp_jacobi(2, 3);
echo "Jacobi(2, 3) = $result2\n";
// Jacobi-Symbol (3/9) — gemeinsamer Faktor, Ergebnis ist 0
$result3 = gmp_jacobi(3, 9);
echo "Jacobi(3, 9) = $result3\n";Jacobi-Symbol mit GMP-Objekten und großen Zahlen
<?php
// Einsatz mit großen GMP-Zahlen
$num = gmp_init('123456789012345678901234567890');
$p = gmp_init('999999999999999999999999999999'); // muss ungerade sein
$jacobi = gmp_jacobi($num, $p);
echo "Jacobi-Symbol: $jacobi\n";
// Solovay-Strassen-ähnlicher Primzahltest (vereinfacht)
function possiblyPrime(int $n, int $rounds = 5): bool {
if ($n < 2) return false;
if ($n === 2) return true;
if ($n % 2 === 0) return false;
for ($i = 0; $i < $rounds; $i++) {
$a = rand(2, $n - 1);
$jacobi = gmp_jacobi($a, $n);
// Berechne a^((n-1)/2) mod n
$exp = gmp_powm($a, (int)(($n - 1) / 2), $n);
$expVal = gmp_intval($exp);
// Wenn Jacobi und Euler-Kriterium nicht übereinstimmen, ist n zusammengesetzt
if ($jacobi === 0 || ($jacobi + $n) % $n !== $expVal) {
return false;
}
}
return true;
}
echo possiblyPrime(17) ? "17 ist wahrscheinlich prim\n" : "17 ist zusammengesetzt\n";
echo possiblyPrime(15) ? "15 ist wahrscheinlich prim\n" : "15 ist zusammengesetzt\n";// Wichtig · Fallstricke
Achtung: Der Parameter p muss ungerade und positiv sein. Wird eine gerade Zahl übergeben, erzeugt PHP eine E_WARNING und die Funktion gibt 0 zurück.
Das Jacobi-Symbol ist nicht dasselbe wie ein Primzahltest: Ein Rückgabewert von 1 garantiert nicht, dass num wirklich ein quadratischer Rest modulo p ist, wenn p keine Primzahl ist (sogenannte Euler-Pseudoprimzahlen).
Die GMP-Erweiterung muss aktiviert sein (--with-gmp beim Kompilieren oder entsprechende PHP-Extension in der php.ini). Ab PHP 5.6 werden GMP-Objekte statt GMP-Ressourcen zurückgegeben.