How to calculate modular multiplicative inverse of a number in the context of RSA encryption?

Question

How to calculate modular multiplicative return number in the context of RSA encryption?

Answer 1

Direct modular exponentiation

The direct modular exponentiation method as an alternative to the extended Euclidean algorithm is as follows:

Source: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Answer 2

Use the Extended Euclidean Algorithm , which is significantly faster than direct modular exponentiation in practice.

Answer 3

In the algorithm .

Answer 4

If you need to calculate w for DSA alghoritm, you can use this:

 w = s^-1 mod q 

in fact

 w = s^(q-2) mod q 

See: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Using_Euler.27s_theorem

Answer 5

I developed a simpler inverse function

 def privateExponent(p,q,e): totient=(p-1)*(q-1) for k in range(1,e): if (totient*k+1) % e==0: return (totient*k+1)/e return -1 # shouldnt get here 

The equation d * e = 1 (total modulo) can be rewritten as d * e = 1 + k * totient (for some value of k), and the program simply looks for the first value of k, which makes the equation divisible by e (public exponent). This will work if e is small (as is usually recommended).

We can move all bignum operations out of a loop to improve its performance.

 def privateExponent(p,q,e): totient=(p-1)*(q-1) t_mod_e=totient % e k=0 total=1 while total!=0: k+=1 total=(total+t_mod_e) % e return (k*totient+1)/e 

It turns out that for e = 3 we really do not need to search, because the answer is always 2 * ((p-1) * (q-1) +1) / 3