Botan
2.19.3
Crypto and TLS for C&
src
lib
math
numbertheory
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::BigInt
Definition
bigint.h:25
Botan::BigInt::is_even
bool is_even() const
Definition
bigint.h:403
Botan::BigInt::is_zero
bool is_zero() const
Definition
bigint.h:421
Botan::Invalid_Argument
Definition
exceptn.h:137
Botan
Definition
alg_id.cpp:13
Botan::low_zero_bits
size_t low_zero_bits(const BigInt &n)
Definition
numthry.cpp:39
Botan::jacobi
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition
jacobi.cpp:15
Generated by
1.9.8