数学研发论坛

 找回密码
 欢迎注册
查看: 2385|回复: 13

[原创] 用程序计算中国剩余定理

[复制链接]
发表于 2011-11-17 16:08:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
中国剩余定理的算法一直是古老的算法,有了计算机没有新的算法也不能进行复杂的运算,本人总结了一种新算法,用程序运行得到适合条件的最小数,与大家共享。
如果要求所有适合条件的数,用适合条件的最小数加上所有除数的最小公倍数

如果我要是简单的说
x=5mod11
x=9mod13
x=3mod17
x=13mod37
x=19mod31
x=17mod43
x=11mod123
得到最小适合条件的数是8914953173可能有作弊的嫌疑
那么我用123456789中的12、23、34、45、56、67、78作除数用2、3、4、5、6、7、8作余数,再找适合这样条件的最小数你还怀疑吗?
x=2mod12
x=3mod23
x=4mod34
x=5mod45
x=6mod56
x=7mod67
x=8mod78
得到最小适合条件的数是
11234797790
或者用123456789中的12、23、34、45、56、67、78作除数用1、2、3、4、5、6、7作余数
x=1mod12
x=2mod23
x=3mod34
x=4mod45
x=5mod56
x=6mod67
x=7mod78
得到最小适合条件的数是
11234797789
我也才发现,这个数与上面的数怎么差不多呢,这会让人怀疑是不是利用了数的什么规律得出来的,这个规律还真得值研究研究。
为了避嫌,用除数的数字之和做余数。
用12、23、34、45、56、67、78作除数用3、5、7、9、11、13、15作余数
x=3mod12
x=5mod23
x=7mod34
x=91mod45
x=11mod56
x=13mod67
x=15mod78
得到最小适合条件的数是
4447107459
不过大家不要误会,除数、余数不是随便编的,前提确实存在那么个数才行,也就是,有一个未知数只知道他分别被a1、a2、a3、……an除,余数分别为b1、b2、b3、……bn
通过这样的除数和余数才能求出适合条件的最小数,那个未知的数,也许是这个最小数,也许是最小数加上若干倍a1、a2、a3、……an的最小公倍数。如果随意取除数和对应的余数,不一定都有结果。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-11-17 18:51:24 | 显示全部楼层
用mathematica计算中国剩余定理

参看我的回复:
/redirect. ... o=lastpost#lastpost
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-11-17 20:03:10 | 显示全部楼层
编程高手不敢较量。
我的程序不是模运算是函数计算,对于我这低手来说也曾试过模运算,
相比之下函数计算要减少很多运行次数,不过对于你这高手来说,无所谓什么算法,
也都能很快实现,我在这里学习了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-26 16:49:58 | 显示全部楼层
参见这边的回复
/redirect. ... o=lastpost#lastpost
我又增加内容了!!!!!!!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-4-27 14:42:29 | 显示全部楼层
佩服!
希望能确认一下:计算适合下面10和11个条件最小数的时间、
前面是除数,后面是对应的余数。
546357,59781
9689641,8356469
9767641,635730
8767641,2580909
8769781,1337652
8767671,7218570
8745679,2598568
9945679,6598568
19945679,9768568
39945679,10767568
得377015171641327388423314171573260603209660132334414913604279636958
再加一个条件:
546357,59781
9689641,8356469
9767641,635730
8767641,2580909
8769781,1337652
8767671,7218570
8745679,2598568
9945679,6598568
19945679,9768568
39945679,10767568
739945321,65107675
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-27 14:50:51 | 显示全部楼层
5# 海里游
1067843838077398806824856020630918695454468820379724531786363078872355932122

Mathematica 瞬间即可算出来的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-27 15:45:44 | 显示全部楼层
代码文件以及图片都在附件里面,你自己看看吧!
其实这些东西都不消耗什么计算时间的!
海里游01.png

cal.gp

403 Bytes, 下载次数: 0, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-27 15:46:24 | 显示全部楼层
代码文件内容:

\r chineseM.gp
a=[59781,8356469,635730,2580909,1337652,7218570,2598568,6598568,9768568,10767568]
b=[546357,9689641,9767641,8767641,8769781,8767671,8745679,9945679,19945679,39945679]
chineseM(a,b)
a=[59781,8356469,635730,2580909,1337652,7218570,2598568,6598568,9768568,10767568,65107675]
b=[546357,9689641,9767641,8767641,8769781,8767671,8745679,9945679,19945679,39945679,739945321]
chineseM(a,b)
很简单的!!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-27 15:48:25 | 显示全部楼层
或者使用下面的代码,这样可以保存结果.
\r chineseM.gp
a=[59781,8356469,635730,2580909,1337652,7218570,2598568,6598568,9768568,10767568]
b=[546357,9689641,9767641,8767641,8769781,8767671,8745679,9945679,19945679,39945679]
chineseM(a,b)
\w
a=[59781,8356469,635730,2580909,1337652,7218570,2598568,6598568,9768568,10767568,65107675]
b=[546357,9689641,9767641,8767641,8769781,8767671,8745679,9945679,19945679,39945679,739945321]
chineseM(a,b)
\w
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-27 15:48:43 | 显示全部楼层
结果是:
Mod(377015171641327388423314171573260603209660132334414913604279636958, 1588353008051967115688819881528670581870780595008940491749652793367)
Mod(1067843838077398806824856020630918695454468820379724531786363078872355932122, 1175294376404328392099807963348914124405631527894461470037594687826491485807)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-12-15 23:06 , Processed in 0.073986 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表