Botan  2.6.0
Crypto and TLS for C++11
ressol.cpp
Go to the documentation of this file.
1 /*
2 * Shanks-Tonnelli (RESSOL)
3 * (C) 2007-2008 Falko Strenzke, FlexSecure GmbH
4 * (C) 2008 Jack Lloyd
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 */
8 
9 #include <botan/numthry.h>
10 #include <botan/reducer.h>
11 
12 namespace Botan {
13 
14 /*
15 * Shanks-Tonnelli algorithm
16 */
17 BigInt ressol(const BigInt& a, const BigInt& p)
18  {
19  if(a == 0)
20  return 0;
21  else if(a < 0)
22  throw Invalid_Argument("ressol: value to solve for must be positive");
23  else if(a >= p)
24  throw Invalid_Argument("ressol: value to solve for must be less than p");
25 
26  if(p == 2)
27  return a;
28  else if(p <= 1)
29  throw Invalid_Argument("ressol: prime must be > 1 a");
30  else if(p.is_even())
31  throw Invalid_Argument("ressol: invalid prime");
32 
33  if(jacobi(a, p) != 1) // not a quadratic residue
34  return -BigInt(1);
35 
36  if(p % 4 == 3)
37  return power_mod(a, ((p+1) >> 2), p);
38 
39  size_t s = low_zero_bits(p - 1);
40  BigInt q = p >> s;
41 
42  q -= 1;
43  q >>= 1;
44 
45  Modular_Reducer mod_p(p);
46 
47  BigInt r = power_mod(a, q, p);
48  BigInt n = mod_p.multiply(a, mod_p.square(r));
49  r = mod_p.multiply(r, a);
50 
51  if(n == 1)
52  return r;
53 
54  // find random non quadratic residue z
55  BigInt z = 2;
56  while(jacobi(z, p) == 1) // while z quadratic residue
57  ++z;
58 
59  BigInt c = power_mod(z, (q << 1) + 1, p);
60 
61  while(n > 1)
62  {
63  q = n;
64 
65  size_t i = 0;
66  while(q != 1)
67  {
68  q = mod_p.square(q);
69  ++i;
70 
71  if(i >= s)
72  {
73  return -BigInt(1);
74  }
75  }
76 
77  c = power_mod(c, BigInt::power_of_2(s-i-1), p);
78  r = mod_p.multiply(r, c);
79  c = mod_p.square(c);
80  n = mod_p.multiply(n, c);
81  s = i;
82  }
83 
84  return r;
85  }
86 
87 }
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:21
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:389
BigInt ressol(const BigInt &x, const BigInt &p)
Definition: ressol.cpp:17
bool is_even() const
Definition: bigint.h:296
static BigInt power_of_2(size_t n)
Definition: bigint.h:583
Definition: alg_id.cpp:13
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15
BigInt square(const BigInt &x) const
Definition: reducer.h:39
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31