bn_fast_mp_invmod.c [plain text]
#include <tommath.h>
#ifdef BN_FAST_MP_INVMOD_C
int fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c)
{
mp_int x, y, u, v, B, D;
int res, neg;
if (mp_iseven (b) == 1) {
return MP_VAL;
}
if ((res = mp_init_multi(&x, &y, &u, &v, &B, &D, NULL)) != MP_OKAY) {
return res;
}
if ((res = mp_copy (b, &x)) != MP_OKAY) {
goto LBL_ERR;
}
if ((res = mp_mod (a, b, &y)) != MP_OKAY) {
goto LBL_ERR;
}
if ((res = mp_copy (&x, &u)) != MP_OKAY) {
goto LBL_ERR;
}
if ((res = mp_copy (&y, &v)) != MP_OKAY) {
goto LBL_ERR;
}
mp_set (&D, 1);
top:
while (mp_iseven (&u) == 1) {
if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
goto LBL_ERR;
}
if (mp_isodd (&B) == 1) {
if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
goto LBL_ERR;
}
}
if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
goto LBL_ERR;
}
}
while (mp_iseven (&v) == 1) {
if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
goto LBL_ERR;
}
if (mp_isodd (&D) == 1) {
if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
goto LBL_ERR;
}
}
if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
goto LBL_ERR;
}
}
if (mp_cmp (&u, &v) != MP_LT) {
if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
goto LBL_ERR;
}
if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
goto LBL_ERR;
}
} else {
if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
goto LBL_ERR;
}
if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
goto LBL_ERR;
}
}
if (mp_iszero (&u) == 0) {
goto top;
}
if (mp_cmp_d (&v, 1) != MP_EQ) {
res = MP_VAL;
goto LBL_ERR;
}
neg = a->sign;
while (D.sign == MP_NEG) {
if ((res = mp_add (&D, b, &D)) != MP_OKAY) {
goto LBL_ERR;
}
}
mp_exch (&D, c);
c->sign = neg;
res = MP_OKAY;
LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL);
return res;
}
#endif