数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 41187|回复: 214

[特别关注]中国剩余定理及求模的逆元的公式

[复制链接]
发表于 2017-10-5 22:45 | 显示全部楼层 |阅读模式
本帖最后由 ysr 于 2017-10-5 14:54 编辑

普及个知识:中国剩余定理在小学课本中有,大学也讲,所以老少皆宜。古代中国🇨🇳 研究已很精辟,并广泛应用。历代皇帝重视历法,历法中大量用到这种计算,古代中国历法精确就得益于此。农历是阴阳合历,既照顾太阳又照顾月亮,较复杂,我不懂历法,不知具体如何算。在现代科技中也会用到,如公钥密码体制中的公钥和私钥的计算。
法:若某数除以ABC余分别为r1,r2,r3,求此数?
      求除A余r1要在BC的倍数中求,先求乘以BC使余数(/A)为1的乘率m,(或直接得出余r1的乘率),则m乘r1与BC的积满足/A余r1。当数据很大不便于从1试到m,求m的方法古人叫“大衍求一术”,其实就是现代的求模的逆元,若ed/P余1则e与d互为逆元。查书,用到辗转相除法,好象没有公式,只讲到方法:辗转相除(用余数再去除除数)到余1再逆推回去。
我弄了个经验公式供试用:
求e模p的逆元d=?即ed/P余1,(e和P必须互质,不互质的姑何?没研究)

当r1=1,则d=1或P的倍数+1,或P+1,
当r2=1,则d=x2(p-1),(这两个解可以证明的,下面的未证明),
x1,x2,…为商,r1,r2,…为余,下面的合为一个公式,当rw=1,则d=x1(x2+x3+…+x(w-1)+1)+w-3,其中w,(w-1),为下脚码,
由公式知,
当r3=1,则d=x1(x2+1),
如求137/120的逆元?137/120=10……17,120/17=7……1,则d=7*119=833,833*137=114121,114120/120=951,
如131/120的逆元?131/120=1……11,120/11=10……10,11/10=1……1,则d=1*(10+1)=11,11*131=1441,1440/120=12,
注意:公式中只计算到倒数第二的商,倒数第一的商没用,公式逻辑未证明,经验公式。
 楼主| 发表于 2017-10-5 23:54 | 显示全部楼层
例某数除120余3,除137余0,求此数?
解:由上知833*3*137/120余3,故此数为114121*3=342363.
这个不是最小的,故342363MOD(137*120)=13563,则13563为最小的满足题意的正确答案。
 楼主| 发表于 2017-10-6 21:29 | 显示全部楼层
模的逆元可以是无穷多,上面的结果是不是最小我们就不管了,只要是真的逆元就行,我们可以通过除以最小公倍求余来得到满足中国剩余定理的最小值。
 楼主| 发表于 2017-10-30 04:48 | 显示全部楼层
如何求出最小的逆元d呢?可以这样做:
例如:求315/11的逆元d?
解:315/11=28……7,11/7=1……4,7/4=1……3,4/3=1……1,据公式得:d=x1(x2+x3+1)+4-3=28*3+1=85,
而315*85=26775,26774/11=2434,故85是逆元,但不是最小。
85/11=7……8,而315*8=2520,2519/11=229,故8才是最小的逆元。
      当然此题可以用试除法(穷举法)直接得出315*8MOD11=1.这样做同样费事。
 楼主| 发表于 2017-10-30 05:11 | 显示全部楼层
本帖最后由 ysr 于 2017-10-29 21:17 编辑

有人这样做:由于315/11=28……7,7*8-1=0MOD11,故d=8。
这样做很简单,但当P很大时也很麻烦,故有时用上面公式更简便些。
 楼主| 发表于 2017-10-30 05:29 | 显示全部楼层
再如上面的例子:833/120=6……113,而113*137-1=0MOD120,故113为最小的逆元。
 楼主| 发表于 2017-10-30 07:35 | 显示全部楼层
由于3*113*137=46443=13563MOD(137*120),故这样得出来的值也不一定是满足中国剩余定理的最小值,而13563/137=99=3*33,而33并不是逆元,虽99是满足*137/120余3的最小值,但要用穷举法试出来很费事,故用公式有时是较省事的。
 楼主| 发表于 2018-2-21 16:05 | 显示全部楼层
中国剩余定理问题中,模数不是两两互质如何弄?
古人研究结果:         (秦九韶)(1)找合适的定数(就是模数),(2)约掉公因子,成新的定数(现代叫模数)。
注意:结果要符合原题意,要具体问题具体分析,自己灵活掌握。
欢迎探讨,欢迎批评!
发表于 2018-2-22 07:02 | 显示全部楼层
67和23就不行。
其实求逆元的公式完全可由辗转相除法得出,但书写麻烦,还不如直接说相除法
 楼主| 发表于 2018-2-22 08:45 | 显示全部楼层
谢谢关注!
例:求67模23的逆元?
67/23=2……21,23/21=1……2,21/2=10……1,故r3=1,x1=2,x2=1,由公式知逆元d=x1(x2+1)=2*(1+1)=4,4*67=268,267/23=11……14,故4非逆元,的确是反例,谢谢提供反例!
查资料,古人求逆元还要看末尾的商值的奇偶性,x3=10为偶数,故可能要另一种公式,再研究研究!谢谢朋友!欢迎继续探讨!
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-29 07:27 , Processed in 0.079101 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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