Botan  1.11.15
src/lib/math/numbertheory/jacobi.cpp
Go to the documentation of this file.
00001 /*
00002 * Jacobi Function
00003 * (C) 1999-2007 Jack Lloyd
00004 *
00005 * Botan is released under the Simplified BSD License (see license.txt)
00006 */
00007 
00008 #include <botan/numthry.h>
00009 
00010 namespace Botan {
00011 
00012 /*
00013 * Calculate the Jacobi symbol
00014 */
00015 s32bit jacobi(const BigInt& a, const BigInt& n)
00016    {
00017    if(a.is_negative())
00018       throw Invalid_Argument("jacobi: first argument must be non-negative");
00019    if(n.is_even() || n < 2)
00020       throw Invalid_Argument("jacobi: second argument must be odd and > 1");
00021 
00022    BigInt x = a, y = n;
00023    s32bit J = 1;
00024 
00025    while(y > 1)
00026       {
00027       x %= y;
00028       if(x > y / 2)
00029          {
00030          x = y - x;
00031          if(y % 4 == 3)
00032             J = -J;
00033          }
00034       if(x.is_zero())
00035          return 0;
00036 
00037       size_t shifts = low_zero_bits(x);
00038       x >>= shifts;
00039       if(shifts % 2)
00040          {
00041          word y_mod_8 = y % 8;
00042          if(y_mod_8 == 3 || y_mod_8 == 5)
00043             J = -J;
00044          }
00045 
00046       if(x % 4 == 3 && y % 4 == 3)
00047          J = -J;
00048       std::swap(x, y);
00049       }
00050    return J;
00051    }
00052 
00053 }