Botan 2.19.2
Crypto and TLS for C&
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
11namespace Botan {
12
13/*
14* Tonelli-Shanks algorithm
15*/
16BigInt 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
static BigInt power_of_2(size_t n)
Definition: bigint.h:758
BigInt square(const BigInt &x) const
Definition: reducer.h:39
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31
Definition: alg_id.cpp:13
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:151
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:39
BigInt ressol(const BigInt &x, const BigInt &p)
Definition: ressol.cpp:16
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15