Modular-Arithmetic
解決給定的 mod 問題有多難
令 c = ab mod p
其中 p 是 n 位素數（例如 128 或 160 位素數）；a - 1 和 (p-1) 之間的隨機數；b - 1 和 (p-1) 之間的隨機數；
給定 c、a 和 p，計算 b 有多難？
很簡單，你只需使用擴展歐幾里得算法來計算 $ a^{-1} \pmod p $ . 然後你有 $ b \equiv ca^{-1} \pmod p $ .
請注意，由於 EEA 具有多項式複雜性，因此即使 $ p $ 非常大（例如，數万位）。
很簡單，不管位長 $ p $ . 你可以計算 $ b = c \cdot a^{-1} \mod p $ 直接地。 $ a^{-1} $ 存在並且可以直接從 $ a $ .