关于模乘法逆元的算法 - 编程论坛

#2

潇湘夜雨2007-05-11 19:16

题意不是很清楚！
A*X=1 %M？

#3

che08042007-05-11 21:06

回复：（潇湘夜雨）题意不是很清楚！A*X=1 %M？

就是A乘X在模M的情况下为1

#4

weishj2007-05-12 12:36

LZ的意思是这样吗
求X,s.t. (A*X)%M==1

#5

zkkpkk2007-05-12 13:21

就是楼上的意思啦，但是楼主是要求第一个？还是要求一个范围内的

#6

leeco2007-05-14 23:21

以下是引用che0804在2007-5-11 17:53:19的发言：
要做一个模乘法逆元的程序,即已知A,M,求X,使得A*X=1 %M,其实很简单,可是我菜得很~~

希望会做的大哥大姐帮帮小弟~!!

其实你说错了，这题不简单，A*X (mod M)=1 (mod M)是一个同余方程，等价于求满足A*X + M*Y=1的X，
这是一个不定方程，你可以参考一下数论的书，数学解法：大衍求一术，这个解法需要一套完整理论的支持，估计够你看上一阵子了，包括整除，剩余系，不定方程，同余，这个问题的解法在孙子定理(中国剩余定理)中也有利用到。
编程算法：扩展欧几里德算法