bignum.cpp

“网络安全技术实践与代码详解”实例代码

         break;
      case 7:
         Result[r] = '7';
         break;
      case 8:
         Result[r] = '8';
         break;
      case 9:
         Result[r] = '9';
         break;
      case 10:
         Result[r] = 'A';
         break;
      case 11:
         Result[r] = 'B';
         break;
      case 12:
         Result[r] = 'C';
         break;
      case 13:
         Result[r] = 'D';
         break;
      case 14:
         Result[r] = 'E';
         break;
      case 15:
         Result[r] = 'F';
         break;
      default:
         Result[r] = '!';
         break;
      }
   }

   Result[nOutSize] = '\0';
   return Result;
}



CBigNum &CBigNum::operator-=(const CBigNum &rhs)
{
   unsigned int nPos;
   unsigned int nBorrow;

   for (nPos=0; nPos<m_nSize; nPos++)
   {
      if (nPos < rhs.m_nSize)
      {
         if (m_arVal[nPos] < rhs.m_arVal[nPos])
         {
            for (nBorrow=nPos+1; nBorrow < m_nSize; nBorrow++)
            {
               if (m_arVal[nBorrow]>0)
               {
                  m_arVal[nBorrow]--;
                  m_arVal[nPos] += (1<<16);
                  break;
               }
               else
               {
                  m_arVal[nBorrow] = 0xFFFF;
               }
            }
         }
         m_arVal[nPos] -= rhs.m_arVal[nPos];
      }
   }
   
   return *this;
}

CBigNum &CBigNum::operator-=(const unsigned int rhs)
{
   unsigned int nBorrow;

   if (m_nSize > 0)
   {
      if (m_arVal[0] < rhs)
      {
         for (nBorrow = 1; nBorrow < m_nSize; nBorrow++)
         {
            if (m_arVal[nBorrow]>0)
            {
               m_arVal[nBorrow]--;
               m_arVal[0] += 1<<16;
               break;
            }
            else
            {
               m_arVal[nBorrow] = 0xFFFF;
            }
         }
      }
      m_arVal[0] -= rhs;
   }
   return *this;
}

CBigNum CBigNum::operator/(const CBigNum &rhs) const
{
   CBigNum result(rhs);
   CBigNum numer;
   CBigNum denom;
   CBigNum placeval;
   unsigned int nMag=0;

   if (rhs==0U) return result;

   while (result < *this)
      result<<=16, nMag+=16;

   if (result==*this)
   {
      return CBigNum(1)<<nMag;
   }

   while ((result > *this) && (nMag))
      result>>=1, nMag--;

   numer = *this;
   denom = result;
   result = 0U;

   for (placeval = CBigNum(1)<<nMag; nMag; placeval>>=1, nMag--)
   {
      if (numer >= denom)
      {
         result |= placeval;
         numer-=denom;
      }
      denom>>=1;
   }

   result.m_arVal[0] |= ((numer >= denom)?1:0);

   return result;
}

CBigNum &CBigNum::operator/=(const CBigNum &rhs)
{
   return *this = *this / rhs;
}

CBigNum CBigNum::operator/(const unsigned int rhs) const
{
   return *this / CBigNum(rhs);
}

CBigNum &CBigNum::operator/=(const unsigned int rhs)
{
   return *this = *this / rhs;
}

CBigNum CBigNum::operator%(const CBigNum &rhs) const
{
   CBigNum result(rhs);
   CBigNum numer;
   CBigNum denom;
   CBigNum placeval;
   unsigned int nMag=0;

   if (rhs==0U) return result;

   while (result < *this)
      result<<=16, nMag+=16;

   if (result==*this)
      return CBigNum(0U);

   while ((result > *this) && (nMag))
      result>>=1, nMag--;

   numer = *this;
   denom = result;
   result = 0U;

   for (placeval = CBigNum(1)<<nMag; nMag; placeval>>=1, nMag--)
   {
      if (numer >= denom)
      {
         result |= placeval;
         numer-=denom;
      }
      denom>>=1;
   }

   if (numer >= denom)
   {
      result.m_arVal[0] |= 1;
      numer -= denom;
   }

   return numer;
}

unsigned int CBigNum::operator%(const unsigned int rhs) const
{
   return (*this % CBigNum(rhs)).m_arVal[0];
}

CBigNum &CBigNum::operator%=(const CBigNum &rhs)
{
   return *this = *this % rhs;
}

unsigned int CBigNum::operator%=(const unsigned int rhs)
{
   *this = *this % rhs; 
   return this->m_arVal[0];
}

bool CBigNum::operator<(const CBigNum &rhs) const
{
   unsigned int nIdx;
   unsigned int nMaxSize;

   if (rhs.m_nSize > m_nSize)
      nMaxSize = rhs.m_nSize;
   else
      nMaxSize = m_nSize;

   for (nIdx = nMaxSize-1; nIdx != 0xFFFFFFFF; nIdx--)
   {
      if (nIdx < rhs.m_nSize)
      {
         if (nIdx < m_nSize)
         {
            if (rhs.m_arVal[nIdx] == m_arVal[nIdx])
               continue;
            return  m_arVal[nIdx] < rhs.m_arVal[nIdx];
         }
         else
            if (rhs.m_arVal[nIdx] != 0)
               return true;
      }
      else
         if (m_arVal[nIdx] != 0)
            return false;
   }

   return false;
}

