The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

逆元—人生到处应何似,应似飞鸿踏雪泥


先看费马小定理:

 费马小定理是数论中的一个重要定理,其内容为:
 假如p是质数,且(a,p)=1,那么 a^(p-1) ≡1(mod p)
 假如p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1

逆元:
设m为正整数,a为正整数,如果存在a' 使得:    
      a X a' = 1(mod m)
a'叫做a的逆元。密码学中用到了这个结论。RSA.

证明:
x^(MOD-1) = 1 (mod MOD)
x*x^(MOD-2) = 1 (mod MOD)  x^(MOD-2)为其逆元
其中MOD 为素数 , x要小于MOD,如果x>=MOD,可以先对x取MOD,这不会影响结果。

另一种想法:
其实用莫线性方程解a'亦可。
扩展欧几里德...

posted on 2010-04-16 19:45 abilitytao 阅读(135) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理