ddn.bigint

BigInt Implementation for Cryptography.

This module provides a multiprecision integer implementation designed to replace std.bigint in cryptographic contexts. It focuses on control over memory and algorithmic correctness.

alias powmod
struct BigInt
fn absUnsign addLimbsLow addLimbsWithCarry blockRedc copyLimbs divMod invModPowerOf2 maskBits mod2k powMod powMod2k powModOdd redcDispatch toDecimalString toHex

Types 2

structBigInt

Arbitrary precision integer. Stores data as an array of 64-bit words (limbs) in Little Endian order.

Fields
ulong[] limbs
bool sign
Methods
void trim() pure nothrow @nogc @safe
bool isZero() const pure nothrow @nogc @safe
BigInt dup() const pure @safe
BigInt abs() const pure @safe
size_t countTrailingZeros() const pure nothrow @nogc @safe
BigInt opOpAssign(string op)(auto ref const BigInt rhs) ref pure @safe
BigInt opOpAssign(string op, T)(T exp) if (op == "^^" && isIntegral!T) ref pure @safePower assignment operator for BigInt ^^= integral exponent.
BigInt opOpAssign(string op, T)(T rhs) if (isIntegral!T && op != "^^") ref pure @safe
BigInt opAssign(T)(T x) if (isIntegral!T) ref pure nothrow @safeAssignment operator from integral types.
BigInt opBinary(string op)(auto ref const BigInt rhs) const pure @safe
BigInt opBinary(string op, T)(T exp) if (op == "^^" && isIntegral!T) const pure @safePower operator for BigInt ^^ integral exponent.
BigInt opBinary(string op, T)(T rhs) if (isIntegral!T && op != "^^") const
BigInt opBinary(string op)(size_t shift) if (op == "<<" || op == ">>") const pure @safe
BigInt opOpAssign(string op)(size_t shift) if (op == "<<" || op == ">>") ref pure @safe
int opCmp()(auto ref const BigInt rhs) const pure nothrow @nogc @safe
int opCmp(T)(T rhs) if (isIntegral!T) const pure @safe
bool opEquals()(auto ref const BigInt rhs) const pure nothrow @nogc @safe
bool opEquals(T)(T rhs) if (isIntegral!T) const pure @safe
int opCmp(T)(const T y) if (isFloatingPoint!T) const nothrow @nogc @safeComparison with floating-point types
bool opEquals(T)(const T y) if (isFloatingPoint!T) const pure nothrow @nogc @safeEquality comparison with floating-point types
size_t toHash() const @safe pure nothrow @nogcComputes a hash value for use in associative arrays.
T toInt(T)() if (isIntegral!T) const pure nothrow @nogc @safe
long toLong() const pure @safeConverts BigInt to long.
T getDigit(T = ulong)(size_t n) const pure nothrow @nogc @safeReturns the n-th digit (limb) of the BigInt magnitude.
size_t ulongLength() @property const pure nothrow @nogc @safeReturns the number of 64-bit limbs (digits) in the BigInt.
size_t uintLength() @property const pure nothrow @nogc @safeReturns the number of 32-bit limbs (digits) in the BigInt.
BigInt opUnary(string op)() if (op == "+" || op == "-" || op == "~") const pure @safeImplements unary operators +, -, ~ for BigInt.
BigInt opUnary(string op)() if (op == "++" || op == "--") ref pure @safeImplements pre-increment (++) and pre-decrement (--) operators for BigInt.
T opCast(T : bool)() const pure nothrow @nogc @safeCasts BigInt to bool.
T opCast(T)() if (isIntegral!T) const pure @safeCasts BigInt to integral types (int, long, ulong, etc.).
T opCast(T)() if (isFloatingPoint!T) const @safe nothrow @nogcCasts BigInt to floating-point types (float, double, real).
BigInt opBinaryRight(string op, T)(T y) if ((op == "+" || op == "*" || op == "|" || op == "&" || op == "^") && isIntegral!T) const pure @safeImplements right-hand commutative operators (+, *, |, &, ^).
BigInt opBinaryRight(string op, T)(T y) if (op == "-" && isIntegral!T) const pure @safeImplements right-hand subtraction operator.
T opBinaryRight(string op, T)(T y) if ((op == "/" || op == "%") && isIntegral!T) const pure @safeImplements right-hand division and modulus operators.
int cmpAbs(ref const BigInt rhs) const pure nothrow @nogc @safe
private BigInt add(ref const BigInt a, ref const BigInt b) pure @safe
private BigInt sub(ref const BigInt a, ref const BigInt b) pure @safe
private ulong[] addLimbs(const(ulong)[] a, const(ulong)[] b) pure @safe
private ulong[] addLimbs(const(ulong)[] a, const(ulong)[] b, ulong[] res) pure nothrow @nogc @trusted
private ulong[] subLimbs(const(ulong)[] a, const(ulong)[] b) pure @trusted
private BigInt mul(ref const BigInt a, ref const BigInt b) pure @safe
private BigInt sqr(ref const BigInt a) pure @safe
private BigInt bitwiseOr(ref const BigInt a, ref const BigInt b) pure @safePerforms bitwise OR operation on two BigInt values.
private BigInt bitwiseAnd(ref const BigInt a, ref const BigInt b) pure @safePerforms bitwise AND operation on two BigInt values.
private BigInt bitwiseXor(ref const BigInt a, ref const BigInt b) pure @safePerforms bitwise XOR operation on two BigInt values.
private BigInt pow(ref const BigInt base, ulong exp) pure @safeRaises a BigInt to an integral power using exponentiation by squaring.
private ulong[] mulLimbs(const(ulong)[] a, const(ulong)[] b) pure @safe
private void mulLimbs(const(ulong)[] a, const(ulong)[] b, ulong[] res, ulong[] scratch = null) pure @safe
private void mulSchoolbook(const(ulong)[] a, const(ulong)[] b, ulong[] res) pure nothrow @nogc @safe
private void mulKaratsuba(const(ulong)[] a, const(ulong)[] b, ulong[] res, ulong[] scratch) pure @safe
private void subLimbsInPlace(ulong[] dest, const(ulong)[] src) pure nothrow @nogc @safe
private void addAt(ulong[] dest, const(ulong)[] src, size_t offset) pure nothrow @nogc @safe
private ulong[] sqrLimbs(const(ulong)[] a) pure @safe
private void sqrLimbs(const(ulong)[] a, ulong[] res, ulong[] scratch = null) pure @safe
private void sqrSchoolbook(const(ulong)[] a, ulong[] res) pure nothrow @nogc @safe
private void sqrKaratsuba(const(ulong)[] a, ulong[] res, ulong[] scratch) pure @safe
private ulong invMod64(ulong n) pure nothrow @nogc @safe
private void redc(ulong[] T, const(ulong)[] mod, ulong modPrime, ulong[] res) pure nothrow @nogc @trustedMontgomery Reduction: res = T * R^-1 mod N.
private int cmpLimbs(const(ulong)[] a, const(ulong)[] b) pure nothrow @nogc @safe
private ulong mulAdd(ulong[] dst, const(ulong)[] src, ulong mul) pure nothrow @nogc @trusted
private ulong mulSub(ulong[] dst, const(ulong)[] src, ulong mul, out bool extraBorrow) pure nothrow @nogc @trusted
private void shiftLeftLimbs(const(ulong)[] src, ulong[] dest, size_t shift) pure nothrow @nogc @safe
private void shiftRightLimbs(const(ulong)[] src, ulong[] dest, size_t shift) pure nothrow @nogc @safe
DivResult divMod(ref const BigInt n, ref const BigInt d) pure @safe
private void mul128(ulong a, ulong b, out ulong hi, out ulong lo) pure nothrow @nogc @safe
ulong div128(ulong u1, ulong u0, ulong v, out ulong r) pure nothrow @nogc @trusted
private ulong div128Unchecked(ulong u1, ulong u0, ulong v, out ulong r) pure nothrow @nogc @trusted
private ulong mul128(ulong u, ulong v, out ulong hi) pure nothrow @nogc @trusted
size_t bitLength() const pure nothrow @nogc @safe
bool testBit(size_t n) const pure nothrow @nogc @safe
void setBit(size_t n) pure @safe
BigInt shiftLeft(size_t shift) const pure @safe
BigInt shiftRight(size_t shift) const pure @safe
int hexDigit(char c) pure nothrow @nogc @safe
int decDigit(char c) pure nothrow @nogc @safe
string toString() const pure @safeConverts BigInt to string (decimal by default).
string toDecimalString() const pure @safeConverts BigInt to decimal string.
string toHexString() const pure @safeConverts BigInt to hexadecimal string.
void toString(Writer)(scope ref Writer sink, scope const ref FormatSpec!char f) constConverts BigInt to string with format specifier.
void toString(Writer)(scope ref Writer sink, string formatString) constConverts BigInt to string with format string.
Constructors
this(T x)
this(string s)
this(bool isNegative, Range magnitude)Constructs a BigInt from a sign and magnitude.
this(Range s)Constructs a BigInt from a bidirectional range of characters.
Nested Templates
DivResult
aliaspowmod = powMod

