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.

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

import std.bignum;

Schicht 2, hängt an std.i128 und 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:

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

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

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 std.i128 ist der richtige Vergleich.

Rechnen

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;
}

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

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

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

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 std.sat
128 Bit	std.i128
beliebig groß	`std.bignum`
Restklassen bis 2⁶²	std.modmath
Primzahltest beliebiger Größe	std.prime

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

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.