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.
4
- 1Are you sure there is a less painful way? Generating an RSA key is expected to be an expensive operation.user149341– user1493412017-01-11 19:58:35 +00:00Commented Jan 11, 2017 at 19:58
- You might also look into Montgomery modular multiplication.President James K. Polk– President James K. Polk2017-01-12 00:42:52 +00:00Commented Jan 12, 2017 at 0:42
- I think, I can't use it since modulus must be odd and .Hubert Bossy– Hubert Bossy2017-01-12 00:49:15 +00:00Commented Jan 12, 2017 at 0:49
- RSA modulus is always odd. You can compute the inverse mod phi(n)/4, and use some simple tricks to get the inverse you want.President James K. Polk– President James K. Polk2017-01-12 23:31:39 +00:00Commented Jan 12, 2017 at 23:31
Add a comment |
2 Answers
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 
Comments
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.
3 Comments
kraskevich
There is one issue with this solution. It requires computing
m^(phi(n)-1) modulo MOD, so it involves finding the remainder and uses division, anyway.
Matt Timmermans
Good answer for the use case -- would normally only apply for constant moduli where you can precompute Φ(n), but since this is for RSA key generation, Φ(n) can be easily calculated from the factors of n, which are known.
Hubert Bossy
@kraskevich I don't think that's the Φ(n) I'm looking for. In private key generation one must find d ≡ e^(−1) (mod φ(n)), so my φ(n) is in fact e^((φ(φ(n))-1) mod φ(n). Also since φ(n) equals (p-1)(q-1) and both of them are primes, I can't use my Montgomery fast exponentiation core because it works only when modulus is odd.