Coverage Report

Created: 2020-06-30 13:58

/src/botan/src/lib/math/numbertheory/ressol.cpp
Line
Count
Source (jump to first uncovered line)
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
23.7k
   {
19
23.7k
   if(a == 0)
20
1
      return 0;
21
23.7k
   else if(a < 0)
22
0
      throw Invalid_Argument("ressol: value to solve for must be positive");
23
23.7k
   else if(a >= p)
24
2
      throw Invalid_Argument("ressol: value to solve for must be less than p");
25
23.7k
26
23.7k
   if(p == 2)
27
0
      return a;
28
23.7k
   else if(p <= 1)
29
0
      throw Invalid_Argument("ressol: prime must be > 1 a");
30
23.7k
   else if(p.is_even())
31
0
      throw Invalid_Argument("ressol: invalid prime");
32
23.7k
33
23.7k
   if(jacobi(a, p) != 1) // not a quadratic residue
34
5.84k
      return -BigInt(1);
35
17.8k
36
17.8k
   if(p % 4 == 3)
37
16.6k
      return power_mod(a, ((p+1) >> 2), p);
38
1.20k
39
1.20k
   size_t s = low_zero_bits(p - 1);
40
1.20k
   BigInt q = p >> s;
41
1.20k
42
1.20k
   q -= 1;
43
1.20k
   q >>= 1;
44
1.20k
45
1.20k
   Modular_Reducer mod_p(p);
46
1.20k
47
1.20k
   BigInt r = power_mod(a, q, p);
48
1.20k
   BigInt n = mod_p.multiply(a, mod_p.square(r));
49
1.20k
   r = mod_p.multiply(r, a);
50
1.20k
51
1.20k
   if(n == 1)
52
57
      return r;
53
1.14k
54
1.14k
   // find random non quadratic residue z
55
1.14k
   BigInt z = 2;
56
10.4k
   while(jacobi(z, p) == 1) // while z quadratic residue
57
9.34k
      ++z;
58
1.14k
59
1.14k
   BigInt c = power_mod(z, (q << 1) + 1, p);
60
1.14k
61
53.3k
   while(n > 1)
62
52.1k
      {
63
52.1k
      q = n;
64
52.1k
65
52.1k
      size_t i = 0;
66
2.71M
      while(q != 1)
67
2.66M
         {
68
2.66M
         q = mod_p.square(q);
69
2.66M
         ++i;
70
2.66M
71
2.66M
         if(i >= s)
72
0
            {
73
0
            return -BigInt(1);
74
0
            }
75
2.66M
         }
76
52.1k
77
52.1k
      c = power_mod(c, BigInt::power_of_2(s-i-1), p);
78
52.1k
      r = mod_p.multiply(r, c);
79
52.1k
      c = mod_p.square(c);
80
52.1k
      n = mod_p.multiply(n, c);
81
52.1k
      s = i;
82
52.1k
      }
83
1.14k
84
1.14k
   return r;
85
1.14k
   }
86
87
}