NIST PRIMES - 密碼學
我有問題，如果我有 $ p = \text{P-192} = 2^{192} - 2^{64} - 1 $ 與基地 $ 2^{64} $ 所以， $ 2^{192} \equiv 2^{64} + 1 \pmod p $ 一樣的 $ (p=\text{P-192}) $ 或者 $ 2^{256} \equiv 2^{128} + 2^{64} \pmod p $
或者
$ 2^{320} \equiv 2^{128} + 2^{64} +1 \pmod p $
請問你能幫幫我嗎？我不明白例如 $ 2^{256} \equiv 2^{128} + 2^{64} \pmod p $
太感謝了。
我不確定我的問題是否正確，但在我看來，您是在詢問關於模減模的問題 $ p=2^{192}-2^{64}-1 $ .
如果是這樣，我應該在寫這個答案之前搜尋雨披的這個答案，可能會讓你感興趣。
請注意，在下文中，基數的選擇並不重要。
如果我們必須減少 $ 2^{192} \mod{p} $ 你可以減去模數 $ p $ 並獲得結果 $ 2^{192} - (2^{192} - 2^{64}-1) = 2^{64} + 1 $ .
現在考慮將數字分成兩部分，高部分和低部分。分隔線是 $ 2^{192} $ ，這樣您就可以將要減少的數字寫為 $ a*2^{192}+b $ .
現在，要執行歸約，您可以使用以下事實： $ a2^{192}+b \mod p = b+a(2^{64} + 1) \mod p $ 如果結果大於 $ 2^{192}-1 $ .
例如，讓我們採取 $ 2^{256} $ ，我們將其重寫為 $ 2^{64}*2^{192} $ 現在 $ 2^{64}2^{192} \mod p = 2^{64}(2^{64} + 1) = 2^{128}+2^{64} $ .
這同樣適用於 $ 2^320 $ , 改寫為 $ 2^{128}*2^{192} $ 現在 $ 2^{128}2^{192} \mod p = 2^{128}(2^{64} + 1) = 2^{192}+2^{128} $ 需要再次減少，因為它大於 $ p $ ， 所以 $ 2^{192}+2^{128} \mod p = 2^{128}+2^{64}+1 $ .
請注意，應進一步注意減少數量大於 $ p $ 但小於 $ 2^{192} $ . 例如號碼 $ \sum^{191}_{i=0}{2^i} $ 大於 $ p $ 但小於 $ 2^{192} $ 並且不能通過上述技巧正確減少（除非您將其重寫為 $ 2^{192} -1 $ ).