Botan 3.7.1
Crypto and TLS for C&
numthry.h
Go to the documentation of this file.
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
14
15namespace Botan {
16
17class RandomNumberGenerator;
18
19/**
20* Return the absolute value
21* @param n an integer
22* @return absolute value of n
23*/
24inline BigInt abs(const BigInt& n) {
25 return n.abs();
26}
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*/
34BigInt 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*/
42BigInt BOTAN_PUBLIC_API(2, 0) lcm(const BigInt& x, const BigInt& y);
43
44/**
45* @param x an integer
46* @return (x*x)
47*/
48BigInt 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*/
62BigInt 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*/
73int32_t BOTAN_PUBLIC_API(2, 0) jacobi(const BigInt& a, const BigInt& n);
74
75/**
76* Modular exponentation
77* @param b an integer base
78* @param x a positive exponent
79* @param m a positive modulus
80* @return (b^x) % m
81*/
82BigInt 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*/
95BigInt 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*/
103size_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*/
118bool 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*/
128BigInt 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*/
141BigInt 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*/
157BigInt 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*/
169BigInt BOTAN_PUBLIC_API(2, 0) random_safe_prime(RandomNumberGenerator& rng, size_t bits);
170
171/**
172* The size of the PRIMES[] array
173*/
174const size_t PRIME_TABLE_SIZE = 6541;
175
176/**
177* A const array of all odd primes less than 65535
178*/
179extern const uint16_t BOTAN_PUBLIC_API(2, 0) PRIMES[];
180
181} // namespace Botan
182
183#endif
#define BOTAN_PUBLIC_API(maj, min)
Definition api.h:19
#define BOTAN_FUTURE_INTERNAL_HEADER(hdr)
Definition api.h:84
BigInt abs() const
Definition bigint.cpp:374
BigInt abs(const BigInt &n)
Definition numthry.h:24