Coverage Report

Created: 2021-05-04 09:02

/src/botan/build/include/botan/numthry.h
Line
Count
Source
1
/*
2
* Number Theory Functions
3
* (C) 1999-2007,2018 Jack Lloyd
4
*
5
* Botan is released under the Simplified BSD License (see license.txt)
6
*/
7
8
#ifndef BOTAN_NUMBER_THEORY_H_
9
#define BOTAN_NUMBER_THEORY_H_
10
11
#include <botan/bigint.h>
12
13
namespace Botan {
14
15
class RandomNumberGenerator;
16
17
/**
18
* Return the absolute value
19
* @param n an integer
20
* @return absolute value of n
21
*/
22
10
inline BigInt abs(const BigInt& n) { return n.abs(); }
23
24
/**
25
* Compute the greatest common divisor
26
* @param x a positive integer
27
* @param y a positive integer
28
* @return gcd(x,y)
29
*/
30
BigInt BOTAN_PUBLIC_API(2,0) gcd(const BigInt& x, const BigInt& y);
31
32
/**
33
* Least common multiple
34
* @param x a positive integer
35
* @param y a positive integer
36
* @return z, smallest integer such that z % x == 0 and z % y == 0
37
*/
38
BigInt BOTAN_PUBLIC_API(2,0) lcm(const BigInt& x, const BigInt& y);
39
40
/**
41
* @param x an integer
42
* @return (x*x)
43
*/
44
BigInt BOTAN_PUBLIC_API(2,0) square(const BigInt& x);
45
46
/**
47
* Modular inversion. This algorithm is const time with respect to x,
48
* as long as x is less than modulus. It also avoids leaking
49
* information about the modulus, except that it does leak which of 3
50
* categories the modulus is in: an odd integer, a power of 2, or some
51
* other even number, and if the modulus is even, leaks the power of 2
52
* which divides the modulus.
53
*
54
* @param x a positive integer
55
* @param modulus a positive integer
56
* @return y st (x*y) % modulus == 1 or 0 if no such value
57
*/
58
BigInt BOTAN_PUBLIC_API(2,0) inverse_mod(const BigInt& x,
59
                                         const BigInt& modulus);
60
61
/**
62
* Compute the Jacobi symbol. If n is prime, this is equivalent
63
* to the Legendre symbol.
64
* @see http://mathworld.wolfram.com/JacobiSymbol.html
65
*
66
* @param a is a non-negative integer
67
* @param n is an odd integer > 1
68
* @return (n / m)
69
*/
70
int32_t BOTAN_PUBLIC_API(2,0) jacobi(const BigInt& a, const BigInt& n);
71
72
/**
73
* Modular exponentation
74
* @param b an integer base
75
* @param x a positive exponent
76
* @param m a positive modulus
77
* @return (b^x) % m
78
*/
79
BigInt BOTAN_PUBLIC_API(2,0) power_mod(const BigInt& b,
80
                                       const BigInt& x,
81
                                       const BigInt& m);
82
83
/**
84
* Compute the square root of x modulo a prime using the Tonelli-Shanks
85
* algorithm. This algorithm is primarily used for EC point
86
* decompression which takes only public inputs, as a consequence it is
87
* not written to be constant-time and may leak side-channel information
88
* about its arguments.
89
*
90
* @param x the input
91
* @param p the prime
92
* @return y such that (y*y)%p == x, or -1 if no such integer
93
*/
94
BigInt BOTAN_PUBLIC_API(2,0) ressol(const BigInt& x, const BigInt& p);
95
96
/**
97
* @param x an integer
98
* @return count of the low zero bits in x, or, equivalently, the
99
*         largest value of n such that 2^n divides x evenly. Returns
100
*         zero if x is equal to zero.
101
*/
102
size_t BOTAN_PUBLIC_API(2,0) low_zero_bits(const BigInt& x);
103
104
/**
105
* Check for primality
106
* @param n a positive integer to test for primality
107
* @param rng a random number generator
108
* @param prob chance of false positive is bounded by 1/2**prob
109
* @param is_random true if n was randomly chosen by us
110
* @return true if all primality tests passed, otherwise false
111
*/
112
bool BOTAN_PUBLIC_API(2,0) is_prime(const BigInt& n,
113
                                    RandomNumberGenerator& rng,
114
                                    size_t prob = 64,
115
                                    bool is_random = false);
116
117
/**
118
* Test if the positive integer x is a perfect square ie if there
119
* exists some positive integer y st y*y == x
120
* See FIPS 186-4 sec C.4
121
* @return 0 if the integer is not a perfect square, otherwise
122
*         returns the positive y st y*y == x
123
*/
124
BigInt BOTAN_PUBLIC_API(2,8) is_perfect_square(const BigInt& x);
125
126
/**
127
* Randomly generate a prime suitable for discrete logarithm parameters
128
* @param rng a random number generator
129
* @param bits how large the resulting prime should be in bits
130
* @param coprime a positive integer that (prime - 1) should be coprime to
131
* @param equiv a non-negative number that the result should be
132
               equivalent to modulo equiv_mod
133
* @param equiv_mod the modulus equiv should be checked against
134
* @param prob use test so false positive is bounded by 1/2**prob
135
* @return random prime with the specified criteria
136
*/
137
BigInt BOTAN_PUBLIC_API(2,0) random_prime(RandomNumberGenerator& rng,
138
                                          size_t bits,
139
                                          const BigInt& coprime = BigInt::from_u64(0),
140
                                          size_t equiv = 1,
141
                                          size_t equiv_mod = 2,
142
                                          size_t prob = 128);
143
144
/**
145
* Generate a prime suitable for RSA p/q
146
* @param keygen_rng a random number generator
147
* @param prime_test_rng a random number generator
148
* @param bits how large the resulting prime should be in bits (must be >= 512)
149
* @param coprime a positive integer that (prime - 1) should be coprime to
150
* @param prob use test so false positive is bounded by 1/2**prob
151
* @return random prime with the specified criteria
152
*/
153
BigInt BOTAN_PUBLIC_API(2,7) generate_rsa_prime(RandomNumberGenerator& keygen_rng,
154
                                                RandomNumberGenerator& prime_test_rng,
155
                                                size_t bits,
156
                                                const BigInt& coprime,
157
                                                size_t prob = 128);
158
159
/**
160
* Return a 'safe' prime, of the form p=2*q+1 with q prime
161
* @param rng a random number generator
162
* @param bits is how long the resulting prime should be
163
* @return prime randomly chosen from safe primes of length bits
164
*/
165
BigInt BOTAN_PUBLIC_API(2,0) random_safe_prime(RandomNumberGenerator& rng,
166
                                               size_t bits);
167
168
/**
169
* The size of the PRIMES[] array
170
*/
171
const size_t PRIME_TABLE_SIZE = 6541;
172
173
/**
174
* A const array of all odd primes less than 65535
175
*/
176
extern const uint16_t BOTAN_PUBLIC_API(2,0) PRIMES[];
177
178
}
179
180
#endif