快速幂取模运算

  • A+
所属分类:网络安全
摘要这一篇讲一下快速幂取模运算,给一个算例,便于理解。

最近在看密码学的时候看到了快速幂取模运算,在这里记录一下思路;

算例

算例还是用手写的了,方便一点;

快速幂取模运算

 

代码

下面来模拟一下上面的计算:

  1. import fire
  2. import pdb
  3. import logging
  4. logging.basicConfig(level=logging.ERROR)
  5. def fast_mod(x, n, m):
  6.     """
  7.     x^n(mod m)
  8.     """
  9.     logging.info("To Calcuate %d^%d(mod %d)" % (x,n,m))
  10.     logging.info("--- --- ---")
  11.     a = 1
  12.     b = x
  13.     loop=1
  14.     while True:
  15.         temp = n
  16.         logging.info("a=%d,b=%d,n=%d" % (a,b,n))
  17.         if n % 2 == 1 :
  18.             a_t = a
  19.             a = a * b % m
  20.             logging.info("Loop:%d, ans = %d * %d mod(%d) = %d" % (loop,a_t,b,m,a))
  21.         else:
  22.             logging.info("Loop:%d, Keep %d" % (loop,a))
  23.         b_tmp = b
  24.         b = b * b % m
  25.         logging.info("b = %d * %d mod(%d) = %d" % (b_tmp,b_tmp,m,b))
  26.         n = n//2
  27.         loop=loop+1
  28.         logging.info("--- --- ---")
  29.         #pdb.set_trace()
  30.         if temp < 1 :
  31.             return a
  32. def main():
  33.     fire.Fire(fast_mod)
  34. if __name__ == '__main__':
  35.     main()

运行结果如下 : 快速幂取模运算

验证一下计算结果是否正确:

快速幂取模运算

参考文章:模重复平方计算法(快速幂)【Python实现】<信安数论>

  • 微信公众号
  • 关注微信公众号
  • weinxin
  • QQ群
  • 我们的QQ群号
  • weinxin
王 茂南

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: