PUBAO — Big Integer Library (C)

PUBAO (P.A.N.D.A.’s Unbounded Big Arithmetic Operations) is a C library for computing with integers larger than standard C integer types. It is intended for workloads such as cryptographic computations and other high-precision arithmetic where native integer widths are insufficient.

Overview

PUBAO represents a big integer as a structure containing:

  • a sign bit,
  • a word length (number of machine words),
  • a dynamically allocated array of words holding the magnitude.

The library includes arithmetic primitives and higher-level operations commonly used in cryptographic code paths (e.g., modular exponentiation and modular reduction).

Key Features

  • Big integer type BINT with dynamic memory management.
  • Core operations: addition/subtraction, multiplication (including Karatsuba), squaring, division, and utilities for bit/word handling.
  • Modular arithmetic support:
    • Modular exponentiation (left-to-right, right-to-left, Montgomery)
    • Barrett reduction (with optional precomputation)
    • Extended Euclidean Algorithm (EEA)
  • Built-in correctness and performance testing harness via Tests/measure.* and Makefile targets.

Project Structure

  • utils.h / utils.c: basic operations and the BINT definition.
  • arithmetic.h / arithmetic.c: higher-level arithmetic (mul/div/exp/mod reductions, etc.).
  • Tests/measure.h / Tests/measure.c: correctness + benchmarking helpers.
  • main.c: test entry point.

Build & Run (Testing)

Note: the current version expects you to modify main.c directly to select or configure tests.

Typical workflow:

make rebuild
make success        # correctness/accuracy workflow + visualization output
make speed          # benchmark workflow + visualization output
make speed-mul      # multiplication benchmarks
make speed-squ      # squaring benchmarks

Notes on Implementation

  • Uses dynamic allocation for the internal word array; callers should free objects using the library’s delete/free routine(s).
  • Supports positive/negative values via the sign field in BINT.

Authors

Ji Yong-Hyeon, Moon Ye-chan, Kim Ye-chan, Yoo Geun-oh