美文网首页
Modular multiplicative inverse

Modular multiplicative inverse

作者: charlieyan | 来源:发表于2017-03-26 23:39 被阅读0次

不是很清楚这个应该怎么翻译,暂且就叫模乘法逆吧,定义是整数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下的模乘法逆

例1

a为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 的模乘法逆

相关文章

网友评论

      本文标题:Modular multiplicative inverse

      本文链接:https://www.haomeiwen.com/subject/ebllottx.html