模n下大数幂乘的两个算法的基本运作原理 - Go语言中文社区

模n下大数幂乘的两个算法的基本运作原理


写在前面:

这是我第一篇CSDN博客,除了跟各位前辈交流学习,我同样想我跟那些没学过计算机的家人朋友分享我所学到的东西(至少让他们知道我是学什么的,真的不是修电脑的大哭)。由于水平所限,肯定无法把这些东西说得十分浅显明白,但我尽量。如有错漏,欢迎指教。


先说几个基本的概念,如果你早知道了就跳过。

1.  mod(求余):

mod(求余)是数论中最基本的运算之一,就是求一个数除以另一个数的余数。

例如:5 mod 7 =5 ;(5除以7,商得0,余数为2)

      18 mod 7 =4;(18除以7,商得2,余数为4)

      5^2 mod 5 =0; (25除以5,商得3,余数为0)

2. RSA算法 :

这是一个目前十分常用公钥加密算法,几乎每次网购都会用到它。所谓的公钥加密算法是一样十分神奇的事物,它的加密密钥和解密密钥并不是同一个密钥,加密密钥是可以公开的。通俗点来说,就是锁上一把锁的钥匙和打开同一把锁的钥匙是两把不一样的钥匙。大家都可以用加密钥匙锁上箱子(加密消息),但只有掌握解密密钥的人才能打开箱子(解密消息)。


3. 模n的大数幂乘算法:

上面那些求余例子十分简单,但遇到像98^193 mod 100 这种数就很难算了。

你可能想先将98^193求出来,再对100求余。但是这样有两个问题:

1.98的193次方这是一个非常非常大的数,在绝大多编程语言中没有一个内置类型能容纳得下那么大的数。

2.98的193次方对100求余,你想想在笔算时要算多久,绝对会算到手软。

在RSA算法中,这种式子的数字一般很大很大,所以这就需要一定的算法来求解这种式子。


模n的大数幂乘有两种比较通用的算法,网上都能搜到,但我没找到相关的算法证明。推导一轮后终于明白是什么回事,所以就写下来了。

求解 x^r mod n

算法1:

1. a<-x; b<-r; c<-1;

2. 若b=0,则输出结果c,结束

3. 若b为奇数,跳转至5

4. b<- b/2; a<-(a*a mod n);跳转至3

5. b<- b-1; c<-(c*a mod n);跳转至2

下面以98^193 mod 100 为例说明这算法如何执行:

   98^193 mod 100                             //a=98;b=193;c=1;n=100

= 1* 98^193    mod 100                     //b=193,奇数,对应步骤5

= (1*98) * (98^192)   mod 100          //b=192,偶数,对应步骤4

= 98 * ( 98^2)^96   mod 100           

= 98* (98^2 mod 100 )^96  mod 100  

= 98 * (4)^96   mod 100               

//因为98^2 mod 100 =t*100+4 (t为某整数) 。根据二项展开式,(t*100+4)^96的展开式中除了4^96    这项外,

    其余项都包括(t*100)这个因子,含有这因子的式子=k*(t*100) ,  在mod100下=0。

=98 * (16)^48   mod 100

=98 * (256 mod 100 )^24   mod 100

=98 * (56)^24   mod 100

=98 * (3136 mod 100)^12 mod 100

=98 * (36)^12 mod 100

=98 * (96)^6  mod 100

=98 * (16)^3 mod 100                     //b=3,奇数,对应步骤5

=(98*16 mod 100) * (16)^2 mod 100

=68 * ( 256 mod 100)^1  mod 100

=68 * (56)^1  mod 100                    //b=1

=(68 * 56 mod 100)  *  (56)^0  mod 100

=8 * (56)^0   mod 100             //  b=0  ,返回结果c=8 ,结束



算法2:( r 转换为2进制数求解,好像该算法是高德纳提出的)

1.  先将r 转换为 2进制数序列,r=Rk Rk-1 Rk-2...Rk1 Rk0。

2.  c <- 1, m<-1;

3.  for i  <-  0 to k

            c<-c^2 mod n                   //计算2^i模12 mod 12 的余数

            if (Ri=1)

            then m = c*m mod n

            next i

下面用9^11 mod 12 来说明:

1)先将11转化为二进制数序列 1011


2)  9^11 mod 12

     = 9^(1011)  mod 12

      = 9^(1000) * 9^(0000) *9^(0010) *9^(0001)   mod 12


3)    9^(0001)   mod 12=9;

          m =1*9 mod 12 =9;      //R0=1,执行m =c*m mod n

          9^(0010)   mod 12=(9^(0001)   mod 12)^2 =9^2 mod 12 =9;

          m=9*9 mod 12 =9      //R1=1,执行m =c*m mod n

          9^(0100)   mod 12=(9^(0010)   mod 12)^2 =9^2 mod 12 =9;

          //R2=0 ,不执行m =c*m mod n,m的值无改变

          9^(1000)   mod 12=(9^(0100)   mod 12)^2 =9^2 mod 12 =9;

          m=9*9 mod 12 =9      //R3=1,执行m =c*m mod n

          循环结束,返回m=9


不知你明白我所说的没。

欢迎交流指教。




版权声明:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/instituteliao/article/details/9326157
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。
  • 发表于 2020-03-01 21:49:25
  • 阅读 ( 873 )
  • 分类:算法

0 条评论

请先 登录 后评论

官方社群

GO教程

猜你喜欢