Botan 3.0.0-alpha0
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
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) { 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*/
30BigInt 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*/
38BigInt BOTAN_PUBLIC_API(2,0) lcm(const BigInt& x, const BigInt& y);
39
40/**
41* @param x an integer
42* @return (x*x)
43*/
44BigInt 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*/
58BigInt 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*/
70int32_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*/
79BigInt 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 modulus
92* @return y such that (y*y)%p == x, or -1 if no such integer
93*/
94BigInt BOTAN_PUBLIC_API(3,0) sqrt_modulo_prime(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*/
102size_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*/
112bool 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*/
124BigInt 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*/
137BigInt 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*/
153BigInt 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*/
165BigInt BOTAN_PUBLIC_API(2,0) random_safe_prime(RandomNumberGenerator& rng,
166 size_t bits);
167
168/**
169* The size of the PRIMES[] array
170*/
171const size_t PRIME_TABLE_SIZE = 6541;
172
173/**
174* A const array of all odd primes less than 65535
175*/
176extern const uint16_t BOTAN_PUBLIC_API(2,0) PRIMES[];
177
178}
179
180#endif
BigInt abs() const
Definition: bigint.cpp:388
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:31
PolynomialVector b
Definition: kyber.cpp:821
Definition: alg_id.cpp:13
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:296
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo, size_t prob)
Definition: make_prm.cpp:106
BigInt lcm(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:282
BigInt square(const BigInt &x)
Definition: numthry.cpp:170
const uint16_t PRIMES[]
Definition: primes.cpp:12
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:181
BigInt abs(const BigInt &n)
Definition: numthry.h:22
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:171
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:370
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
Definition: make_prm.cpp:229
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:220
BigInt sqrt_modulo_prime(const BigInt &a, const BigInt &p)
Definition: numthry.cpp:40
BigInt is_perfect_square(const BigInt &C)
Definition: numthry.cpp:338
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: numthry.cpp:130
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:308
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: mod_inv.cpp:177