bool CBigNum::operator<=(const CBigNum &rhs) const
{
   unsigned int nIdx;
   unsigned int nMaxSize;

   if (rhs.m_nSize > m_nSize)
      nMaxSize = rhs.m_nSize;
   else
      nMaxSize = m_nSize;

   for (nIdx = nMaxSize-1; nIdx != 0xFFFFFFFF; nIdx--)
   {
      if (nIdx < rhs.m_nSize)
      {
         if (nIdx < m_nSize)
         {
            if (rhs.m_arVal[nIdx] == m_arVal[nIdx])
               continue;
            return  m_arVal[nIdx] < rhs.m_arVal[nIdx];
         }
         else
            if (rhs.m_arVal[nIdx] != 0)
               return true;
      }
      else
         if (m_arVal[nIdx] != 0)
            return false;
   }

   return true;
}

bool CBigNum::operator==(const CBigNum &rhs) const
{
   unsigned int nIdx;
   unsigned int nMaxSize;

   if (rhs.m_nSize > m_nSize)
      nMaxSize = rhs.m_nSize;
   else
      nMaxSize = m_nSize;

   nIdx = nMaxSize-1;
   if (nIdx >=0)
   {
      do
      {
         if (nIdx < rhs.m_nSize)
         {
            if (nIdx < m_nSize)
            {
               if (rhs.m_arVal[nIdx] != m_arVal[nIdx])
                  return false;
            }
            else
               if (rhs.m_arVal[nIdx] != 0)
                  return false;
         }
         else
            if (m_arVal[nIdx] != 0)
               return false;
      } while (nIdx-- > 0);
   }
   return true;
}

bool CBigNum::operator!=(const CBigNum &rhs) const
{
   return !(operator==(rhs));
}

bool CBigNum::operator>(const CBigNum &rhs) const
{
   return !(*this <= rhs);
}

bool CBigNum::operator>=(const CBigNum &rhs) const
{
   return !(*this < rhs);
}

bool CBigNum::operator<(const unsigned int rhs) const
{
   int nIdx;

   switch(m_nSize)
   {
   case 0:
      return rhs > 0;
   case 1:
      return m_arVal[0] < rhs;
   case 2:
      return ((m_arVal[1] << 16) | m_arVal[0]) < rhs;
   default:
      for (nIdx = m_nSize-1; nIdx >= 0; nIdx--)
      {
         if (m_arVal[nIdx] != 0)
         {
            switch(nIdx)
            {
            case 0:
               return m_arVal[0] < rhs;
            case 1:
               return ((m_arVal[1] << 16) | m_arVal[0]) < rhs;
            default:
               return false;
            }
         }
      }
   }
   return false;
}

bool CBigNum::operator<=(const unsigned int rhs) const
{
   int nIdx;

   switch(m_nSize)
   {
   case 0:
      return rhs >= 0;
   case 1:
      return m_arVal[0] <= rhs;
   case 2:
      return ((m_arVal[1] << 16) | m_arVal[0]) <= rhs;
   default:
      for (nIdx = m_nSize-1; nIdx >= 0; nIdx--)
      {
         if (m_arVal[nIdx] != 0)
         {
            switch(nIdx)
            {
            case 0:
               return m_arVal[0] <= rhs;
            case 1:
               return ((m_arVal[1] << 16) | m_arVal[0]) <= rhs;
            default:
               return false;
            }
         }
      }
   }
   
   return true;
}

bool CBigNum::operator>(const unsigned int rhs) const
{
   return !(*this <= rhs);
}

bool CBigNum::operator>=(const unsigned int rhs) const
{
   return !(*this < rhs);
}

CBigNum &CBigNum::operator |=(const CBigNum &rhs)
{
   unsigned int nIdx;

   if (m_nSize < rhs.m_nSize)
      Resize(rhs.m_nSize);

   for (nIdx=0; nIdx < rhs.m_nSize; nIdx++)
   {
      m_arVal[nIdx] |= rhs.m_arVal[nIdx];
   }

   return *this;
}

CBigNum CBigNum::operator|(const CBigNum &rhs) const
{
   CBigNum Result(*this);
   Result |= rhs;
   return Result;
}

CBigNum &CBigNum::operator|=(const unsigned int rhs)
{
   this->m_arVal[0] |= rhs & 0xFFFF;
   this->m_arVal[1] |= rhs >> 16;
   return *this;
}

CBigNum CBigNum::operator|(const unsigned int rhs) const
{
   CBigNum Result(*this);
   Result.m_arVal[0] |= rhs & 0xFFFF;
   Result.m_arVal[1] |= rhs >> 16;
   return Result;
}

