如何快速求a^x≡1 (mod n )中的x(n,a已知)

qianyb · 发表于 2010-5-6 14:12:39

您需要登录才可以下载或查看，没有账号？欢迎注册

×

根据$a^{x}-=1(mod n)$
如果已知a和n(a,x,n均为整数值)，如何快速求得x的值

mathe · 发表于 2010-5-6 14:28:41

这个是计算a关于n的次数，我们知道
$a^{phi(n)}-=1(mod n)$
所以x只能是$phi(n)$的因子，因子分解$phi(n)$就可以了。
当然如果n是非常大的合数导致$phi(n)$的计算很困难，那么就没有很好的计算方法了

wayne · 发表于 2010-5-6 14:50:13

最小的x，即Multiplicative Order ，学习了，。。。

qianyb · 发表于 2010-5-6 14:55:59

晕,我的公式怎么就显示不正确呢,mathe的公式就可以
a^x-=1(mod n)
哪里错了呢

wayne · 发表于 2010-5-6 14:57:39

a^{x}-=1
$a^{x}-=1$

===============
不过，在Firefox里面没问题

gxqcn · 发表于 2010-5-6 15:04:12

晕,我的公式怎么就显示不正确呢,mathe的公式就可以
a^x-=1(mod n)
哪里错了呢
qianyb 发表于 2010-5-6 14:55

我也在编辑你的帖子，问题不在于你，
而是自动标签“mod”带来的副作用。

qianyb · 发表于 2010-5-6 15:06:34

$a^{phi(n)}-=1(mod n)$,a^{phi(n)}-=1(mod n)

gxqcn · 发表于 2010-5-6 15:07:45

刚才在后台强行删除标签“mod”，就不存在楼主所说的问题了。

qianyb · 发表于 2010-5-6 15:11:26

谢谢了,现在可以了,呵呵

gxqcn · 发表于 2010-5-6 15:16:36

题目并没有强调求最小的x（即“数论指数”），
所以可直接令 $x=phi(n)$ 即可，前提是 $GCD(a,n)=1$

账号		自动登录	找回密码
密码			欢迎注册

[提问] 如何快速求a^x≡1 (mod n )中的x(n,a已知)