mathematica 发表于 2008-12-13 20:52:49

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

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

mathematica 发表于 2008-12-13 21:04:33

我自己通过网络会了！！

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

无心人 发表于 2008-12-13 22:58:09

你可以考虑NTL

medie2005 发表于 2008-12-14 15:23:44

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

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

mathematica 发表于 2008-12-14 17:17:27

mathematica7.0

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

mathematica 发表于 2008-12-14 17:18:27

http://www.alpertron.com.ar/DILOG.HTM

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

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

mathematica 发表于 2008-12-14 17:20:43

pari计算！

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

无心人 发表于 2008-12-14 21:05:49

呵呵

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

medie2005 发表于 2008-12-15 08:42:04

计算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 发表于 2008-12-15 09:00:52

确实如此。:b:
页: [1] 2
查看完整版本: pari中如何计算中国剩余定理？