====== std.bignum — Ganzzahlen beliebiger Größe ======

Zahlen ohne Größenbeschränkung: Grundrechenarten, Division mit Rest, ggT, Dezimal- und Hexdarstellung und modulare Potenz — die zweite davon per Montgomery, rund 47× schneller.

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

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

Schicht 2, hängt an [[lyx_-_programmiersprache:units:i128|std.i128]] und [[lyx_-_programmiersprache:units:bits|std.bits]]. 37 Funktionen. Alle Beispiele mit ''lyxc 1.0.21A'' übersetzt und ausgeführt.

----

===== Darstellung =====

Eine große Zahl ist ein Speicherblock mit Kopf. ''BigNew(capWords)'' legt ihn an, ''BigFree'' gibt ihn zurück:

<code lyx>
var a: int64 := BigNew(64);          // Platz für 64 Wörter = 4096 Bit
BigFromDecimal("123456789012345678901234567890"c, a);
</code>

<WRAP alert>
**Die Kapazität ist fest.** ''BigNew(capWords)'' reserviert einmal; eine Rechnung, deren Ergebnis nicht hineinpasst, gibt ''false'' zurück. Der Rückgabewert **ist** die Fehleranzeige — jede rechnende Funktion liefert ''bool''.

Als Faustregel: das Produkt zweier Zahlen braucht die **Summe** ihrer Wortlängen, eine Potenz entsprechend mehr. Wer knapp bemisst, bekommt kein falsches Ergebnis, aber ein ''false'', das leicht übersehen wird.
</WRAP>

''BigCap'', ''BigLen'', ''BigBitLen'' und ''BigSign'' geben Auskunft. ''BigWord(p, i)'' liefert ein einzelnes Wort.

<box gh>
> **Wörter aus ''BigWord'' sind Bitmuster, keine Zahlen.** Jeder Vergleich darauf muss vorzeichenlos sein — ''w < 2'' ist für ''2⁶⁴−1'' **wahr**, weil dessen Wort als ''int64'' negativ ist. Dieser Fehler ist bei der Entstehung der Unit dreimal aufgetreten und äußert sich als verdächtig schnelles, falsches Ergebnis. ''I128LtU64'' aus [[lyx_-_programmiersprache:units:i128|std.i128]] ist der richtige Vergleich.
</box>

----

===== Rechnen =====

<code lyx>
unit main;
import std.io;
import std.string;
import std.alloc;
import std.bignum;

fn ZI(t: pchar, v: int64): void { Print(t); PrintLn(IntToStr(v)); }
fn ZD(t: pchar, p: int64): void {
    var b: int64 := alloc(512);
    BigToDecimal(p, b, 512);
    Print(t); PrintLn(b as pchar);
}

fn main(): int64 {
    var a: int64 := BigNew(64);
    var b: int64 := BigNew(64);
    var r: int64 := BigNew(64);

    BigFromDecimal("123456789012345678901234567890"c, a);
    BigFromDecimal("987654321098765432109876543210"c, b);

    BigMul(a, b, r);   ZD("a * b            = ", r);
    BigAdd(a, b, r);   ZD("a + b            = ", r);
    BigGcd(a, b, r);   ZD("gcd(a, b)        = ", r);

    var z: int64 := BigNew(64);
    var p: int64 := BigNew(64);
    BigSetU64(z, 2);
    BigShl(z, 99, p);
    ZD("2^100            = ", p);
    ZI("BitLen(2^100)    = ", BigBitLen(p));

    var base: int64 := BigNew(64);
    var ex: int64 := BigNew(64);
    var mod: int64 := BigNew(64);
    var out: int64 := BigNew(64);
    BigSetU64(base, 2);
    BigSetU64(ex, 1000);
    BigFromDecimal("1000000007"c, mod);
    BigPowMod(base, ex, mod, out);
    ZD("2^1000 mod 1e9+7 = ", out);
    return 0;
}
</code>

<code>
a * b            = 121932631137021795226185032733622923332237463801111263526900
a + b            = 1111111110111111111011111111100
gcd(a, b)        = 9000000000900000000090
2^100            = 1267650600228229401496703205376
BitLen(2^100)    = 101
2^1000 mod 1e9+7 = 688423210
</code>