Alias for compatibility with std.bigint (lowercase version)

Functions 15

fnstring toDecimalString(const BigInt x) pure @safeConverts a BigInt to its decimal string representation.
fnstring toHex(const BigInt x) pure @safeConverts a BigInt to its hexadecimal string representation with underscores.
fnvoid divMod(const BigInt dividend, const BigInt divisor, out BigInt quotient, out BigInt remainder) pure @safePerforms division with remainder on two BigInt values.
fnBigInt powMod(BigInt base, BigInt exp, BigInt mod)Computes modular exponentiation: base^exp mod mod.
fnauto absUnsign(T)(T x) if (isIntegral!T)Returns the absolute value of an integral type as an unsigned type.
fnBigInt powModOdd(BigInt base, BigInt exp, BigInt mod)Computes modular exponentiation for odd modulus using sliding window binary exponentiation with regular modular reduction.
private fnvoid redcDispatch(ulong[] T, const(ulong)[] mod, ulong nPrime, const(ulong)[] nPrimeBig, ulong[] res, ulong[] scratch) pure @safe
private fnvoid blockRedc(ulong[] T, const(ulong)[] mod, const(ulong)[] nPrimeBig, ulong[] res, ulong[] scratch) pure @safe
private fnulong addLimbsLow(const(ulong)[] a, const(ulong)[] b) pure nothrow @nogc @safe
private fnulong addLimbsWithCarry(const(ulong)[] a, const(ulong)[] b, ulong[] res, ulong carryIn) pure nothrow @nogc @safe
fnBigInt powMod2k(BigInt base, BigInt exp, size_t k) pure @safeComputes modular exponentiation modulo a power of 2: base^exp mod 2^k.
fnBigInt invModPowerOf2(BigInt n, size_t k) pure @safeComputes the modular inverse of n modulo a power of 2: n^-1 mod 2^k.
fnBigInt mod2k(BigInt n, size_t k) pure @safeComputes n mod 2^k (reduction modulo a power of 2).
fnBigInt maskBits(BigInt n, size_t k) pure @safeMasks the lower k bits of a BigInt (computes abs(n) & ((1<<k)-1)).
private fnvoid copyLimbs(ulong[] dest, const(ulong)[] src) pure nothrow @nogc @safe