mil_rab.cpp

来自「含有多种公开密钥算法、多种块加密、多种数据流加密、多种HASH函数、多种Chec」· C++ 代码 · 共 54 行

/*************************************************
* Miller-Rabin Tester Source File                *
* (C) 1999-2002 The Botan Project                *
*************************************************/

#include <botan/mil_rab.h>
#include <botan/numthry.h>
#include <botan/barrett.h>

namespace Botan {

/*************************************************
* Miller-Rabin Test                              *
*************************************************/
bool MillerRabin_Test::passes_test(const BigInt& a)
   {
   if(a < 2 || a >= n_minus_1)
      throw Invalid_Argument("Bad size for 'a' in Miller-Rabin test");

   BigInt y = power_mod(a, r, reducer);

   if(y == BigInt::one() || y == n_minus_1)
      return true;

   for(u32bit j = 1; j != s; j++)
      {
      y = reducer->multiply(y, y);
      if(y == BigInt::one())
         return false;
      if(y == n_minus_1)
         return true;
      }
   return false;
   }

/*************************************************
* Miller-Rabin Constructor                       *
*************************************************/
MillerRabin_Test::MillerRabin_Test(const BigInt& num)
   {
   if(num.is_even() || num < 3)
      throw Invalid_Argument("MillerRabin_Test: Invalid number for testing");

   n = num;
   n_minus_1 = n - BigInt::one();
   r = n - BigInt::one();
   s = 0;

   while(r.is_even()) { s++; r >>= 1; }
   reducer = new BarrettReducer(n);
   }

}