bignum.h raw

   1  // Copyright (c) 2025 The Limenka developers
   2  // Distributed under the MIT software license, see the accompanying
   3  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4  
   5  #ifndef LIMENKA_CRYPTO_BIGNUM_H
   6  #define LIMENKA_CRYPTO_BIGNUM_H
   7  
   8  #include <cstddef>
   9  #include <cstdint>
  10  #include <memory>
  11  #include <span>
  12  #include <string>
  13  #include <vector>
  14  
  15  class BigNum {
  16  public:
  17      BigNum() { m_limbs = {0}; }
  18      explicit BigNum(const std::vector<uint8_t>& bytes, bool big_endian = true);
  19      explicit BigNum(uint32_t val);
  20  
  21      std::vector<uint8_t> to_bytes(size_t width = 0) const;
  22  
  23      bool is_zero() const;
  24      bool is_one() const;
  25      bool is_even() const { return (m_limbs[0] & 1) == 0; }
  26      size_t num_limbs() const { return m_limbs.size(); }
  27      uint32_t limb(size_t i) const { return i < m_limbs.size() ? m_limbs[i] : 0; }
  28      size_t bit_length() const;
  29  
  30      int compare(const BigNum& other) const;
  31      bool operator==(const BigNum& other) const { return compare(other) == 0; }
  32      bool operator!=(const BigNum& other) const { return compare(other) != 0; }
  33  
  34      BigNum& operator+=(const BigNum& other);
  35      BigNum& operator-=(const BigNum& other);
  36      BigNum& operator*=(const BigNum& other);
  37  
  38      BigNum operator+(const BigNum& other) const { BigNum r(*this); r += other; return r; }
  39      BigNum operator-(const BigNum& other) const { BigNum r(*this); r -= other; return r; }
  40      BigNum operator*(const BigNum& other) const { BigNum r(*this); r *= other; return r; }
  41      BigNum operator%(const BigNum& other) const { BigNum r(*this); r %= other; return r; }
  42  
  43      BigNum& operator%=(const BigNum& mod);
  44  
  45      /** Sequential squaring: sqr = x, then sqr = sqr*sqr mod m, D times.
  46       *  Stores every k-th intermediate (k=16) for proof reconstruction.
  47       *  intermediates[i] = x^(2^(i*k)) mod m.  intermediates[0] = x^(2^0) = x.
  48       */
  49      static BigNum sqr_chain(const BigNum& base, uint32_t D, const BigNum& m,
  50                              std::vector<BigNum>* intermediates = nullptr);
  51  
  52      /** Modular exponentiation: base^exp mod m (square-and-multiply). */
  53      static BigNum mod_pow(BigNum base, BigNum exp, const BigNum& m);
  54  
  55      /** Montgomery modular multiplication: (a * b * R^-1) mod m.  m must be odd. */
  56      static BigNum mont_mul(const BigNum& a, const BigNum& b,
  57                             const BigNum& m, uint32_t m_prime);
  58  
  59      /** Montgomery precomputation: m_prime such that m * m_prime ≡ -1 (mod 2^32). */
  60      static uint32_t mont_mp(const BigNum& m);
  61  
  62      /** Montgomery precomputation: R^2 mod m where R = 2^(32 * m.num_limbs()). */
  63      static BigNum mont_r2(const BigNum& m);
  64  
  65      /** Binary GCD. */
  66      static BigNum gcd(const BigNum& a, const BigNum& b);
  67  
  68      /** Division: compute quotient and remainder.  num / den = q, num % den = r. */
  69      static void div_rem(const BigNum& num, const BigNum& den,
  70                          BigNum& quot, BigNum& rem);
  71  
  72      // Allow hash functions to access internal representation
  73      const std::vector<uint32_t>& limbs() const { return m_limbs; }
  74  
  75  private:
  76      std::vector<uint32_t> m_limbs;
  77      void trim();
  78  };
  79  
  80  std::string BigNumToHex(const BigNum& n);
  81  
  82  #endif // LIMENKA_CRYPTO_BIGNUM_H
  83