how to calculate (!a/!b)mod N

1 Like

thanksâ€¦

Let **a! = x, b! = y**. Then you want to calculate **x/y (mod N)** which can be obtained as **x*z (mod N)** where **z** is the modular multiplicative inverse of **y**, which exists if and only if **y** and **N** are prime to each other. If **N** is a prime number, then for all **y** in the set of natural numbers, **y** and **N** will be prime to each other.

You can calculate modular multiplicative inverse using several ways including Extended Euclidean Algorithm, Fermatâ€™s Little Theorem, etc.

More read: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

1 Like