1.简单
用欧几里得算法求 gcd(738, 648)。
a = 738b = 648
gcd(738, 648) =
2.简单
用欧几里得算法求 gcd(918, 846)。
a = 918b = 846
gcd(918, 846) =
3.中等
求 15 模 37 的逆元:满足 0 < x < 37 且 15·x ≡ 1 (mod 37) 的数 x。
a = 15n = 37
15−1 mod 37 =
4.中等
解 42x ≡ 29 (mod 97)。给出满足 0 < x < 97 的解 x。
42x ≡ 29 (mod 97)
x =
5.困难
用反复平方法求 47133 mod 90。
a = 47k = 133n = 90
47133 mod 90 =
6.困难
用 RSA 公钥 (n, e) = (629, 5) 加密消息 m = 328。求密文 c。
n = 629e = 5m = 328
c =
答案
- 1. gcd(738, 648) = 18
- 2. gcd(918, 846) = 18
- 3. 15−1 mod 37 = 5
- 4. x = 3
- 5. 47133 mod 90 = 47
- 6. c = 575
完整分步解答:请在 examproblems.com 上练习本主题。