SBIL++ (Simple Big Integer Library in C++)

SBIL++ is a C++ library designed for arbitrary-precision integer arithmetic. It provides a BigInt class capable of handling integers far exceeding the limits of standard types like long long. This library is built using modern C++20 features, focusing on correctness, clarity, and ease of use — with high-performance algorithms and an optional cryptographic-safe build mode.

This project started as a guided learning exercise and aims to provide a robust foundation for applications requiring large integer mathematics.

Features

• Arbitrary Precision: Stores integers of virtually unlimited size.
• Core Arithmetic:
  • Addition (+, +=)
  • Subtraction (-, -=)
  • Multiplication (*, *=) — schoolbook + Karatsuba
  • Division and Modulo (/, /=, %, %=) — Knuth Algorithm D + Burnikel-Ziegler recursive
  • Modular exponentiation (mod_pow) — Montgomery (CIOS/SOS) for odd moduli, Barrett for even
• Comparison: Full set of comparison operators (==, !=, <, >, <=, >=).
• Sign Handling: Correctly manages positive and negative numbers.
• Construction:
  • From long long (explicit).
  • From std::string (explicit).
• Output: Stream insertion operator (<<) for easy printing via std::cout.
• Number theory: isPrime (Miller-Rabin), nextPrime, gcd, lcm, modInverse, sqrt, factorial.
• PRNG: pseudo_random (Mersenne Twister, NOT for crypto) and secure_random (/dev/urandom).
• Cryptographic-safe mode: build with -Dcrypto_safe=true to get constant-time mod_pow (Montgomery ladder), constant-time comparisons, and zeroing of all limb memory (SecureAllocator) — protection against timing attacks for secret data.
• Modern C++: Uses C++20, RAII (via std::vector), explicit constructors, and the Rule of Five.
• Tested: Includes a growing suite of unit tests using the Catch2 framework.

Building SBIL++

This project uses the Meson build system.

Dependencies

• A C++20 compliant compiler (e.g., GCC, Clang)
• Meson (>= 0.60)
• Ninja (or another Meson backend)
• Catch2 (>= 3.x) - Handled automatically via Meson Wrap or Nix

Build Instructions

1. Clone the Repository:

   git clone <your-repo-url>
   cd SBIL++

2. Configure with Meson: This command sets up the build directory (build) and detects dependencies. If using Meson Wrap, Catch2 will be downloaded automatically.

   meson setup build

   (Optional: For a release build, use meson setup build --buildtype=release)

3. Compile:

   meson compile -C build

4. Run Tests:

   meson test -C build

Cryptographic-safe build

To get constant-time operations (Montgomery ladder in mod_pow, full-scan comparisons) and zeroing of all limb memory, build with the crypto_safe option:

meson setup build-crypto -Dcrypto_safe=true
meson compile -C build-crypto
meson test -C build-crypto    # full suite must pass in BOTH modes

Scope limits: division, gcd, modInverse, and isPrime/nextPrime candidate rejection remain variable-time; constant-time mod_pow throws std::invalid_argument for even moduli. Keep exponents fixed-size in crypto use (the ladder iterates exponent.bitLength() times).

Building with Nix (Recommended for NixOS / Nix users)

A shell.nix file is provided for a reproducible development environment.

1. Enter the Nix Shell: Navigate to the project root and run:

   nix-shell

   (Or use direnv allow if you have direnv configured)

2. Build using Meson: Follow steps 2-4 from the standard build instructions above. The Nix environment provides all necessary dependencies.

Basic Usage

#include <iostream>
#include "sbilpp/BigInt.h" 


int main() {
    // Construction (Explicit)
    SBILPP::BigInt a("-1234567890123456789012345");
    SBILPP::BigInt b(9876543210);

    // Arithmetic
    SBILPP::BigInt sum = a + b;
    SBILPP::BigInt product = a * 100; 
    SBILPP::BigInt division = product / 7559;
    a += b;

    // Comparison
    if (a < b) {
        std::cout << "a is smaller than b" << std::endl;
    }

    // Output
    std::cout << "a = " << a << std::endl;
    std::cout << "b = " << b << std::endl;
    std::cout << "Sum = " << sum << std::endl;
    std::cout << "Product = " << product << std::endl;
    std::cout << "Division = " << division << std::endl;

    return 0;
}