数学难题:关于欧拉定理:求高手来观望.在欧拉定理里面说,存在最小的M使得A^M==1(MOD N),M叫做A模N的指数,请问这个最小的指数怎么求啊,或者有什么算法吗?求高手指教?谢谢.

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/07 03:16:13

数学难题:关于欧拉定理:求高手来观望.在欧拉定理里面说,存在最小的M使得A^M==1(MOD N),M叫做A模N的指数,请问这个最小的指数怎么求啊,或者有什么算法吗?求高手指教?谢谢.
数学难题:关于欧拉定理:求高手来观望.
在欧拉定理里面说,存在最小的M使得A^M==1(MOD N),M叫做A模N的指数,请问这个最小的指数怎么求啊,或者有什么算法吗?求高手指教?谢谢.

数学难题:关于欧拉定理:求高手来观望.在欧拉定理里面说,存在最小的M使得A^M==1(MOD N),M叫做A模N的指数,请问这个最小的指数怎么求啊,或者有什么算法吗?求高手指教?谢谢.
最小的指数就是N的欧拉函数,也就是模N的完全剩余系中与N互质的数的个数
计算的话,如果一个数N的质因数分解是N=p1^n1*p2^n2*...*pm^nm
这个数的欧拉函数M=(p1^n1-p1^(n1-1))(p2^n2-p2^(n2-1))...(pn^nm-pn^(nm-1))
初等数论的书里都有,想进一步了解的话翻翻书吧