Botan  2.4.0
Crypto and TLS for C++11
jacobi.cpp
Go to the documentation of this file.
1 /*
2 * Jacobi Function
3 * (C) 1999-2007 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/numthry.h>
9 
10 namespace Botan {
11 
12 /*
13 * Calculate the Jacobi symbol
14 */
15 int32_t 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  int32_t 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_negative() const
Definition: bigint.h:353
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:21
bool is_zero() const
Definition: bigint.h:255
bool is_even() const
Definition: bigint.h:237
Definition: alg_id.cpp:13
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15