Coverage Report

Created: 2021-05-04 09:02

`/src/botan/build/include/botan/numthry.h`
 `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 ` `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` `10` `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 = 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` `*/` `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`