读书人

问下分数取余的方法.该如何处理

发布时间: 2012-02-14 19:19:19 作者: rapoo

问下分数取余的方法.
2/5) mod 17
=2×5^-1 mod 17 (中间的是5的-1次方)
=2×7 mod 17
=14

(4/6) mod 17
=4×6^-1 mod 17 (中间的是6的-1次方)
=4×3 mod 17
=12

类似这种运算,红色部分是怎么算出来的?
麻烦会数学的解答下,谢谢!

[解决办法]
1/x mod n
=x^(-1) mod n

就是求y,满足:
xy = 1 mod n

y是有限域F(n)上x的乘法逆元素。

具体算法,请查“扩展欧几里德算法”。

读书人网 >软件架构设计

热点推荐