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

无心人 · 发表于 2008-12-15 09:24:39

100位？你确定容易么？

我想，至少24小时以上的分解时间
我上次测试只测试到了90位，5个小时
估计95位是50小时，100位500小时

gxqcn · 发表于 2008-12-15 09:28:52

相对来说，离散对数问题有时即便知道了因数分解形式也很难解决，
所以 9# medie2005 说得比较合情合理。

无心人 · 发表于 2008-12-15 10:47:25

你的意思
他的说法是建立在算法基础上的
而不是他本身可计算的基础

medie2005 · 发表于 2008-12-15 11:33:32

500小时还不算多。而且应该还可以更少。
但是，计算离散对数，就我知道的知识来看，比因子分解是要难一些的。当然，我仅仅是用了使用Pollard rho方法的工具，像什么据说是亚指数复杂度的Index Calculus Method，我就没用过了，也不知道具体速度如何（没找到这个算法的实现）。

mathematica · 发表于 2011-3-12 09:48:13

用mathematica计算中国剩余定理
http://bbs.emath.ac.cn/viewthread.php?tid=3039&extra=

mathematica · 发表于 2012-4-26 16:44:02

pari/gp计算中国剩余定理的子函数
http://bbs.emath.ac.cn/viewthrea ... romuid=865#pid42937

JogeChen · 发表于 2012-8-14 09:29:41

mathematica ：你好！
没想到都有计算中国同余定理的函数了，但我不清楚这些函数的内部计算如何，也不懂得如何使用这些函数，我想问你的是：这些函数对于位数高的，性能如何？

前不久我在“百度知道”中发布一个问题，没想到有人用ChineseRemainder计算出答案了!
题目是：同时符合以下3条件最小自然数是多少？除以9876543210余数54321，除以1234567899余321，除以5555666777余4321。
该用户使用ChineseRemainder[{54321, 321, 4321}, {9876543210, 1234567899, 5555666777}] 计算出正解：3719340241582843545611851311 也不晓得该函数用时多久。

你能否帮忙测一下此函数计算该题性能如何？还有适合该类问题最佳的函数是什么，性能如何？
以上是10位数的，假如20位、30位...呢？我有一方法，人工计算只需要40分钟左右可算出此题，若该方法写入函数中，性能肯定很快不用1秒，该方法有用吗？有经济价值吗？

mathematica · 发表于 2012-8-14 10:32:33

mathematica ：你好！
没想到都有计算中国同余定理的函数了，但我不清楚这些函数的内部计算如何，也不懂得如何使用这些函数，我想问你的是：这些函数对于位数高的，性能如何？

前不久我在“百度知道”中发布一个 ...
JogeChen 发表于 2012-8-14 09:29

你的第一帖就是用来回复我发的帖子，看来我写的帖子对论坛的流量的增加起到了作用，
其实这类计算都会不到1秒的，但是我觉得pari/gp的子函数功能更好，
http://bbs.emath.ac.cn/viewthrea ... romuid=865#pid42937
mathematica软件没有给出模，但是pari/gp给出了模，也就是给出了所有的解，
但是我觉得这个问题并没有太大的计算价值！

mathematica · 发表于 2012-8-14 10:34:34

Timing@ChineseRemainder[{54321, 321, 4321}, {9876543210, 1234567899,
5555666777}]
计算时间是非常约等于零
{0., 3719340241582843545611851311}

mathematica · 发表于 2012-8-14 10:36:21

这年代都没有人用手工计算这些问题了，手工计算那还得了？？？？？？？？
只是按回车键而已

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

[原创] pari中如何计算中国剩余定理？

点评

评分