Botan
1.11.15
|
00001 /* 00002 * Jacobi Function 00003 * (C) 1999-2007 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/numthry.h> 00009 00010 namespace Botan { 00011 00012 /* 00013 * Calculate the Jacobi symbol 00014 */ 00015 s32bit jacobi(const BigInt& a, const BigInt& n) 00016 { 00017 if(a.is_negative()) 00018 throw Invalid_Argument("jacobi: first argument must be non-negative"); 00019 if(n.is_even() || n < 2) 00020 throw Invalid_Argument("jacobi: second argument must be odd and > 1"); 00021 00022 BigInt x = a, y = n; 00023 s32bit J = 1; 00024 00025 while(y > 1) 00026 { 00027 x %= y; 00028 if(x > y / 2) 00029 { 00030 x = y - x; 00031 if(y % 4 == 3) 00032 J = -J; 00033 } 00034 if(x.is_zero()) 00035 return 0; 00036 00037 size_t shifts = low_zero_bits(x); 00038 x >>= shifts; 00039 if(shifts % 2) 00040 { 00041 word y_mod_8 = y % 8; 00042 if(y_mod_8 == 3 || y_mod_8 == 5) 00043 J = -J; 00044 } 00045 00046 if(x % 4 == 3 && y % 4 == 3) 00047 J = -J; 00048 std::swap(x, y); 00049 } 00050 return J; 00051 } 00052 00053 }