計算大數的模數

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)。