CODEWITHSUNDEEP
algorithmcryptographyrsafpga
Hubert Bossy
Hubert Bossy

Reputation: 138

How do I find modular multiplicative inverse of number without using division for fpga?

The canonical answer for this question is "use extended euclidean algorithm" however it utilizes division and multiplication operations, which are pain to implement for very big numbers on FPGAs. I would like to use it in RSA key generation.

Upvotes: 1

Views: 1797

Answers (2)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

I recommend the 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.

I've found a Python implementation of the binary extended Euclidean algorithm 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

Upvotes: 3

btilly
btilly

Reputation: 46507

Given n, let Φ(n) be the number of integers less than n and relatively prime to it.

From https://en.wikipedia.org/wiki/Euler%27s_theorem, if m is relatively prime to n then m^(Φ(n)-1) is the multiplicative inverse of m. This can be computed with O(log(n)) multiplications.

Upvotes: 2

Related Questions