快速幂取模运算

王 茂南
王 茂南
王 茂南
3043
文章
75
评论
2018年11月11日15:14:52
评论 965字阅读3分13秒
摘要这一篇讲一下快速幂取模运算，给一个算例，便于理解。

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

算例

算例还是用手写的了，方便一点；

快速幂取模运算

 

代码

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

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

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

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

快速幂取模运算

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

  • 微信公众号
  • 关注微信公众号
  • weinxin
  • QQ群
  • 我们的QQ群号
  • weinxin
王 茂南
  • 本文由 发表于 2018年11月11日15:14:52
  • 转载请务必保留本文链接：https://mathpretty.com/9852.html
匿名

发表评论

匿名网友 填写信息

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