std.modmath — Restklassenarithmetik

Rechnen modulo m ohne Überlauf: erweiterter Euklid, modulares Inverses, chinesischer Restsatz, Ordnung und Primitivwurzeln, Legendre- und Jacobi-Symbol, Quadratwurzeln modulo einer Primzahl.

→ Mathematik-Units · std.prime · std.bignum · std.i128

import std.modmath;

Schicht 0, hängt nur an std.alloc. 24 Funktionen, zwei Konstanten. Alle Beispiele mit lyxc 1.0.21A übersetzt und ausgeführt.

Zwei Konventionen, die man zuerst kennen muss

Der Modul ist auf 2⁶² − 1 begrenzt

MOD_MAX ist 4611686018427387903. Der Grund steht in der Quelle: die Zwischenergebnisse müssen in int64 passen, und dafür ist bei 2⁶² Schluss. ModIsValidModulus(m) prüft 1 ⇐ m ⇐ MOD_MAX; jede Funktion ruft das zuerst auf.

Wer größere Moduln braucht, ist bei std.bignum richtig.

Fehler sind ''MOD_ERR'', nicht Ausnahmen

MOD_ERR ist −1. Da alle gültigen Ergebnisse einer Restklassenrechnung im Bereich 0 … m−1 liegen, ist −1 eindeutig als Fehler erkennbar — aber nur, wenn geprüft wird. Ein ungeprüftes MOD_ERR rechnet sich als −1 still weiter.

Der Rest hat immer das richtige Vorzeichen

unit main;
import std.io;
import std.string;
import std.alloc;
import std.modmath;

fn ZI(t: pchar, v: int64): void { Print(t); PrintLn(IntToStr(v)); }

fn main(): int64 {
    ZI("ModNorm(-7, 5)         : ", ModNorm(-7, 5));
    ZI("roh     -7 % 5         : ", -7 % 5);
    ZI("ModPow(2, 100, 1000007): ", ModPow(2, 100, 1000007));
    ZI("ModInv(3, 11)          : ", ModInv(3, 11));
    ZI("ModInv(4, 8)           : ", ModInv(4, 8));
    ZI("MOD_ERR                : ", MOD_ERR);
    ZI("ModGcd(48, 18)         : ", ModGcd(48, 18));
    return 0;
}

ModNorm(-7, 5)         : 3
roh     -7 % 5         : -2
ModPow(2, 100, 1000007): 698635
ModInv(3, 11)          : 4
ModInv(4, 8)           : -1
MOD_ERR                : -1
ModGcd(48, 18)         : 6

ModNorm liefert 3, der rohe Operator −2. Der %-Operator übernimmt das Vorzeichen des Dividenden; in einer Restklasse ist der Vertreter aber immer 0 … m−1. Wer roh rechnet und den Wert als Feldindex nimmt, greift daneben.

ModInv(4, 8) ist MOD_ERR — und das ist richtig: 4 und 8 sind nicht teilerfremd, ein Inverses existiert nicht. ModInv(3, 11) = 4, denn 3·4 = 12 ≡ 1 (mod 11). Ob ein Inverses überhaupt existiert, beantwortet ModIsUnit(a, m) vorab.

ModPow potenziert per Square-and-Multiply; ModMul vermeidet den Überlauf des Zwischenprodukts. Beides ist der Grund, diese Unit statt eigener %-Rechnungen zu nehmen.

Erweiterter Euklid und chinesischer Restsatz

unit main;
import std.io;
import std.string;
import std.alloc;
import std.modmath;

fn main(): int64 {
    var x: int64 := alloc(8);
    var y: int64 := alloc(8);
    var g: int64 := ModGcdExt(48, 18, x, y);
    Print("GcdExt(48,18): g="); Print(IntToStr(g));
    Print(" x="); Print(IntToStr(peek64(x)));
    Print(" y="); PrintLn(IntToStr(peek64(y)));

    var r: int64 := alloc(8);
    var m: int64 := ModCrt2(2, 3, 3, 5, r);
    Print("CRT x=2(3), x=3(5): modul="); Print(IntToStr(m));
    Print(" rest="); PrintLn(IntToStr(peek64(r)));
    return 0;
}

GcdExt(48,18): g=6 x=-1 y=3
CRT x=2(3), x=3(5): modul=15 rest=8

ModGcdExt liefert neben dem ggT die Koeffizienten der Bézout-Identität: 48·(−1) + 18·3 = −48 + 54 = 6. Darauf beruht das modulare Inverse.

