gmp_gcdext — Funktion · PHP-Referenz

Signatur

gmp_gcdext(GMP|int|string $num1, GMP|int|string $num2): array

Beschreibung

gmp_gcdext implementiert den erweiterten euklidischen Algorithmus und liefert nicht nur den größten gemeinsamen Teiler (ggT) zweier ganzer Zahlen, sondern auch die sogenannten Bézout-Koeffizienten s und t. Diese erfüllen die Identität: num1 * s + num2 * t = ggT(num1, num2).

Das Ergebnis ist ein assoziatives Array mit den Schlüsseln g (der ggT), s (Koeffizient für num1) und t (Koeffizient für num2). Alle drei Werte sind vom Typ GMP.

Die Funktion ist besonders nützlich in der Kryptographie und der Zahlentheorie, z. B. zur Berechnung modularer Inversen (wie beim RSA-Algorithmus), zur Lösung linearer diophantischer Gleichungen oder zur Analyse teilerfremder Zahlen.

Alle Parameter können als GMP-Objekt, als int oder als numerischer string übergeben werden, was eine flexible Nutzung auch mit sehr großen Zahlen ermöglicht.

Parameter

Name	Typ	Default	Beschreibung
$num1 Pflicht	GMP\|int\|string		Erste ganze Zahl. Kann als `GMP`-Objekt, als `int` oder als numerischer `string` übergeben werden.
$num2 Pflicht	GMP\|int\|string		Zweite ganze Zahl. Kann als `GMP`-Objekt, als `int` oder als numerischer `string` übergeben werden.

Rückgabewert

Typ

array

Beschreibung

Gibt ein assoziatives Array mit drei Schlüsseln zurück:

g — der ggT von num1 und num2 als GMP-Objekt
s — der Bézout-Koeffizient für num1 als GMP-Objekt
t — der Bézout-Koeffizient für num2 als GMP-Objekt

Es gilt stets: num1 * s + num2 * t = g.

Beispiele

Bézout-Koeffizienten und ggT berechnen

<?php
$a = gmp_init(35);
$b = gmp_init(15);

$result = gmp_gcdext($a, $b);

$g = gmp_strval($result['g']);
$s = gmp_strval($result['s']);
$t = gmp_strval($result['t']);

echo "ggT(35, 15) = $g\n";
echo "Bézout: 35 * $s + 15 * $t = $g\n";

// Probe
$probe = gmp_add(gmp_mul($a, $result['s']), gmp_mul($b, $result['t']));
echo "Probe: " . gmp_strval($probe) . "\n";

ggT(35, 15) = 5 Bézout: 35 * 1 + 15 * -2 = 5 Probe: 5

Modulare Inverse berechnen (wie bei RSA)

<?php
// Berechnung der modularen Inversen von a modulo m
// Das ist möglich, wenn ggT(a, m) = 1
$a = gmp_init(3);
$m = gmp_init(11);

$result = gmp_gcdext($a, $m);

if (gmp_cmp($result['g'], 1) === 0) {
    // s ist die modulare Inverse von a modulo m
    $inverse = gmp_mod($result['s'], $m);
    echo "Modulare Inverse von 3 mod 11: " . gmp_strval($inverse) . "\n";
    // Probe: 3 * 4 = 12 ≡ 1 (mod 11)
    $probe = gmp_mod(gmp_mul($a, $inverse), $m);
    echo "Probe: 3 * " . gmp_strval($inverse) . " mod 11 = " . gmp_strval($probe) . "\n";
} else {
    echo "Keine modulare Inverse vorhanden (ggT != 1).\n";
}

Modulare Inverse von 3 mod 11: 4 Probe: 3 * 4 mod 11 = 1

// Wichtig · Fallstricke

Vorzeichen: Die Bézout-Koeffizienten können negativ sein. Bei der Berechnung modularer Inversen muss s daher ggf. mit gmp_mod in den positiven Bereich gebracht werden (wie im zweiten Beispiel gezeigt).

Eindeutigkeit: Die Bézout-Koeffizienten sind nicht eindeutig — es gibt unendlich viele Lösungspaare. Die Funktion liefert ein konkretes Paar, das vom Algorithmus ermittelt wird.

Voraussetzung für modulare Inverse: Eine modulare Inverse existiert nur dann, wenn ggT(a, m) = 1, also wenn a und m teilerfremd sind. Andernfalls ist das Ergebnis mathematisch nicht definiert.

GMP-Erweiterung erforderlich: Die Funktion setzt die PHP-Erweiterung ext-gmp voraus. Diese muss bei der PHP-Kompilierung aktiviert oder als Modul geladen sein.

Siehe auch

gmp_gcd gmp_invert gmp_lcm gmp_mod gmp_init