algorithm - 如何在不使用 fpga 除法的情况下找到数字的模乘逆？

Question

这个问题的规范答案是“使用扩展欧几里得算法”，但是它使用除法和乘法运算，这对于在 FPGA 上实现非常大的数字来说是很痛苦的。我想在 RSA key 生成中使用它。

Answer 1

我推荐 binary euclidean algorithm

it replaces division with arithmetic shifts, comparisons, and subtraction

An extended binary GCD, analogous to the extended Euclidean algorithm, is given by Knuth along with pointers to other versions.

我找到了二进制扩展欧几里德算法的 Python 实现 here :

def strip_powers_of_two(c, p, q, gamma, delta):
    c = c / 2
    if (p % 2 == 0) and (q % 2 == 0):
        p, q = p//2, q//2
    else:
        p, q = (p + delta)//2, (q - gamma)//2
    return c, p, q

def ext_bin_gcd(a,b):
    u, v, s, t, r = 1, 0, 0, 1, 0
    while (a % 2 == 0) and (b % 2 == 0):
        a, b, r = a//2, b//2, r+1
    alpha, beta = a, b
    while (a % 2 == 0):
        a, u, v = strip_powers_of_two(a, u, v, alpha, beta)
    while a != b:
        if (b % 2 == 0):
            b, s, t = strip_powers_of_two(b, s, t, alpha, beta)
        elif b < a:
            a, b, u, v, s, t = b, a, s, t, u, v
        else:
            b, s, t = b - a, s - u, t - v
    return (2 ** r) * a, s, t