重复平方法求解指数运算的模结果

2020年4月16日22:32:22 发表评论

在学习非对称加密的算法时,我看到了个很有意思的数学问题,它能利用较小的计算量来计算一个较大的指数运算后的模结果,即xy%n的结果。

简单的累乘法

例如520%35。一般来说我们会简单的用5自乘20次再对35进行模运算,结果如下:

520%35=95367431640626%35=25%35

这样做的结果是在进行模运算之前会产生一个巨大的数值,但事实上只需要产生一个0-34之间的结果。下面我们介绍一种更简单的方法。

重复平方法

本着先观察再探究原理的思路学习,我们先引从上面那种方法更简单的计算步骤:

首先将20变成二进制即10100

逐步取上面的二进制位有(0,1,2,5,10,20)分别对应(0,1,10,101,1010,10100)

然后计算如下数值:

51=(50)251%35=5%35;
52=(51)2%35=25%35=25%35;
55=(52)251%35=625*5%35=10%35
510=(55)2%35=100%35=30%35;
520=(510)2%35=900%35=25%35

相信有些读者已经明白其中的奥义了,像是每次读取指数的一个位,然后左移一位,再加上后面一位的值。因此,我们要想得到520的值,只需要计算几次前面的数就能得到所需的结果。比起先求解指数结果,这样方便了很多。这也类似于之前的学的动态规划,将一个问题分解成许许多多的小问题求解思路。

好了,这只是一个数学问题,初看时觉得奥妙无穷,现在一想又觉得很自然。

flyingsheep

发表评论