- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
RSA算法从数学基础到实例全面解
HYPERLINK /boksic/article/details/6912381 RSA算法从数学基础到实例全面解析
分类: HYPERLINK /boksic/article/category/911247 算法 2011-11-20 21:59 148人阅读 HYPERLINK /boksic/article/details/6912381 \l comments#comments 评论(0) HYPERLINK javascript:void(0); \o 收藏 收藏 HYPERLINK /boksic/article/details/6912381 \l report#report \o 举报 举报
1、同余(合同式)
两个整数a,b,若它们除以正整数m所得的余数相等,则称a,b对于模m同余
记作
例如1≡13 (mod 12),可以理解为时钟上1点和13点的指针位置相同
重要性质
例如1^5=1,13 ^5=371293=30941*12+1
即1^5≡1≡13 ^5(mod 12)
2、欧拉函数(Eulers totient function)
欧拉函数 φ(n)是少于或等于n的数中与n互质的数的数目,例如φ(9) = 6,因为比9小的数中与9互质的有1, 2, 4, 5, 7,8六个数,所以9的欧拉函数为6。
计算方法:
将n分解为质数相乘的形式
,每个pi都是质数
则欧拉函数
例如
两条结论
若n为质数,则φ(n)=n-1
若m与n互质,则 φ(mn) = φ(m)φ(n)
3、费马小定理与欧拉定理
费马小定理
若a为整数,p为质数则
如果a不是p的倍数,可写为
推广:欧拉定理
对任何两互质正整数a, m,,有
4、模反
a的模反(模m)即满足下列等式的x
或写成
例如
当x=4时上式成立,所以4是3的模反,
注意:4并不是唯一的解,在4的基础上加上模(11)的倍数依然满足上式,例如15,26,37,48等
但是寻找这样的x并不是一目了然,可以用下面的扩展欧几里得算法。
5、扩展欧几里得算法
作为欧几里得算法的扩展,寻找的是满足ax + by = gcd(a,b)的x和y。
当a,b互质时,可以看出x是a在b模下的反(ax=1(mod y)) ;可以看出y是b在a模下的反(by=1(mod x))
我用python写了一个递归实现
[python] HYPERLINK /boksic/article/details/6912381 \o view plain view plain HYPERLINK /boksic/article/details/6912381 \o copy copy HYPERLINK /boksic/article/details/6912381 \o print print HYPERLINK /boksic/article/details/6912381 \o ? ?
def?extended_gcd(a,?b):??
????if?(b?==?0):??
????????return?(1,?0)??
????else:??
????????q,?r?=?a/b,a%b??
????????s,?t?=?extended_gcd(b,?r)??
????????return?(t,?s?-?q?*?t)??
??????????
HTMLCONTROL Forms.HTML:TextArea.1 运行实例,还是拿上面的例子,求3在模11下的反
[python] HYPERLINK /boksic/article/details/6912381 \o view plain view plain HYPERLINK /boksic/article/details/6912381 \o copy copy HYPERLINK /boksic/article/details/6912381 \o print print HYPERLINK /boksic/article/details/6912381 \o ? ?
print?extended_gcd(3,11)??
HTMLCONTROL Forms.HTML:TextArea.1 得到结果:
[plain] HYPERLINK /boksic/article/details/6912381 \o view plain view plain HYPERLINK /boksic/article/details/6912381 \o copy copy HYPERLINK /boksic/artic
您可能关注的文档
- PRIMUS集团并购广州得力,月盛装亮相上海洗涤展.doc
- Prim算法和Kruskal算法.doc
- Preparationofcrudenuclearextractfromratprimaryhepatocytes.doc
- PRINCE国际项目管理论证培训(F+P).doc
- PrinciplesofCorporateFinance英文十版习题解答Chap.doc
- PRNproductbriefv.doc
- PressDisplay全球报刊数据库.doc
- PrinciplesofCorporateFinance英文十版习题解答Chap4.doc
- ProductChangeControlProcedure.doc
- ProductCertificationApplicationRevformforfactory.doc
最近下载
- 艾梅乙医学ppt课件.pptx VIP
- 海姆立克急救法(完美版)课件.pptx VIP
- 锂离子电池不良失效分析系列压差大.pptx VIP
- 《童年》阅读评测试题(附答案).pdf VIP
- 英语常用词根词缀表(排版整齐).pdf VIP
- 【小升初】2024-2025学年四川省成都市下学期新七年级分班真题数学试题(含答案).docx VIP
- TD∕T 1087-2023 主体功能区优化完善技术指南.pdf
- 优秀备课组评选方案.docx VIP
- 稳定币发展十年:趋势、应用与前景.docx VIP
- 四川省成都市成都石室联合中学2024-2025学年上学期七年级分班(奖学金)模拟数学试题(含答案).pdf VIP
文档评论(0)