text: // Copyright (c) 2009-2010 Satoshi Nakamoto
  // Copyright (c) 2009-2012 The Bitcoin developers
  // Copyright (c) 2017-2019 The BIOA3 developers
  // Distributed under the MIT/X11 software license, see the accompanying
  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  
  #include "bignum.h"
  
  CBigNum::CBigNum()
  {
      bn = BN_new();
  }
  
  CBigNum::CBigNum(const CBigNum& b)
  {
      bn = BN_new();
      if (!BN_copy(bn, b.bn))
      {
          BN_clear_free(bn);
          throw bignum_error("CBigNum::CBigNum(const CBigNum&) : BN_copy failed");
      }
  }
  
  CBigNum& CBigNum::operator=(const CBigNum& b)
  {
      if (!BN_copy(bn, b.bn))
          throw bignum_error("CBigNum::operator= : BN_copy failed");
      return (*this);
  }
  
  CBigNum::~CBigNum()
  {
      BN_clear_free(bn);
  }
  
  //CBigNum(char n) is not portable.  Use 'signed char' or 'unsigned char'.
  CBigNum::CBigNum(signed char n)        { bn = BN_new(); if (n >= 0) setulong(n); else setint64(n); }
  CBigNum::CBigNum(short n)              { bn = BN_new(); if (n >= 0) setulong(n); else setint64(n); }
  CBigNum::CBigNum(int n)                { bn = BN_new(); if (n >= 0) setulong(n); else setint64(n); }
  CBigNum::CBigNum(long n)               { bn = BN_new(); if (n >= 0) setulong(n); else setint64(n); }
  CBigNum::CBigNum(long long n)          { bn = BN_new(); setint64(n); }
  CBigNum::CBigNum(unsigned char n)      { bn = BN_new(); setulong(n); }
  CBigNum::CBigNum(unsigned short n)     { bn = BN_new(); setulong(n); }
  CBigNum::CBigNum(unsigned int n)       { bn = BN_new(); setulong(n); }
  CBigNum::CBigNum(unsigned long n)      { bn = BN_new(); setulong(n); }
  CBigNum::CBigNum(unsigned long long n) { bn = BN_new(); setuint64(n); }
  CBigNum::CBigNum(uint256 n)            { bn = BN_new(); setuint256(n); }
  
  CBigNum::CBigNum(const std::vector<unsigned char>& vch)
  {
      bn = BN_new();
      setvch(vch);
  }
  
  /** Generates a cryptographically secure random number between zero and range-1 (inclusive)
  * i.e. 0 <= returned number < range
  * @param range The upper bound on the number.
  * @return
  */
  CBigNum CBigNum::randBignum(const CBigNum& range)
  {
      CBigNum ret;
      if(!BN_rand_range(ret.bn, range.bn)){
          throw bignum_error("CBigNum:rand element : BN_rand_range failed");
      }
      return ret;
  }
  
  /** Generates a cryptographically secure random k-bit number
  * @param k The bit length of the number.
  * @return
  */
  CBigNum CBigNum::randKBitBignum(const uint32_t k)
  {
      CBigNum ret;
      if(!BN_rand(ret.bn, k, -1, 0)){
          throw bignum_error("CBigNum:rand element : BN_rand failed");
      }
      return ret;
  }
  
  /**Returns the size in bits of the underlying bignum.
   *
   * @return the size
   */
  int CBigNum::bitSize() const
  {
      return  BN_num_bits(bn);
  }
  
  void CBigNum::setulong(unsigned long n)
  {
      if (!BN_set_word(bn, n))
          throw bignum_error("CBigNum conversion from unsigned long : BN_set_word failed");
  }
  
  unsigned long CBigNum::getulong() const
  {
      return BN_get_word(bn);
  }
  
  unsigned int CBigNum::getuint() const
  {
      return BN_get_word(bn);
  }
  
  int CBigNum::getint() const
  {
      unsigned long n = BN_get_word(bn);
      if (!BN_is_negative(bn))
          return (n > (unsigned long)std::numeric_limits<int>::max() ? std::numeric_limits<int>::max() : n);
      else
          return (n > (unsigned long)std::numeric_limits<int>::max() ? std::numeric_limits<int>::min() : -(int)n);
  }
  
  void CBigNum::setint64(int64_t sn)
  {
      unsigned char pch[sizeof(sn) + 6];
      unsigned char* p = pch + 4;
      bool fNegative;
      uint64_t n;
  
      if (sn < (int64_t)0)
      {
          // Since the minimum signed integer cannot be represented as positive so long as its type is signed,
          // and it's not well-defined what happens if you make it unsigned before negating it,
          // we instead increment the negative integer by 1, convert it, then increment the (now positive) unsigned integer by 1 to compensate
          n = -(sn + 1);
          ++n;
          fNegative = true;
      } else {
          n = sn;
          fNegative = false;
      }
  
      bool fLeadingZeroes = true;
      for (int i = 0; i < 8; i++)
      {
          unsigned char c = (n >> 56) & 0xff;
          n <<= 8;
          if (fLeadingZeroes)
          {
              if (c == 0)
                  continue;
              if (c & 0x80)
                  *p++ = (fNegative ? 0x80 : 0);
              else if (fNegative)
                  c |= 0x80;
              fLeadingZeroes = false;
          }
          *p++ = c;
      }
      unsigned int nSize = p - (pch + 4);
      pch[0] = (nSize >> 24) & 0xff;
      pch[1] = (nSize >> 16) & 0xff;
      pch[2] = (nSize >> 8) & 0xff;
      pch[3] = (nSize) & 0xff;
      BN_mpi2bn(pch, p - pch, bn);
  }
  
  void CBigNum::setuint64(uint64_t n)
  {
      unsigned char pch[sizeof(n) + 6];
      unsigned char* p = pch + 4;
      bool fLeadingZeroes = true;
      for (int i = 0; i < 8; i++)
      {
          unsigned char c = (n >> 56) & 0xff;
          n <<= 8;
          if (fLeadingZeroes)
          {
              if (c == 0)
                  continue;
              if (c & 0x80)
                  *p++ = 0;
              fLeadingZeroes = false;
          }
          *p++ = c;
      }
      unsigned int nSize = p - (pch + 4);
      pch[0] = (nSize >> 24) & 0xff;
      pch[1] = (nSize >> 16) & 0xff;
      pch[2] = (nSize >> 8) & 0xff;
      pch[3] = (nSize) & 0xff;
      BN_mpi2bn(pch, p - pch, bn);
  }
  
  void CBigNum::setuint256(uint256 n)
  {
      unsigned char pch[sizeof(n) + 6];
      unsigned char* p = pch + 4;
      bool fLeadingZeroes = true;
      unsigned char* pbegin = (unsigned char*)&n;
      unsigned char* psrc = pbegin + sizeof(n);
      while (psrc != pbegin)
      {
          unsigned char c = *(--psrc);
          if (fLeadingZeroes)
          {
              if (c == 0)
                  continue;
              if (c & 0x80)
                  *p++ = 0;
              fLeadingZeroes = false;
          }
          *p++ = c;
      }
      unsigned int nSize = p - (pch + 4);
      pch[0] = (nSize >> 24) & 0xff;
      pch[1] = (nSize >> 16) & 0xff;
      pch[2] = (nSize >> 8) & 0xff;
      pch[3] = (nSize >> 0) & 0xff;
      BN_mpi2bn(pch, p - pch, bn);
  }
  
  uint256 CBigNum::getuint256() const
  {
      if(bitSize() > 256) {
              throw std::range_error("cannot convert to uint256, bignum longer than 256 bits");
      }
      unsigned int nSize = BN_bn2mpi(bn, NULL);
      if (nSize < 4)
          return 0;
      std::vector<unsigned char> vch(nSize);
      BN_bn2mpi(bn, &vch[0]);
      if (vch.size() > 4)
          vch[4] &= 0x7f;
      uint256 n = 0;
      for (unsigned int i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
          ((unsigned char*)&n)[i] = vch[j];
      return n;
  }
  
  void CBigNum::setvch(const std::vector<unsigned char>& vch)
  {
      std::vector<unsigned char> vch2(vch.size() + 4);
      unsigned int nSize = vch.size();
      // BIGNUM's byte stream format expects 4 bytes of
      // big endian size data info at the front
      vch2[0] = (nSize >> 24) & 0xff;
      vch2[1] = (nSize >> 16) & 0xff;
      vch2[2] = (nSize >> 8) & 0xff;
      vch2[3] = (nSize >> 0) & 0xff;
      // swap data to big endian
      reverse_copy(vch.begin(), vch.end(), vch2.begin() + 4);
      BN_mpi2bn(&vch2[0], vch2.size(), bn);
  }
  
  std::vector<unsigned char> CBigNum::getvch() const
  {
      unsigned int nSize = BN_bn2mpi(bn, NULL);
      if (nSize <= 4)
          return std::vector<unsigned char>();
      std::vector<unsigned char> vch(nSize);
      BN_bn2mpi(bn, &vch[0]);
      vch.erase(vch.begin(), vch.begin() + 4);
      reverse(vch.begin(), vch.end());
      return vch;
  }
  
  void CBigNum::SetDec(const std::string& str)
  {
      BN_dec2bn(&bn, str.c_str());
  }
  
  bool CBigNum::SetHexBool(const std::string& str)
  {
      // skip 0x
      const char* psz = str.c_str();
      while (isspace(*psz))
          psz++;
      bool fNegative = false;
      if (*psz == '-')
      {
          fNegative = true;
          psz++;
      }
      if (psz[0] == '0' && tolower(psz[1]) == 'x')
          psz += 2;
      while (isspace(*psz))
          psz++;
  
      // hex string to bignum
      static const signed char phexdigit[256] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0 };
      *this = 0;
      while (isxdigit(*psz))
      {
          *this <<= 4;
          int n = phexdigit[(unsigned char)*psz++];
          *this += n;
      }
      if (fNegative)
          *this = 0 - *this;
  
      return true;
  }
  
  
  std::string CBigNum::ToString(int nBase) const
  {
      CAutoBN_CTX pctx;
      CBigNum bnBase = nBase;
      CBigNum bn0 = 0;
      CBigNum locBn = *this;
      std::string str;
      BN_set_negative(locBn.bn, false);
      CBigNum dv;
      CBigNum rem;
      if (BN_cmp(locBn.bn, bn0.bn) == 0)
          return "0";
      while (BN_cmp(locBn.bn, bn0.bn) > 0)
      {
          if (!BN_div(dv.bn, rem.bn, locBn.bn, bnBase.bn, pctx))
              throw bignum_error("CBigNum::ToString() : BN_div failed");
          locBn = dv;
          unsigned int c = rem.getulong();
          str += "0123456789abcdef"[c];
      }
      if (BN_is_negative(bn))
          str += "-";
      reverse(str.begin(), str.end());
      return str;
  }
  
  /**
   * exponentiation this^e
   * @param e the exponent
   * @return
   */
  CBigNum CBigNum::pow(const CBigNum& e) const
  {
      CAutoBN_CTX pctx;
      CBigNum ret;
      if (!BN_exp(ret.bn, bn, e.bn, pctx))
          throw bignum_error("CBigNum::pow : BN_exp failed");
      return ret;
  }
  
  /**
   * modular multiplication: (this * b) mod m
   * @param b operand
   * @param m modulus
   */
  CBigNum CBigNum::mul_mod(const CBigNum& b, const CBigNum& m) const
  {
      CAutoBN_CTX pctx;
      CBigNum ret;
      if (!BN_mod_mul(ret.bn, bn, b.bn, m.bn, pctx))
              throw bignum_error("CBigNum::mul_mod : BN_mod_mul failed");
  
      return ret;
  }
  
  /**
   * modular exponentiation: this^e mod n
   * @param e exponent
   * @param m modulus
   */
  CBigNum CBigNum::pow_mod(const CBigNum& e, const CBigNum& m) const
  {
      CAutoBN_CTX pctx;
      CBigNum ret;
      if( e < 0){
          // g^-x = (g^-1)^x
          CBigNum inv = this->inverse(m);
          CBigNum posE = e * -1;
          if (!BN_mod_exp(ret.bn, inv.bn, posE.bn, m.bn, pctx))
              throw bignum_error("CBigNum::pow_mod: BN_mod_exp failed on negative exponent");
      }else
          if (!BN_mod_exp(ret.bn, bn, e.bn, m.bn, pctx))
              throw bignum_error("CBigNum::pow_mod : BN_mod_exp failed");
  
      return ret;
  }
  
  /**
  * Calculates the inverse of this element mod m.
  * i.e. i such this*i = 1 mod m
  * @param m the modu
  * @return the inverse
  */
  CBigNum CBigNum::inverse(const CBigNum& m) const
  {
      CAutoBN_CTX pctx;
      CBigNum ret;
      if (!BN_mod_inverse(ret.bn, bn, m.bn, pctx))
          throw bignum_error("CBigNum::inverse*= :BN_mod_inverse");
      return ret;
  }
  
  /**
   * Generates a random (safe) prime of numBits bits
   * @param numBits the number of bits
   * @param safe true for a safe prime
   * @return the prime
   */
  CBigNum CBigNum::generatePrime(const unsigned int numBits, bool safe)
  {
      CBigNum ret;
      if(!BN_generate_prime_ex(ret.bn, numBits, (safe == true), NULL, NULL, NULL))
          throw bignum_error("CBigNum::generatePrime*= :BN_generate_prime_ex");
      return ret;
  }
  
  /**
   * Calculates the greatest common divisor (GCD) of two numbers.
   * @param m the second element
   * @return the GCD
   */
  CBigNum CBigNum::gcd( const CBigNum& b) const
  {
      CAutoBN_CTX pctx;
      CBigNum ret;
      if (!BN_gcd(ret.bn, bn, b.bn, pctx))
          throw bignum_error("CBigNum::gcd*= :BN_gcd");
      return ret;
  }
  
  /**
  * Miller-Rabin primality test on this element
  * @param checks: optional, the number of Miller-Rabin tests to run
  *                          default causes error rate of 2^-80.
  * @return true if prime
  */
  bool CBigNum::isPrime(const int checks) const
  {
      CAutoBN_CTX pctx;
      int ret = BN_is_prime_ex(bn, checks, pctx, NULL);
      if(ret < 0){
          throw bignum_error("CBigNum::isPrime :BN_is_prime");
      }
      return ret;
  }
  
  bool CBigNum::isOne() const
  {
      return BN_is_one(bn);
  }
  
  bool CBigNum::operator!() const
  {
      return BN_is_zero(bn);
  }
  
  CBigNum& CBigNum::operator+=(const CBigNum& b)
  {
      if (!BN_add(bn, bn, b.bn))
          throw bignum_error("CBigNum::operator+= : BN_add failed");
      return *this;
  }
  
  CBigNum& CBigNum::operator-=(const CBigNum& b)
  {
      if (!BN_sub(bn, bn, b.bn))
          throw bignum_error("CBigNum::operator-= : BN_sub failed");
      return *this;
  }
  
  CBigNum& CBigNum::operator*=(const CBigNum& b)
  {
      CAutoBN_CTX pctx;
      if (!BN_mul(bn, bn, b.bn, pctx))
          throw bignum_error("CBigNum::operator*= : BN_mul failed");
      return *this;
  }
  
  CBigNum& CBigNum::operator<<=(unsigned int shift)
  {
      if (!BN_lshift(bn, bn, shift))
          throw bignum_error("CBigNum:operator<<= : BN_lshift failed");
      return *this;
  }
  
  CBigNum& CBigNum::operator>>=(unsigned int shift)
  {
      // Note: BN_rshift segfaults on 64-bit if 2^shift is greater than the number
      //   if built on ubuntu 9.04 or 9.10, probably depends on version of OpenSSL
      CBigNum a = 1;
      a <<= shift;
      if (BN_cmp(a.bn, bn) > 0)
      {
          bn = 0;
          return *this;
      }
  
      if (!BN_rshift(bn, bn, shift))
          throw bignum_error("CBigNum:operator>>= : BN_rshift failed");
      return *this;
  }
  
  
  CBigNum& CBigNum::operator++()
  {
      // prefix operator
      if (!BN_add(bn, bn, BN_value_one()))
          throw bignum_error("CBigNum::operator++ : BN_add failed");
      return *this;
  }
  
  CBigNum& CBigNum::operator--()
  {
      // prefix operator
      CBigNum r;
      if (!BN_sub(r.bn, bn, BN_value_one()))
          throw bignum_error("CBigNum::operator-- : BN_sub failed");
      bn = r.bn;
      return *this;
  }
  