Sämtliche Werte stimmen mit der Referenzrechnung überein.

----

===== Modulare Potenz: zwei Wege =====

^ Funktion ^ Voraussetzung ^ Geschwindigkeit ^
| ''BigPowMod(b, e, m, out)'' | beliebiger Modul | über Division |
| ''BigPowModOdd(b, e, m, out)'' | **ungerader** Modul | Montgomery, **rund 47× schneller** |

<box tip>
> **Der Faktor 47 ist der Grund, warum die Unit brauchbar ist.** Ein Miller-Rabin-Test auf einer 256-Bit-Zahl hätte über die Division rund **8 Sekunden** gekostet — damit wäre [[lyx_-_programmiersprache:units:prime|std.prime]] unbenutzbar gewesen. Montgomery ersetzt die Division im inneren Schritt durch Multiplikation und Verschiebung; das setzt einen ungeraden Modul voraus, und genau das ist bei Primzahltests und RSA immer erfüllt.
>
> Gemessen **vor** dem Bauen: hätte man erst die Unit geschrieben und dann gemessen, wäre eine unbrauchbare Unit entstanden.
</box>

----

===== Funktionsübersicht =====

^ Gruppe ^ Funktionen ^
| Anlegen | ''BigNew'' · ''BigFree'' · ''BigZero'' · ''BigCopy'' |
| Setzen | ''BigSetU64'' · ''BigSetI64'' · ''BigFromDecimal'' |
| Abfragen | ''BigCap'' · ''BigLen'' · ''BigSign'' · ''BigIsZero'' · ''BigIsNeg'' · ''BigIsOdd'' · ''BigBitLen'' · ''BigTestBit'' · ''BigWord'' |
| Grenzen | ''BigFitsU64'' · ''BigToU64'' |
| Grundrechenarten | ''BigAdd'' · ''BigSub'' · ''BigMul'' · ''BigMulU64'' · ''BigNeg'' · ''BigAbs'' |
| Schieben | ''BigShl'' · ''BigShr'' |
| Division | ''BigDivRem'' · ''BigDivRemAbs'' · ''BigMod'' |
| Zahlentheorie | ''BigGcd'' · ''BigPowMod'' · ''BigPowModOdd'' |
| Vergleichen | ''BigCmp'' · ''BigCmpAbs'' · ''BigEquals'' |
| Text | ''BigToDecimal'' · ''BigToHex'' · ''BigFromDecimal'' |

''BigDivRem'' folgt dem Vorzeichen der Sprache, ''BigDivRemAbs'' rechnet auf Beträgen. ''BigToDecimal'' braucht einen ausreichend großen Puffer — eine ''n''-Wort-Zahl hat bis zu ''n · 20'' Dezimalstellen.

----

===== Abgrenzung =====

^ Bereich ^ Unit ^
| bis 2⁶³−1 | roh, mit [[lyx_-_programmiersprache:units:sat|std.sat]] |
| 128 Bit | [[lyx_-_programmiersprache:units:i128|std.i128]] |
| **beliebig groß** | ''std.bignum'' |
| Restklassen bis 2⁶² | [[lyx_-_programmiersprache:units:modmath|std.modmath]] |
| Primzahltest beliebiger Größe | [[lyx_-_programmiersprache:units:prime|std.prime]] |

<box gh>
> **Für ein eigenes RSA fehlt noch etwas.** Vorhanden sind Bignum-Arithmetik und Miller-Rabin. Es fehlen: eine geprüfte Zufallsquelle für die Schlüsselerzeugung, eine konstantzeit-Potenzierung (die Montgomery-Leiter aus [[lyx_-_programmiersprache:units:crypto:ec|std.crypto.ec]] zeigt den Weg) und der erweiterte Euklid für das modulare Inverse über große Zahlen. ''std.crypto.rsa'' im Bestand ist reiner OpenSSL-Aufruf und rechnet selbst nichts.
</box>

----

Letzte Aktualisierung: 2026-08-16 · alle Beispiele mit ''lyxc 1.0.21A'' übersetzt und ausgeführt; Produkt, Summe, ggT, Potenz und modulare Potenz gegen eine unabhängige Referenzrechnung geprüft.