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