Botan  2.11.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(n.is_even() || n < 2)
18  throw Invalid_Argument("jacobi: second argument must be odd and > 1");
19 
20  BigInt x = a % n;
21  BigInt y = n;
22  int32_t J = 1;
23 
24  while(y > 1)
25  {
26  x %= y;
27  if(x > y / 2)
28  {
29  x = y - x;
30  if(y % 4 == 3)
31  J = -J;
32  }
33  if(x.is_zero())
34  return 0;
35 
36  size_t shifts = low_zero_bits(x);
37  x >>= shifts;
38  if(shifts % 2)
39  {
40  word y_mod_8 = y % 8;
41  if(y_mod_8 == 3 || y_mod_8 == 5)
42  J = -J;
43  }
44 
45  if(x % 4 == 3 && y % 4 == 3)
46  J = -J;
47  std::swap(x, y);
48  }
49  return J;
50  }
51 
52 }
BigInt const BigInt & x
Definition: numthry.h:139
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:26
BigInt size_t n
Definition: bigint.h:1096
size_t const BigInt & a
Definition: numthry.h:111
Definition: alg_id.cpp:13
const OctetString & y
Definition: symkey.h:126
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15