Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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 }
Botan::Invalid_Argument
Definition: exceptn.h:136
Botan::BigInt::is_even
bool is_even() const
Definition: bigint.h:401
Botan::low_zero_bits
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:40
Botan::BigInt
Definition: bigint.h:24
Botan
Definition: alg_id.cpp:13
Botan::BigInt::is_zero
bool is_zero() const
Definition: bigint.h:419
Botan::jacobi
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15