如何使用歐拉和中國剩餘定理進行模冪運算？
我正在嘗試使用拉格朗日和中國剩餘定理在 Java 中實現模冪運算。
我們給出的例子是：
讓 $ N = 55 = 5 · 11 $ 並假設我們要計算 $ 27^{37} \pmod N $ .
他沒有給我們答案，而是說：
最有效的方法是使用拉格朗日定理、一些模 5 和 11 的乘法以及 CRT 來組合這兩個結果。
使用 Lagrange / Euler totient 我得到 $ \varphi(N) = 40 $ ，似乎我應該使用它來計算放入中國剩餘定理所需的同餘。
我知道我可以使用擴展歐幾里得算法計算同餘，但需要減少答案，否則執行時間仍然不可行（在這種情況下可能不可行，但對於我正在使用的 1024 位數，這是一個大問題）。
我知道它們可以減少，從我在研究這個時發現的一份文件中，該文件指出：
$$ a^k \equiv a ^ { k \pmod{\varphi(n)}} \pmod n. $$
我已經嘗試過並嘗試過並嘗試按照他的方式進行減少，但我就是不明白。他也沒有提到什麼 $ m $ 當他說 $ k = m · \varphi(n) + k’ $ .
正如您可能收集的那樣，我的數學不是那麼熱門，所以如果可能的話，也許可以給出一個“傻瓜”的答案。
給出的例子——讓 $ N = 55 = 5 · 11 $ 並假設我們要計算 $ 27^{37} \pmod N $ - 不是家庭作業，所以如果有人能指導我完成它，特別是簡化中文剩餘定理同餘的簡化，我將非常感激。
簡單地通過它：
- 第 1 步：我們首先計算計算 $ M^e \bmod p $ （在哪裡 $ p $ 是模量的因素之一。根據費馬小定理，這與 $ M^{e \mod p-1} \bmod p $ （這就是真正節省的地方），所以在你的例子中（ $ p=5 $ )，我們得到：
$ M^e \bmod p = 27^{37 \bmod 4} \bmod 5 = 2^1 \bmod 5 = 2 $
- 第2步：我們對另一個素數做同樣的事情 $ q $ :
$ M^e \bmod q = 27^{37 \bmod 10} \bmod 11 = 5^7 \bmod 11 = 3 $
- 第三步：利用中國剩餘定理，我們重構 $ M^e \bmod pq $ 從 $ M^e \bmod p $ 和 $ M^e \bmod q $ :
$ C_p = M^e \bmod p = 2 $
$ C_q = M^e \bmod q = 3 $
$ M^e \bmod pq = C_q + q \cdot (q^{-1} (C_p - C_q) \bmod p) = 3 + 11 \cdot (1 \cdot (2-3) \bmod 5) = 3 + 11 \cdot 4 = 47 $