gmp_legendre — Funktion · PHP-Referenz

Signatur

gmp_legendre(GMP|int|string $num, GMP|int|string $prime): int

Beschreibung

Die Funktion gmp_legendre() berechnet das Legendre-Symbol (a/p) für eine ganze Zahl num (a) und eine ungerade Primzahl prime (p). Das Legendre-Symbol ist ein zahlentheoretisches Konzept, das angibt, ob eine Zahl ein quadratischer Rest modulo einer Primzahl ist.

1: num ist ein quadratischer Rest modulo prime (d. h. es existiert ein x mit x² ≡ num (mod prime)).
-1: num ist kein quadratischer Rest modulo prime.
0: num ist durch prime teilbar.

Das Legendre-Symbol findet Anwendung in der Kryptographie, bei primzahlbasierten Algorithmen sowie in der Zahlentheorie — beispielsweise beim Testen quadratischer Reste oder beim Solovay-Strassen-Primzahltest.

Für zusammengesetzte Zahlen (statt Primzahlen) sollte das verwandte gmp_jacobi() verwendet werden, da gmp_legendre() ausschließlich für Primzahlen korrekt definiert ist.

Parameter

Name	Typ	Default	Beschreibung
$num Pflicht	GMP\|int\|string		Die zu prüfende ganze Zahl (der Zähler des Symbols). Kann als `GMP`-Objekt, als `int` oder als numerischer `string` übergeben werden.
$prime Pflicht	GMP\|int\|string		Eine ungerade Primzahl (der Nenner des Symbols). Muss eine ungerade Primzahl sein, damit das Ergebnis mathematisch korrekt ist. Kann als `GMP`-Objekt, als `int` oder als numerischer `string` übergeben werden.

Rückgabewert

Typ

int

Beschreibung

Gibt 1 zurück, wenn num ein quadratischer Rest modulo prime ist; -1, wenn nicht; 0, wenn num durch prime teilbar ist.

Beispiele

Grundlegende Verwendung von gmp_legendre

<?php
// Ist 2 ein quadratischer Rest modulo 7?
$result = gmp_legendre(2, 7);
echo "Legendre(2, 7) = $result\n";
// 3² = 9 ≡ 2 (mod 7) → ja, quadratischer Rest

// Ist 3 ein quadratischer Rest modulo 7?
$result2 = gmp_legendre(3, 7);
echo "Legendre(3, 7) = $result2\n";
// Kein x mit x² ≡ 3 (mod 7) → kein quadratischer Rest

// num ist durch prime teilbar
$result3 = gmp_legendre(7, 7);
echo "Legendre(7, 7) = $result3\n";
?>

Legendre(2, 7) = 1 Legendre(3, 7) = -1 Legendre(7, 7) = 0

Verwendung mit großen Zahlen und GMP-Objekten

<?php
// Große Primzahl
$prime = gmp_init('104729'); // bekannte Primzahl
$num   = gmp_init('12345');

$symbol = gmp_legendre($num, $prime);

if ($symbol === 1) {
    echo gmp_strval($num) . ' ist ein quadratischer Rest modulo ' . gmp_strval($prime) . "\n";
} elseif ($symbol === -1) {
    echo gmp_strval($num) . ' ist KEIN quadratischer Rest modulo ' . gmp_strval($prime) . "\n";
} else {
    echo gmp_strval($num) . ' ist durch ' . gmp_strval($prime) . " teilbar\n";
}
?>

12345 ist ein quadratischer Rest modulo 104729

// Wichtig · Fallstricke

Achtung: gmp_legendre() ist nur dann mathematisch korrekt, wenn prime eine ungerade Primzahl ist. Bei zusammengesetzten Zahlen liefert die Funktion intern dasselbe Ergebnis wie das Jacobi-Symbol — nutzen Sie in diesem Fall explizit gmp_jacobi(), um den semantischen Unterschied klar zu machen.

Die GMP-Erweiterung muss beim Kompilieren von PHP aktiviert worden sein (oder als Shared Extension geladen sein), andernfalls steht die Funktion nicht zur Verfügung.

Siehe auch

gmp_jacobi gmp_kronecker gmp_powm gmp_init