Modular multiplicative inverse

2019-04-14 21:18发布

不是很清楚这个应该怎么翻译,暂且就叫模乘法逆吧,定义是整数a在整数m下的模乘法逆为x,有ax=(mod m)x的范围要在0,1,2,...,m-1之间举个例子就能说明这个问题啦Given two integers ‘a’ and ‘m’, find modular multiplicative inverse of ‘a’ under modulo ‘m’.
给定两个整数a和m,找到a在m下的模乘法逆例1a为3,m为11输入:  a = 3, m = 11
输出: 4因 (4*3) mod 11 = 1, 4 是 3 的模乘法逆有人可能会说 15 也是3的模乘法逆,因为 "(15*3) mod 11"的结果也是 1, 但是 15 不在范围 {0, 1, 2, ... 10}中, 所以15不是例2输入:  a = 10, m = 17输出: 12因 (10*12) mod 17 = 1, 12 是 10 的模乘法逆