commit fa1c24d14baf903c549fdb4f30a55b115eccad7d
author Michael Brown <mcb30@ipxe.org> Mon Oct 21 16:09:44 2024 +0100
committer Michael Brown <mcb30@ipxe.org> Mon Oct 21 17:24:53 2024 +0100
tree ada42236cae9c3c4af021eba46065a936729b85d
parent c69f9589cc7543baba08dbabdb5c30104fadaa34

[crypto] Add bigint_mod_invert() to calculate inverse modulo a power of two

Montgomery multiplication requires calculating the inverse of the
modulus modulo a larger power of two.

Add bigint_mod_invert() to calculate the inverse of any (odd) big
integer modulo an arbitrary power of two, using a lightly modified
version of the algorithm presented in "A New Algorithm for Inversion
mod p^k (Koç, 2017)".

The power of two is taken to be 2^k, where k is the number of bits
available in the big integer representation of the invertend.  The
inverse modulo any smaller power of two may be obtained simply by
masking off the relevant bits in the inverse.

Signed-off-by: Michael Brown <mcb30@ipxe.org>