diff options
author | Keith Isdale <keith.isdale@nokia.com> | 2010-07-26 14:56:53 +1000 |
---|---|---|
committer | Keith Isdale <keith.isdale@nokia.com> | 2010-07-26 14:56:53 +1000 |
commit | 9f034793bcfc51c2b7c1dd14db806f7258f9a9eb (patch) | |
tree | 63bd0f50ce5b77828ad8205eafd7b9412810499e /botan/src/math/numbertheory/jacobi.cpp | |
parent | 619d92cfef29e653bfdf852e83888e50cfc4348f (diff) | |
parent | 65271649dbc90f3af1184ad1b23bdb64c0c07d07 (diff) |
Merge branch 'master' of git://git-nokia.trolltech.com.au/qtsoftware/research/qtuitest
Diffstat (limited to 'botan/src/math/numbertheory/jacobi.cpp')
-rw-r--r-- | botan/src/math/numbertheory/jacobi.cpp | 53 |
1 files changed, 53 insertions, 0 deletions
diff --git a/botan/src/math/numbertheory/jacobi.cpp b/botan/src/math/numbertheory/jacobi.cpp new file mode 100644 index 0000000..2ad05ff --- /dev/null +++ b/botan/src/math/numbertheory/jacobi.cpp @@ -0,0 +1,53 @@ +/* +* Jacobi Function +* (C) 1999-2007 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include <botan/numthry.h> + +namespace Botan { + +/* +* Calculate the Jacobi symbol +*/ +s32bit jacobi(const BigInt& a, const BigInt& n) + { + if(a.is_negative()) + throw Invalid_Argument("jacobi: first argument must be non-negative"); + if(n.is_even() || n < 2) + throw Invalid_Argument("jacobi: second argument must be odd and > 1"); + + BigInt x = a, y = n; + s32bit 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; + + u32bit 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; + } + +} |