/*

* Jacobi Function

* (C) 1999-2007 Jack Lloyd

*

* Botan is released under the Simplified BSD License (see license.txt)

*/

#include <botan/numthry.h>

namespace Botan {

/*

* Calculate the Jacobi symbol

*/

int32_t jacobi(const BigInt& a, const BigInt& n)

   {

   if(n.is_even() || n < 2)

      throw Invalid_Argument("jacobi: second argument must be odd and > 1");

   BigInt x = a % n;

   BigInt y = n;

   int32_t J = 1;

   while(y > 1)

      {

      x %= y;

      if(x > y / 2)

         {

         x = y - x;

         if(y % 4 == 3)

            J = -J;

         }

      if(x.is_zero())

         return 0;

      size_t shifts = low_zero_bits(x);

      x >>= shifts;

      if(shifts % 2)

         {

         word y_mod_8 = y % 8;

         if(y_mod_8 == 3 || y_mod_8 == 5)

            J = -J;

         }

      if(x % 4 == 3 && y % 4 == 3)

         J = -J;

      std::swap(x, y);

      }

   return J;

   }

}