Botan  1.10.9
jacobi.cpp
Go to the documentation of this file.
1 /*
2 * Jacobi Function
3 * (C) 1999-2007 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/numthry.h>
9 
10 namespace Botan {
11 
12 /*
13 * Calculate the Jacobi symbol
14 */
15 s32bit jacobi(const BigInt& a, const BigInt& n)
16  {
17  if(a.is_negative())
18  throw Invalid_Argument("jacobi: first argument must be non-negative");
19  if(n.is_even() || n < 2)
20  throw Invalid_Argument("jacobi: second argument must be odd and > 1");
21 
22  BigInt x = a, y = n;
23  s32bit J = 1;
24 
25  while(y > 1)
26  {
27  x %= y;
28  if(x > y / 2)
29  {
30  x = y - x;
31  if(y % 4 == 3)
32  J = -J;
33  }
34  if(x.is_zero())
35  return 0;
36 
37  size_t shifts = low_zero_bits(x);
38  x >>= shifts;
39  if(shifts % 2)
40  {
41  word y_mod_8 = y % 8;
42  if(y_mod_8 == 3 || y_mod_8 == 5)
43  J = -J;
44  }
45 
46  if(x % 4 == 3 && y % 4 == 3)
47  J = -J;
48  std::swap(x, y);
49  }
50  return J;
51  }
52 
53 }
bool is_even() const
Definition: bigint.h:158
BigInt n
Definition: numthry.cpp:26
bool is_negative() const
Definition: bigint.h:245
std::invalid_argument Invalid_Argument
Definition: exceptn.h:20
signed int s32bit
Definition: types.h:37
s32bit jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:141
void swap(Botan::MemoryRegion< T > &x, Botan::MemoryRegion< T > &y)
Definition: secmem.h:425
bool is_zero() const
Definition: bigint.h:176