计算大数的模数

Question

我正在学习离散结构的测验。我如何计算2^50（mod5）？我可以使用计算器使用较小的数字计算结果，但我无法用大数目计算结果。

Answer 1

假设我们有一个数字N = 5X + Y，其中N，X和Y是整数（即N mod 5 = Y）。那么随之而来的是2N = 2(5X + Y) = 10x + 2Y，即2N mod 5 = 2Y mod 5。

相若方式中，由于2^50可以被改写为（（2^5）^ 5）^ 2：

2^50 mod 5 = ((2^5 mod 5)^5 mod 5)^2 mod 5

2^50 mod 5 = ((2)^5 mod 5)^2 mod 5

2^50 mod 5 = (2)^2 mod 5

2^50 mod 5 = 4

Answer 2

您可以利用if (2^x = t)(mod A) then (2^(x*y) = t^y)(mod A)这一事实。

因此，我们有：

2^2 = (-1) (mod 5) which means 
2^50 = (-1)^25(mod 5) 
    = -1 (mod 5) (which is the same as 4 (mod 5)) 

使用实际计算中，我们看到2^50 = 1125899906842624 = -1(mod 5)。