Coverage Report

Created: 2020-05-23 13:54

/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
20.8k
   {
19
20.8k
   if(a == 0)
20
1
      return 0;
21
20.8k
   else if(a < 0)
22
0
      throw Invalid_Argument("ressol: value to solve for must be positive");
23
20.8k
   else if(a >= p)
24
2
      throw Invalid_Argument("ressol: value to solve for must be less than p");
25
20.7k
26
20.7k
   if(p == 2)
27
0
      return a;
28
20.7k
   else if(p <= 1)
29
0
      throw Invalid_Argument("ressol: prime must be > 1 a");
30
20.7k
   else if(p.is_even())
31
0
      throw Invalid_Argument("ressol: invalid prime");
32
20.7k
33
20.7k
   if(jacobi(a, p) != 1) // not a quadratic residue
34
4.94k
      return -BigInt(1);
35
15.8k
36
15.8k
   if(p % 4 == 3)
37
14.8k
      return power_mod(a, ((p+1) >> 2), p);
38
1.05k
39
1.05k
   size_t s = low_zero_bits(p - 1);
40
1.05k
   BigInt q = p >> s;
41
1.05k
42
1.05k
   q -= 1;
43
1.05k
   q >>= 1;
44
1.05k
45
1.05k
   Modular_Reducer mod_p(p);
46
1.05k
47
1.05k
   BigInt r = power_mod(a, q, p);
48
1.05k
   BigInt n = mod_p.multiply(a, mod_p.square(r));
49
1.05k
   r = mod_p.multiply(r, a);
50
1.05k
51
1.05k
   if(n == 1)
52
45
      return r;
53
1.00k
54
1.00k
   // find random non quadratic residue z
55
1.00k
   BigInt z = 2;
56
9.34k
   while(jacobi(z, p) == 1) // while z quadratic residue
57
8.34k
      ++z;
58
1.00k
59
1.00k
   BigInt c = power_mod(z, (q << 1) + 1, p);
60
1.00k
61
47.2k
   while(n > 1)
62
46.2k
      {
63
46.2k
      q = n;
64
46.2k
65
46.2k
      size_t i = 0;
66
2.38M
      while(q != 1)
67
2.34M
         {
68
2.34M
         q = mod_p.square(q);
69
2.34M
         ++i;
70
2.34M
71
2.34M
         if(i >= s)
72
0
            {
73
0
            return -BigInt(1);
74
0
            }
75
2.34M
         }
76
46.2k
77
46.2k
      c = power_mod(c, BigInt::power_of_2(s-i-1), p);
78
46.2k
      r = mod_p.multiply(r, c);
79
46.2k
      c = mod_p.square(c);
80
46.2k
      n = mod_p.multiply(n, c);
81
46.2k
      s = i;
82
46.2k
      }
83
1.00k
84
1.00k
   return r;
85
1.00k
   }
86
87
}