====== 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.

→ [[lyx_-_programmiersprache:units:mathematik|Mathematik-Units]] · [[lyx_-_programmiersprache:units:prime|std.prime]] · [[lyx_-_programmiersprache:units:bignum|std.bignum]] · [[lyx_-_programmiersprache:units:i128|std.i128]]

<code lyx>
import std.modmath;
</code>

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 [[lyx_-_programmiersprache:units:bignum|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 =====

<code lyx>
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;
}
</code>

<code>
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
</code>

**''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 =====

<code lyx>
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;
}
</code>

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

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

<box tip>
> **''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.
</box>

''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 =====

<code lyx>
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;
}
</code>

<code>
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
</code>

**''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&#94;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) |

<box gh>
> **''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.
</box>

''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 | [[lyx_-_programmiersprache:units:bignum|std.bignum]] |
| Primzahltest beliebiger Größe | [[lyx_-_programmiersprache:units:prime|std.prime]] |
| 128-Bit-Zwischenergebnis | [[lyx_-_programmiersprache:units:i128|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.