Botan
1.11.15
|
00001 /* 00002 * Shanks-Tonnelli (RESSOL) 00003 * (C) 2007-2008 Falko Strenzke, FlexSecure GmbH 00004 * (C) 2008 Jack Lloyd 00005 * 00006 * Botan is released under the Simplified BSD License (see license.txt) 00007 */ 00008 00009 #include <botan/numthry.h> 00010 #include <botan/reducer.h> 00011 00012 namespace Botan { 00013 00014 /* 00015 * Shanks-Tonnelli algorithm 00016 */ 00017 BigInt ressol(const BigInt& a, const BigInt& p) 00018 { 00019 if(a < 0) 00020 throw Invalid_Argument("ressol(): a to solve for must be positive"); 00021 if(p <= 1) 00022 throw Invalid_Argument("ressol(): prime must be > 1"); 00023 00024 if(a == 0) 00025 return 0; 00026 if(p == 2) 00027 return a; 00028 00029 if(jacobi(a, p) != 1) // not a quadratic residue 00030 return -BigInt(1); 00031 00032 if(p % 4 == 3) 00033 return power_mod(a, ((p+1) >> 2), p); 00034 00035 size_t s = low_zero_bits(p - 1); 00036 BigInt q = p >> s; 00037 00038 q -= 1; 00039 q >>= 1; 00040 00041 Modular_Reducer mod_p(p); 00042 00043 BigInt r = power_mod(a, q, p); 00044 BigInt n = mod_p.multiply(a, mod_p.square(r)); 00045 r = mod_p.multiply(r, a); 00046 00047 if(n == 1) 00048 return r; 00049 00050 // find random non quadratic residue z 00051 BigInt z = 2; 00052 while(jacobi(z, p) == 1) // while z quadratic residue 00053 ++z; 00054 00055 BigInt c = power_mod(z, (q << 1) + 1, p); 00056 00057 while(n > 1) 00058 { 00059 q = n; 00060 00061 size_t i = 0; 00062 while(q != 1) 00063 { 00064 q = mod_p.square(q); 00065 ++i; 00066 } 00067 00068 if(s <= i) 00069 return -BigInt(1); 00070 00071 c = power_mod(c, BigInt::power_of_2(s-i-1), p); 00072 r = mod_p.multiply(r, c); 00073 c = mod_p.square(c); 00074 n = mod_p.multiply(n, c); 00075 s = i; 00076 } 00077 00078 return r; 00079 } 00080 00081 }