- 1、本文档共141页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
* 本原根有关定理(续) * 本原根有关定理(续) 定理(原根的计算): * 本原根有关定理(续) * 本原根有关定理(续) * 本原根有关定理(续) 定理(原根的计算): * 本原根有关定理(续) 一个计算原根的算法: * 本原根有关定理(续) * 本原根有关定理(续) * 指数 如果整数m0有一个元根g,g,g2,…g?(m)(或数1,g,g,g2,…g?(m)-1)组成模数m的一组缩系。 例如, 3是模7的本原根,因此: 31 ≡3 32 ≡2 33 ≡6 34 ≡4 35 ≡5 36 ≡1 上述六个数刚好是模数m的一组缩系。 * 指数(续) 定义:任一整数n,(n,m)=1,必有唯一的整数k(0≤k ?(m)),满足: n≡gk(mod m) 其中k叫做n对模数m的指数,记做k=indgn(简记为ind n) (指数也叫做离散对数)。 * 指数(续) * 指数(续) * 指数(续) * 指数的性质:设g是m的原根,如果(a,m)=(b,m)=1: 指数(续) * 指数(续) * 指数(续) * 指数(续) * 离散对数困难问题 基于离散对数困难性假设,EIGamal提出了EIgamal公钥密码体制。 * 《孙子算经》中记载着一道世界闻名的“孙子问题”:“今有无不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?” 孙子问题等同于下面这样一个问题: 已知 x=2mod3,x=3mod5且x=2mod7,求整数x。 中国剩余定理 * 中国剩余定理(续) * 中国剩余定理(续) * 中国剩余定理(续) * 中国剩余定理(孙子: Sun Ze, 公元前450年,孙子定理): 设自然数m1,m2,…mr两两互素,并记M=m1m2…mr,则同余方程组: x ≡ b1(mod m1) x ≡ b2(mod m2) ....... ....... x ≡ br(mod mr) 有唯一解: x ≡ b1*M1*y1+b2*M2*y2+…+br*Mr*yr (mod M) Mi = M/mi ,yi = Mi-1 (mod mi) (1 ?i ?r) 中国剩余定理(续) * 例如:求以下同余方程组的解: x ≡5 mod 7 x ≡3 mod 11 x ≡10 mod 13 中国剩余定理解同余方程组 解: r=3,m1=7,m2=11,m3=13;b1=5,b2=3,b3=10; 模M = m1 ?m2 ? m3 = 1001, M1 =M/ m1 = m2 ? m3 = 143, M2 =91, M3 =77. y1 = M1-1(mod m1) = 143-1(mod 7) = 5, y2=4, y3=12. 解为: x = b1 ? M1 ? y1 + b2 ? M2 ? y2 + b3 ? M3 ? y3 (mod M) = 5 ? 143 ? 5 + 3 ? 91 ? 4 + 10 ? 77 ? 12 (mod 1001) =13907 (mod 1001) = 894 验证: x = 894 = 127 ?7+5 = 5 (mod 7) * 中国剩余定理: 除数 余数 最小公倍数 衍数 乘率 各总 答数 m1 b1 m=m1m2…mk M1 M1’ M1M1’b1 X=∑MiMi’bi (mod m) m2 b2 M2 M2’ M2M2’b2 …… …… …… …… …… mk bk Mk Mk’ MkMk’bk 其中: m=miMi Mi’Mi=1 (mod m) 中国剩余定理(续) * 中国剩余定理(续) * 例如(孙子算经)解法:表格法 除数 余数 最小公倍数 衍数 乘率 各总 答数 3 2 3x5x7=105 5x7 M1’=2 35x2x2 140+63+30=233 5 3 7x3 M2’=1 21x
您可能关注的文档
最近下载
- 【教学设计】 相交线.pdf VIP
- 期末模拟质量检测卷(试题)2023-2024学年统编版语文五年级上册.docx VIP
- 基于STM32指纹识别密码锁控制系统的设计与实现毕业论文.doc
- 干阑式建筑课件.ppt
- 新生儿早期基本保健(EENC)—新生儿早期基本保健(EENC)概述(儿童保健课件).pptx VIP
- 期末模拟质量检测卷(试题)2023-2024学年统编版语文五年级上册 (1).docx VIP
- 重庆工商大学2021-2022学年《Python程序设计》期末考试试卷(B卷)及标准答案.docx
- 应急管理综合行政执法有关政策解读-2024年云南省执业药师公需课答案.docx VIP
- 中国乙型肝炎病毒母婴传播防治指南(2024年版)解读.pdf
- 小学六年级语文上册各单元(1-8单元)检测试题卷含答案全套(部编版统编教材).doc
文档评论(0)