Botan  1.10.9
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 * Distributed under the terms of the Botan license
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  throw Invalid_Argument("ressol(): a to solve for must be positive");
21  if(p <= 1)
22  throw Invalid_Argument("ressol(): prime must be > 1");
23 
24  if(a == 0)
25  return 0;
26  if(p == 2)
27  return a;
28 
29  if(jacobi(a, p) != 1) // not a quadratic residue
30  return -BigInt(1);
31 
32  if(p % 4 == 3)
33  return power_mod(a, ((p+1) >> 2), p);
34 
35  size_t s = low_zero_bits(p - 1);
36  BigInt q = p >> s;
37 
38  q -= 1;
39  q >>= 1;
40 
41  Modular_Reducer mod_p(p);
42 
43  BigInt r = power_mod(a, q, p);
44  BigInt n = mod_p.multiply(a, mod_p.square(r));
45  r = mod_p.multiply(r, a);
46 
47  if(n == 1)
48  return r;
49 
50  // find random non quadratic residue z
51  BigInt z = 2;
52  while(jacobi(z, p) == 1) // while z quadratic residue
53  ++z;
54 
55  BigInt c = power_mod(z, (q << 1) + 1, p);
56 
57  while(n > 1)
58  {
59  q = n;
60 
61  size_t i = 0;
62  while(q != 1)
63  {
64  q = mod_p.square(q);
65  ++i;
66  }
67 
68  if(s <= i)
69  return -BigInt(1);
70 
71  c = power_mod(c, BigInt(BigInt::Power2, s-i-1), p);
72  r = mod_p.multiply(r, c);
73  c = mod_p.square(c);
74  n = mod_p.multiply(n, c);
75  s = i;
76  }
77 
78  return r;
79  }
80 
81 }
BigInt n
Definition: numthry.cpp:26
BigInt BOTAN_DLL ressol(const BigInt &x, const BigInt &p)
Definition: ressol.cpp:17
std::invalid_argument Invalid_Argument
Definition: exceptn.h:20
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31
s32bit jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:141
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:251
BigInt r
Definition: numthry.cpp:26
BigInt square(const BigInt &x) const
Definition: reducer.h:39
size_t s
Definition: numthry.cpp:27