diff options
Diffstat (limited to 'comm/third_party/botan/src/lib/math/numbertheory/jacobi.cpp')
-rw-r--r-- | comm/third_party/botan/src/lib/math/numbertheory/jacobi.cpp | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/comm/third_party/botan/src/lib/math/numbertheory/jacobi.cpp b/comm/third_party/botan/src/lib/math/numbertheory/jacobi.cpp new file mode 100644 index 0000000000..284fc2b204 --- /dev/null +++ b/comm/third_party/botan/src/lib/math/numbertheory/jacobi.cpp @@ -0,0 +1,52 @@ +/* +* Jacobi Function +* (C) 1999-2007 Jack Lloyd +* +* Botan is released under the Simplified BSD License (see license.txt) +*/ + +#include <botan/numthry.h> + +namespace Botan { + +/* +* Calculate the Jacobi symbol +*/ +int32_t jacobi(const BigInt& a, const BigInt& n) + { + if(n.is_even() || n < 2) + throw Invalid_Argument("jacobi: second argument must be odd and > 1"); + + BigInt x = a % n; + BigInt y = n; + int32_t J = 1; + + while(y > 1) + { + x %= y; + if(x > y / 2) + { + x = y - x; + if(y % 4 == 3) + J = -J; + } + if(x.is_zero()) + return 0; + + size_t shifts = low_zero_bits(x); + x >>= shifts; + if(shifts % 2) + { + word y_mod_8 = y % 8; + if(y_mod_8 == 3 || y_mod_8 == 5) + J = -J; + } + + if(x % 4 == 3 && y % 4 == 3) + J = -J; + std::swap(x, y); + } + return J; + } + +} |