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

确实如此。