static inline void Montgomery_inversion_mod_order_bingcd_partial()

in src/fpx.c [1322:1378]

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

static inline void Montgomery_inversion_mod_order_bingcd_partial(const digit_t* a, digit_t* x1, unsigned int* k, const digit_t* order)
{ // Partial Montgomery inversion modulo order.
    digit_t u[NWORDS_ORDER], v[NWORDS_ORDER], x2[NWORDS_ORDER] = {0};
    unsigned int cwords;  // number of words necessary for x1, x2

    copy_words(a, u, NWORDS_ORDER);
    copy_words(order, v, NWORDS_ORDER);
    copy_words(x2, x1, NWORDS_ORDER);
    x1[0] = 1;
    *k = 0;

    while (!is_zero_mod_order(v)) {
        cwords = ((*k + 1) / RADIX) + 1;
        if ((cwords < NWORDS_ORDER)) {
            if (is_even_mod_order(v)) {
                mp_shiftr1(v, NWORDS_ORDER);
                mp_shiftl1(x1, cwords);
            } else if (is_even_mod_order(u)) {
                mp_shiftr1(u, NWORDS_ORDER);
                mp_shiftl1(x2, cwords);
            } else if (!is_lt_mod_order(v, u)) {
                mp_sub(v, u, v, NWORDS_ORDER);
                mp_shiftr1(v, NWORDS_ORDER);
                mp_add(x1, x2, x2, cwords);
                mp_shiftl1(x1, cwords);
            } else {
                mp_sub(u, v, u, NWORDS_ORDER);
                mp_shiftr1(u, NWORDS_ORDER);
                mp_add(x1, x2, x1, cwords);
                mp_shiftl1(x2, cwords);
            }
        } else {
            if (is_even_mod_order(v)) {
                mp_shiftr1(v, NWORDS_ORDER);
                mp_shiftl1(x1, NWORDS_ORDER);
            } else if (is_even_mod_order(u)) {
                mp_shiftr1(u, NWORDS_ORDER);
                mp_shiftl1(x2, NWORDS_ORDER);
            } else if (!is_lt_mod_order(v, u)) {
                mp_sub(v, u, v, NWORDS_ORDER);
                mp_shiftr1(v, NWORDS_ORDER);
                mp_add(x1, x2, x2, NWORDS_ORDER);
                mp_shiftl1(x1, NWORDS_ORDER);
            } else {
                mp_sub(u, v, u, NWORDS_ORDER);
                mp_shiftr1(u, NWORDS_ORDER);
                mp_add(x1, x2, x1, NWORDS_ORDER);
                mp_shiftl1(x2, NWORDS_ORDER);
            }
        }
        *k += 1;
    }

    if (is_lt_mod_order(order, x1)) {
        mp_sub(x1, order, x1, NWORDS_ORDER);
    }
}