Botan  2.19.1
Crypto and TLS for C++11
ressol.cpp
Go to the documentation of this file.
1 /*
2 * (C) 2007,2008 Falko Strenzke, FlexSecure GmbH
3 * (C) 2008 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/numthry.h>
9 #include <botan/reducer.h>
10 
11 namespace Botan {
12 
13 /*
14 * Tonelli-Shanks algorithm
15 */
16 BigInt ressol(const BigInt& a, const BigInt& p)
17  {
18  if(p <= 1 || p.is_even())
19  throw Invalid_Argument("ressol: invalid prime");
20 
21  if(a == 0)
22  return 0;
23  else if(a < 0)
24  throw Invalid_Argument("ressol: value to solve for must be positive");
25  else if(a >= p)
26  throw Invalid_Argument("ressol: value to solve for must be less than p");
27 
28  if(p == 2)
29  return a;
30 
31  if(jacobi(a, p) != 1) // not a quadratic residue
32  return -BigInt(1);
33 
34  if(p % 4 == 3) // The easy case
35  {
36  return power_mod(a, ((p+1) >> 2), p);
37  }
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 quadratic nonresidue z
55  word z = 2;
56  for(;;)
57  {
58  if(jacobi(z, p) == -1) // found one
59  break;
60 
61  z += 1; // try next z
62 
63  /*
64  * The expected number of tests to find a non-residue modulo a
65  * prime is 2. If we have not found one after 256 then almost
66  * certainly we have been given a non-prime p.
67  */
68  if(z >= 256)
69  return -BigInt(1);
70  }
71 
72  BigInt c = power_mod(z, (q << 1) + 1, p);
73 
74  while(n > 1)
75  {
76  q = n;
77 
78  size_t i = 0;
79  while(q != 1)
80  {
81  q = mod_p.square(q);
82  ++i;
83 
84  if(i >= s)
85  {
86  return -BigInt(1);
87  }
88  }
89 
90  c = power_mod(c, BigInt::power_of_2(s-i-1), p);
91  r = mod_p.multiply(r, c);
92  c = mod_p.square(c);
93  n = mod_p.multiply(n, c);
94  s = i;
95  }
96 
97  return r;
98  }
99 
100 }
bool is_even() const
Definition: bigint.h:403
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:39
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:151
BigInt ressol(const BigInt &x, const BigInt &p)
Definition: ressol.cpp:16
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31
static BigInt power_of_2(size_t n)
Definition: bigint.h:758
Definition: alg_id.cpp:13
BigInt square(const BigInt &x) const
Definition: reducer.h:39
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15