silc_mp_modinv

SYNOPSIS

    SilcBool silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n);

DESCRIPTION

Find multiplicative inverse using Euclid's extended algorithm. Computes inverse such that a * inv mod n = 1, where 0 < a < n. Algorithm goes like this:

g(0) = n v(0) = 0 g(1) = a v(1) = 1

y = g(i-1) / g(i) g(i+1) = g(i-1) - y * g(i) = g(i)-1 mod g(i) v(i+1) = v(i-1) - y * v(i)

do until g(i) = 0, then inverse = v(i-1). If inverse is negative then n, is added to inverse making it positive again. (Sometimes the algorithm has a variable u defined too and it behaves just like v, except that initalize values are swapped (i.e. u(0) = 1, u(1) = 0). However, u is not needed by the algorithm so it does not have to be included.)