如何计算x ^ y mod z? [英] How to calculate x^y mod z?
本文介绍了如何计算x ^ y mod z?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我想知道如何计算x ^ y mod z. x和y非常大(无法容纳64位整数),而z将容纳64位整数. 一件事不给出答案,例如x ^ y mod z与(x mod z)^ y mod z相同.
I am wondering how to calculate x^y mod z. x and y are very large (can't fit in 64 bit integer) and z will fit 64 bit integer. And one thing don't give answers like x^y mod z is same as (x mod z)^y mod z.
推荐答案
以下是标准方法,采用伪代码:
Here is the standard method, in pseudo-code:
function powerMod(b, e, m)
x := 1
while e > 0
if e % 2 == 1
x := (b * x) % m
e := e - 1
else
b := (b * b) % m
e := e / 2
return x
该算法称为通过平方求幂"或平方乘"方法.
The algorithm is known as exponentiation by squaring or the square and multiply method.
这篇关于如何计算x ^ y mod z?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文