如何快速求a^x≡1 (mod n )中的x(n,a已知)
根据a^{x}-=1(mod n)如果已知a和n(a,x,n均为整数值)，如何快速求得x的值 这个是计算a关于n的次数，我们知道
$a^{phi(n)}-=1(mod n)$
所以x只能是$phi(n)$的因子，因子分解$phi(n)$就可以了。
当然如果n是非常大的合数导致$phi(n)$的计算很困难，那么就没有很好的计算方法了 最小的x，即Multiplicative Order ，学习了，。。。 晕,我的公式怎么就显示不正确呢,mathe的公式就可以
a^x-=1(mod n)
哪里错了呢 a^{x}-=1
$a^{x}-=1$
===============
不过，在Firefox里面没问题 晕,我的公式怎么就显示不正确呢,mathe的公式就可以
a^x-=1(mod n)
哪里错了呢
qianyb 发表于 2010-5-6 14:55 http://bbs.emath.ac.cn/images/common/back.gif
我也在编辑你的帖子，问题不在于你，
而是自动标签“mod”带来的副作用。 $a^{phi(n)}-=1(mod n)$,a^{phi(n)}-=1(mod n) 刚才在后台强行删除标签“mod”，就不存在楼主所说的问题了。 谢谢了,现在可以了,呵呵 题目并没有强调求最小的x（即“数论指数”），
所以可直接令 x=phi(n) 即可，前提是 GCD(a,n)=1
页:
[1]
2