1
$\begingroup$

I need to multiply a number x by modular inverse of y , and then with modular inverse of z and so many numbers . For example $$F=x\cdot (y)^{-1}\cdot (z)^{-1}\cdot (z_1)^{-1}... $$ Now beacause of this I need to calculate the mod. inverse of each number that I want to multiply . My question is how can I reduce the calculations, something like in terms of product of yz... or any method which doesn't requires calculating mod inverse every time? is it possible?

$\endgroup$
  • $\begingroup$ You better go to the site's page and learn how to write mathematics there, otherwise it could be not many will try to read your post as it is hard to understand. $\endgroup$ – DonAntonio Jun 9 '16 at 17:35
  • $\begingroup$ Fixed for legibility. And good instinct; there is indeed a better way, as per lhf's answer. $\endgroup$ – Joffan Jun 9 '16 at 17:45
3
$\begingroup$

The set of numbers that have a multiplicative inverse mod $m$ form an abelian group and so $$ x \cdot y_1^{-1} \cdot y_2^{-1} \cdots y_n^{-1} \equiv x \cdot (y_1 \cdot y_2 \cdots y_n)^{-1} \bmod m $$ and so you need compute only one modular inverse.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.