CBigNum::operator CBigNumString() const
{
   CBigNumString TempBigNum;
   CBigNum outval(*this);
   unsigned int nDigit;
   unsigned int nNumLen;
   unsigned int nPos;

   if (m_nSize <= 0)
   {
      TempBigNum.Realloc(2);
      TempBigNum[0U] = '0';
      TempBigNum[1U] = '\0';
      return TempBigNum;
   }

   if (outval == 0U)
   {
      TempBigNum.Realloc(2);
      TempBigNum[0U] = '0';
      TempBigNum[1U] = '\0';
      return TempBigNum;
   }

   nNumLen = m_nSize * 5;
   TempBigNum.Realloc(nNumLen+1);

   for (nDigit=nNumLen-1; outval>0U; nDigit--, outval/=10U)
   {
      TempBigNum[nDigit] = '0' + (outval % 10U);
   }

   if(++nDigit > 0U)
   {
      for (nPos=0; nDigit < nNumLen; nPos++, nDigit++)
      {
         TempBigNum[nPos] = TempBigNum[nDigit];
      }
   }
   TempBigNum[nPos] = '\0';
   
   return TempBigNum;
}

char & CBigNumString::operator [](unsigned int nIdx)
{
   static char dummychar = '\0';

   if (nIdx < m_nSize)
   {
      return m_szBuffer[nIdx];
   }

   return dummychar;
}

CBigNum::operator const char *() const
{
   static CBigNumString bnstr;

   bnstr = ((CBigNum *)this)->operator CBigNumString();
   return bnstr;
}

const CBigNumString &CBigNumString::operator=(const CBigNumString rhs)
{
   if (m_szBuffer == rhs.m_szBuffer)
   {
      return *this;
   }

   if (m_szBuffer != NULL)
   {
      delete[] m_szBuffer;
      m_szBuffer = NULL;
      m_nSize = 0;
   }
   if (rhs.m_nSize)
   {
      m_szBuffer = new char[rhs.m_nSize];
      m_nSize = rhs.m_nSize;
      strcpy(m_szBuffer, rhs.m_szBuffer);
   }

   return *this;
}

CBigNum CBigNum::factorial() const
{
   CBigNum Num;

   CBigNum dest(*this);

   for (Num=(*this)-1U; Num; Num-=1U)
   {
      dest *= Num;
   }
   return dest;
}

CBigNum CBigNum::operator-(const unsigned int rhs) const
{
   CBigNum rslt(*this);
   rslt -= rhs;
   return rslt;
}

CBigNum CBigNum::operator+(const CBigNum &rhs) const
{
   CBigNum rslt(*this);
   rslt += rhs;
   return rslt;
}

CBigNum CBigNum::operator+(const unsigned int rhs) const
{
   CBigNum rslt(*this);
   rslt += rhs;
   return rslt;
}

CBigNum CBigNum::sqrt() const
{
   CBigNum nGuess(*this<<2U);
   CBigNum nUpper(*this<<1U);
   CBigNum nLower(1);
   CBigNum nSqr;

   if (nGuess < nLower)
      nGuess = nLower;

   while (nLower < nUpper)
   {
      nSqr = nGuess*nGuess;
      if (nSqr > *this)
      {
         if (nUpper == nGuess)
            return nGuess;
         nUpper = nGuess;
      }
      else if (nSqr < *this)
      {
         if (nLower == nGuess)
            return nGuess;
         nLower = nGuess;
      }
      else
         return nGuess;
      nGuess = (nLower + nUpper) >> 1U;
   }
   nGuess.Reduce();

   return nGuess;
}

CBigNum CBigNum::gcd(const CBigNum &x, const CBigNum &y)
{
   if (y==0U) return x;
   return gcd(y, x%y);
}

CBigNum CBigNum::lcm(const CBigNum &x, const CBigNum &y)
{
   return x*y/gcd(x,y);
}

unsigned int CBigNum::log10() const
{
   CBigNum nNum(*this);
   unsigned int nLog10=0;

   while(nNum >= 10U)
      nNum/=10U,nLog10++;
   
   return nLog10;
}

unsigned int CBigNum::log2() const
{
   unsigned int i;
   unsigned int nMag = m_nSize * 16 - 1;

   for (i=m_nSize-1; i>0; i--)
   {
      if(m_arVal[i])
         break;
      nMag -= 16;
   }
   if ((i==0) && (m_arVal[i] == 0))
      return 0;

   while(!(m_arVal[i]&(1U<<(nMag%16))))
      nMag--;

   return nMag;
}

CBigNum CBigNum::Inverse(const CBigNum &mod) const
{
   CBigNum quo, mod1=mod, mod2=*this, modsq = mod * mod;
   CBigNum p1=0U, p2=1U, p3;

   while(mod2)
   {
      quo = mod1 / mod2;
      p3 = mod2;
      mod2 = mod1 % mod2;
      mod1 = p3;
      p3 = modsq + p1;
      p3 -= p2 * quo;
      p3 %= mod;
      p1 = p2;
      p2 = p3;
   }
   p1.Reduce();
   return p1;
}

void CBigNum::Reduce()
{
   unsigned int i;

   if (m_nSize <= 0)
      return;

   for (i=m_nSize-1; i>0; i--)
      if (m_arVal[i])
         break;

   if (++i < m_nSize)
      Resize(i);
}