ModCrt2 gibt den zusammengesetzten Modul zurück, keinen Wahrheitswert. Für x ≡ 2 (mod 3) und x ≡ 3 (mod 5) ist die Lösung x ≡ 8 (mod 15) — der Rückgabewert 15 ist der neue Modul, der Rest 8 steht unter outR. Im Fehlerfall — unverträgliche Kongruenzen, ungültiger Modul, oder wenn das kleinste gemeinsame Vielfache MOD_MAX überschreitet — kommt MOD_ERR. Die Quelle prüft das kgV vor der Multiplikation, weil ein stiller Überlauf hier ein gültig aussehendes Ergebnis erzeugen würde.

ModCrtN(resids, mods, n, outR) macht dasselbe für n Kongruenzen, ModSolveLinear löst a·x ≡ b (mod m) — auch dann, wenn a nicht invertierbar ist und es mehrere Lösungen gibt.

Zahlentheorie

unit main;
import std.io;
import std.string;
import std.alloc;
import std.modmath;

fn ZI(t: pchar, v: int64): void { Print(t); PrintLn(IntToStr(v)); }

fn main(): int64 {
    ZI("EulerPhi(12)      : ", ModEulerPhi(12));
    ZI("ModIsPrime(97)    : ", ModIsPrime(97) as int64);
    ZI("ModIsPrime(561)   : ", ModIsPrime(561) as int64);
    ZI("ModOrder(2, 7)    : ", ModOrder(2, 7));
    ZI("PrimitiveRoot(7)  : ", ModPrimitiveRoot(7));
    ZI("Legendre(2, 7)    : ", ModLegendre(2, 7));
    ZI("Jacobi(2, 15)     : ", ModJacobi(2, 15));
    ZI("ModSqrt(2, 7)     : ", ModSqrt(2, 7));
    return 0;
}

EulerPhi(12)      : 4
ModIsPrime(97)    : 1
ModIsPrime(561)   : 0
ModOrder(2, 7)    : 3
PrimitiveRoot(7)  : 3
Legendre(2, 7)    : 1
Jacobi(2, 15)     : 1
ModSqrt(2, 7)     : 4

ModIsPrime(561) ist 0, und das ist der interessante Fall. 561 = 3·11·17 ist eine Carmichael-Zahl — sie besteht den einfachen Fermat-Test für jede zu ihr teilerfremde Basis und sieht damit prim aus. Ein naiver Test fällt darauf herein.

Funktion	Liefert
`ModEulerPhi(n)`	Anzahl der zu `n` teilerfremden Zahlen unter `n`
`ModIsPrime(n)`	Primzahltest bis 2⁶²
`ModOrder(a, m)`	kleinstes `k` mit `a^k ≡ 1`
`ModIsPrimitiveRoot` / `ModPrimitiveRoot`	Erzeuger der multiplikativen Gruppe
`ModLegendre(a, p)`	1 / −1 / 0 — ist `a` quadratischer Rest mod Primzahl `p`?
`ModJacobi(a, n)`	Verallgemeinerung auf zusammengesetzte `n`
`ModSqrt(a, p)`	Quadratwurzel mod `p` (Tonelli-Shanks)

ModJacobi ist kein Ersatz für ModLegendre. Bei zusammengesetztem n bedeutet Jacobi = 1 nicht, dass a ein quadratischer Rest ist — nur, dass die Anzahl der Nichtreste gerade ist. Oben ist Jacobi(2, 15) = 1, obwohl 2 modulo 15 kein Quadrat ist. Wer aus dem Jacobi-Symbol auf Lösbarkeit schließt, liegt falsch.

ModSqrt(2, 7) liefert 4; die zweite Wurzel ist 7 − 4 = 3. Die Funktion gibt eine der beiden zurück.

Abgrenzung

Aufgabe	Unit
Modul bis 2⁶² − 1	`std.modmath`
Beliebig große Zahlen	std.bignum
Primzahltest beliebiger Größe	std.prime
128-Bit-Zwischenergebnis	std.i128

ModIsPrime (schnell, bis 2⁶²) und PrimeIsPrime (beliebig groß) kennen einander derzeit nicht — PrimeIsPrime delegiert für Einwort-Zahlen nicht an modmath. Wer weiß, dass die Zahl in int64 passt, nimmt ModIsPrime.

Letzte Aktualisierung: 2026-08-16 · alle Beispiele mit lyxc 1.0.21A übersetzt und ausgeführt; sämtliche Zahlenwerte gegen eine unabhängige Referenzrechnung geprüft, die Rückgabekonventionen von ModCrt2 und MOD_ERR aus der Quelle abgelesen.