Botan
2.1.0
Crypto and TLS for C++11
Main Page
Namespaces
Classes
Files
File List
File Members
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
(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
}
Botan::Invalid_Argument
Definition:
exceptn.h:34
Botan::BigInt::is_even
bool is_even() const
Definition:
bigint.h:232
Botan::BigInt
Definition:
bigint.h:23
Botan::BigInt::is_negative
bool is_negative() const
Definition:
bigint.h:348
Botan
Definition:
alg_id.cpp:13
Botan::low_zero_bits
size_t low_zero_bits(const BigInt &n)
Definition:
numthry.cpp:20
Botan::BigInt::is_zero
bool is_zero() const
Definition:
bigint.h:250
Botan::jacobi
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition:
jacobi.cpp:15
Generated on Fri Aug 4 2017 19:29:39 for Botan by
1.8.9.1