Revision control
Copy as Markdown
Other Tools
/*
* 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;
}
}