pari中如何计算中国剩余定理？

mathematica

我知道mathematica中是使用ChineseRemainder这个函数，
但是pari/gp中的范例太少，我不知道如何使用chinese这个函数，
不知道谁能给我几个示范的例子？？？？

mathematica

chinese(Mod(2,29),Mod(52,251))但是这个函数远远没有mathematica的好！！！！
pari/gp一次只能使用两个参数！郁闷！！！！！！

无心人

你可以考虑NTL

medie2005

感觉PARI/GP还是不能令人满意的。很多功能没实现，有些实现了的效率也很差。

mathematica也有一些函数效率很差。比如，计算离散对数的函数MultiplicativeOrder[g, n, a1, a2, ...]. 我在mathematica 6.0中用这个函数计算
$4^{x}=9 mod 744490528907$，慢得让人不感相信！
而在Discrete logarithm calculator中，得出x，1秒都不要。不知道mathematica 7.0是否有改进。

mathematica

input：Timing[MultiplicativeOrder[4, 744490528907]]
output：{0., 372245264453}
无论6.0还是7.0都没有你说的那么慢！

mathematica

找到一个bug！
base=3
power=1
modulus=10000

计算不出来！！！！！！！！！！！！！！！

mathematica

znorder(Mod(3,10000))
得500
3^k=1 mod 10000, k是最小的正整数，k=500

无心人

呵呵

嫌弃他们慢
自己写C代码啊

medie2005

计算a^x=1 mod n当然简单了，计算phi(n),然后求phi(n)的因子，依次计算就可以了。
对744490528907，phi(744490528907)=2*372245264453.
因此，我们只需要计算4^372245264453 mod 744490528907, 4^2 mod 744490528907就可以了。
因此，很快就可以确定x的值。

对计算a^x=1 mod n而言，复杂度等同与因子分解。目前来看，计算100位的n还是可以的。
但是对计算a^x=c mod n而言，计算80位都比较困难。

gxqcn

确实如此。