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中如何计算中国剩余定理？

点评

评分