/src/botan/build/include/botan/numthry.h
Line | Count | Source (jump to first uncovered line) |
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 | 0 | 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 = 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 |