static inline void fpinv_mont_bingcd_partial()

in src/fpx.c [1081:1137]

• 54 lines of code
• 10 McCabe index (conditional complexity)

static inline void fpinv_mont_bingcd_partial(const felm_t a, felm_t x1, unsigned int* k)
{ // Partial Montgomery inversion via the binary GCD algorithm.
    felm_t u, v, x2;
    unsigned int cwords;  // Number of words necessary for x1, x2

    fpcopy(a, u);
    fpcopy((digit_t*)PRIME, v);
    fpzero(x1); x1[0] = 1;
    fpzero(x2);
    *k = 0;

    while (!is_felm_zero(v)) {
        cwords = ((*k + 1) / RADIX) + 1;
        if ((cwords < NWORDS_FIELD)) {
            if (is_felm_even(v)) {
                mp_shiftr1(v, NWORDS_FIELD);
                mp_shiftl1(x1, cwords);
            } else if (is_felm_even(u)) {
                mp_shiftr1(u, NWORDS_FIELD);
                mp_shiftl1(x2, cwords);
            } else if (!is_felm_lt(v, u)) {
                mp_sub(v, u, v, NWORDS_FIELD);
                mp_shiftr1(v, NWORDS_FIELD);
                mp_add(x1, x2, x2, cwords);
                mp_shiftl1(x1, cwords);
            } else {
                mp_sub(u, v, u, NWORDS_FIELD);
                mp_shiftr1(u, NWORDS_FIELD);
                mp_add(x1, x2, x1, cwords);
                mp_shiftl1(x2, cwords);
            }
        } else {
            if (is_felm_even(v)) {
                mp_shiftr1(v, NWORDS_FIELD);
                mp_shiftl1(x1, NWORDS_FIELD);
            } else if (is_felm_even(u)) {
                mp_shiftr1(u, NWORDS_FIELD);
                mp_shiftl1(x2, NWORDS_FIELD);
            } else if (!is_felm_lt(v, u)) {
                mp_sub(v, u, v, NWORDS_FIELD);
                mp_shiftr1(v, NWORDS_FIELD);
                mp_add(x1, x2, x2, NWORDS_FIELD);
                mp_shiftl1(x1, NWORDS_FIELD);
            } else {
                mp_sub(u, v, u, NWORDS_FIELD);
                mp_shiftr1(u, NWORDS_FIELD);
                mp_add(x1, x2, x1, NWORDS_FIELD);
                mp_shiftl1(x2, NWORDS_FIELD);
            }
        }
        *k += 1;
    }

    if (is_felm_lt((digit_t*)PRIME, x1)) {
        mp_sub(x1, (digit_t*)PRIME, x1, NWORDS_FIELD);
    }
}