/src/botan/build/include/public/botan/numthry.h

Source
/*
* Number Theory Functions
* (C) 1999-2007,2018 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#ifndef BOTAN_NUMBER_THEORY_H_
#define BOTAN_NUMBER_THEORY_H_

#include <botan/bigint.h>

BOTAN_FUTURE_INTERNAL_HEADER(numthry.h)

namespace Botan {

class RandomNumberGenerator;

/**
* Return the absolute value
* @param n an integer
* @return absolute value of n
*/
inline BigInt abs(const BigInt& n) {
   return n.abs();
}

/**
* Compute the greatest common divisor
* @param x a positive integer
* @param y a positive integer
* @return gcd(x,y)
*/
BigInt BOTAN_PUBLIC_API(2, 0) gcd(const BigInt& x, const BigInt& y);

/**
* Least common multiple
* @param x a positive integer
* @param y a positive integer
* @return z, smallest integer such that z % x == 0 and z % y == 0
*/
BigInt BOTAN_PUBLIC_API(2, 0) lcm(const BigInt& x, const BigInt& y);

/**
* @param x an integer
* @return (x*x)
*/
BigInt BOTAN_PUBLIC_API(2, 0) square(const BigInt& x);

/**
* Modular inversion. This algorithm is const time with respect to x,
* as long as x is less than modulus. It also avoids leaking
* information about the modulus, except that it does leak which of 3
* categories the modulus is in: an odd integer, a power of 2, or some
* other even number, and if the modulus is even, leaks the power of 2
* which divides the modulus.
*
* @param x a positive integer
* @param modulus a positive integer
* @return y st (x*y) % modulus == 1 or 0 if no such value
*/
BigInt BOTAN_PUBLIC_API(2, 0) inverse_mod(const BigInt& x, const BigInt& modulus);

/**
* Compute the Jacobi symbol. If n is prime, this is equivalent
* to the Legendre symbol.
* @see http://mathworld.wolfram.com/JacobiSymbol.html
*
* @param a is a non-negative integer
* @param n is an odd integer > 1
* @return (n / m)
*/
int32_t BOTAN_PUBLIC_API(2, 0) jacobi(BigInt a, BigInt n);

/**
* Modular exponentiation
* @param b an integer base
* @param x a positive exponent
* @param m a positive modulus
* @return (b^x) % m
*/
BigInt BOTAN_PUBLIC_API(2, 0) power_mod(const BigInt& b, const BigInt& x, const BigInt& m);

/**
* Compute the square root of x modulo a prime using the Tonelli-Shanks
* algorithm. This algorithm is primarily used for EC point
* decompression which takes only public inputs, as a consequence it is
* not written to be constant-time and may leak side-channel information
* about its arguments.
*
* @param x the input
* @param p the prime modulus
* @return y such that (y*y)%p == x, or -1 if no such integer
*/
BigInt BOTAN_PUBLIC_API(3, 0) sqrt_modulo_prime(const BigInt& x, const BigInt& p);

/**
* @param x an integer
* @return count of the low zero bits in x, or, equivalently, the
*         largest value of n such that 2^n divides x evenly. Returns
*         zero if x is equal to zero.
*/
size_t BOTAN_PUBLIC_API(2, 0) low_zero_bits(const BigInt& x);

/**
* Check for primality
*
* This uses probabilistic algorithms - there is some non-zero (but very low)
* probability that this function will return true even if *n* is actually
* composite.
*
* @param n a positive integer to test for primality
* @param rng a random number generator
* @param prob chance of false positive is bounded by 1/2**prob
* @param is_random true if n was randomly chosen by us
* @return true if all primality tests passed, otherwise false
*/
bool BOTAN_PUBLIC_API(2, 0)
   is_prime(const BigInt& n, RandomNumberGenerator& rng, size_t prob = 64, bool is_random = false);

/**
* Test if the positive integer x is a perfect square ie if there
* exists some positive integer y st y*y == x
* See FIPS 186-4 sec C.4
* @return 0 if the integer is not a perfect square, otherwise
*         returns the positive y st y*y == x
*/
BigInt BOTAN_PUBLIC_API(2, 8) is_perfect_square(const BigInt& x);

/**
* Randomly generate a prime suitable for discrete logarithm parameters
* @param rng a random number generator
* @param bits how large the resulting prime should be in bits
* @param coprime a positive integer that (prime - 1) should be coprime to
* @param equiv a non-negative number that the result should be
               equivalent to modulo equiv_mod
* @param equiv_mod the modulus equiv should be checked against
* @param prob use test so false positive is bounded by 1/2**prob
* @return random prime with the specified criteria
*/
BigInt BOTAN_PUBLIC_API(2, 0) random_prime(RandomNumberGenerator& rng,
                                           size_t bits,
                                           const BigInt& coprime = BigInt::from_u64(0),
                                           size_t equiv = 1,
                                           size_t equiv_mod = 2,
                                           size_t prob = 128);

/**
* Generate a prime suitable for RSA p/q
* @param keygen_rng a random number generator
* @param prime_test_rng a random number generator
* @param bits how large the resulting prime should be in bits (must be >= 512)
* @param coprime a positive integer that (prime - 1) should be coprime to
* @param prob use test so false positive is bounded by 1/2**prob
* @return random prime with the specified criteria
*/
BigInt BOTAN_PUBLIC_API(2, 7) generate_rsa_prime(RandomNumberGenerator& keygen_rng,
                                                 RandomNumberGenerator& prime_test_rng,
                                                 size_t bits,
                                                 const BigInt& coprime,
                                                 size_t prob = 128);

/**
* Return a 'safe' prime, of the form p=2*q+1 with q prime
* @param rng a random number generator
* @param bits is how long the resulting prime should be
* @return prime randomly chosen from safe primes of length bits
*/
BigInt BOTAN_PUBLIC_API(2, 0) random_safe_prime(RandomNumberGenerator& rng, size_t bits);

/**
* The size of the PRIMES[] array
*/
const size_t PRIME_TABLE_SIZE = 6541;

/**
* A const array of all odd primes less than 65535
*/
extern const uint16_t BOTAN_PUBLIC_API(2, 0) PRIMES[];

}  // namespace Botan

#endif

Coverage Report

Created: 2025-11-09 06:58

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