Как найти модульный мультипликативный инверсный номер без использования деления для fpga?

Question

Канонический ответ на этот вопрос - «использовать расширенный алгоритм евклидова», однако он использует операции деления и умножения, которые являются болью для реализации очень больших чисел на ПЛИС. Я хотел бы использовать его в генерации ключей RSA.

Answer 1

Я рекомендую binary euclidean algorithm

заменяет деление арифметических сдвигов, сравнение и вычитание

Удлиненных двоичный НОД, аналогично расширенным алгоритм Евклида, задается Кнутом вместе с указателями на другой версии.

Я нашел реализацию 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 

Answer 2

Предоставлено n, пусть Φ(n) будет числом целых чисел менее n и относительно простым с ним.

От https://en.wikipedia.org/wiki/Euler%27s_theorem, если m взаимно простое с n то m^(Φ(n)-1) мультипликативная инверсия m. Это можно вычислить с помощью умножения O(log(n)).