| 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 |