Botan 2.19.2 Crypto and TLS for C&
jacobi.cpp
Go to the documentation of this file.
1/*
2* Jacobi Function
3* (C) 1999-2007 Jack Lloyd
4*
6*/
7
8#include <botan/numthry.h>
9
10namespace Botan {
11
12/*
13* Calculate the Jacobi symbol
14*/
15int32_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}
bool is_even() const
Definition: bigint.h:403
bool is_zero() const
Definition: bigint.h:421
Definition: alg_id.cpp:13
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:39
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15