Name Description Size
barrett.cpp Barrett Reduction This function assumes that the significant size of x_words (ie the number of words with a value other than zero) is at most 2 * mod_words. In any case, any larger value cannot be reduced using Barrett reduction; callers should have already checked for this. 6761
barrett.h Barrett Reduction 2043
dsa_gen.cpp Check if this size is allowed by FIPS 186-3 3567
info.txt 359
make_prm.cpp If v % p == (p-1)/2 then 2*v+1 == 0 (mod p) So if potentially generating a safe prime, we want to avoid this value because 2*v+1 will certainly not be prime. See "Safe Prime Generation with a Combined Sieve" M. Wiener https://eprint.iacr.org/2003/186.pdf 8879
mod_inv.cpp This uses a modular inversion algorithm designed by Niels Möller and implemented in Nettle. The same algorithm was later also adapted to GMP in mpn_sec_invert. It can be easily implemented in a way that does not depend on secret branches or memory lookups, providing resistance against some forms of side channel attack. There is also a description of the algorithm in Appendix 5 of "Fast Software Polynomial Multiplication on ARM Processors using the NEON Engine" by Danilo Câmara, Conrado P. L. Gouvêa, Julio López, and Ricardo Dahab in LNCS 8182 https://inria.hal.science/hal-01506572/document Thanks to Niels for creating the algorithm, explaining some things about it, and the reference to the paper. 11796
mod_inv.h Compute the inverse of x modulo some integer m Returns nullopt if no such integer exists eg if gcd(x, m) > 1 This algorithm is const time with respect to x, aside from its length. It also avoids leaking information about the modulus m, except that it does leak which of 3 categories the modulus is in: - An odd integer - A power of 2 - Some even number not a power of 2 And if the modulus is even, it leaks the power of 2 which divides the modulus. @param x a positive integer less than m @param m a positive integer Throws Invalid_Argument if x or m are negative 3571
monty.cpp 13084
monty.h The Montgomery representation of an integer 5775
monty_exp.cpp 7797
monty_exp.h Precompute for calculating values g^x mod p 2365
numthry.cpp Tonelli-Shanks algorithm 9973
numthry.h Return the absolute value @param n an integer @return absolute value of n 6064
primality.cpp -1 is the trivial square root of unity, so ``a`` is not a witness for this number - give up 5108
primality.h Perform Lucas primality test @see FIPS 186-4 C.3.3 @warning it is possible to construct composite integers which pass this test alone. @param n the positive integer to test @param mod_n a pre-created Barrett_Reduction for n @return true if n seems probably prime, false if n is composite 4264
primes.cpp 47157
reducer.cpp 509
reducer.h Modular Reducer This class is deprecated without replacement 2562