1.简单
用欧几里得算法求 gcd(77, 56)。
a = 77b = 56
gcd(77, 56) =
数论与模运算练习卷（附答案）
2.简单
用欧几里得算法求 gcd(583, 440)。
a = 583b = 440
gcd(583, 440) =
3.中等
求满足 x ≡ 5 (mod 6) 和 x ≡ 3 (mod 7) 的最小正整数 x。
x ≡ 5 (mod 6)x ≡ 3 (mod 7)
x =
4.中等
求 23 模 59 的逆元：满足 0 < x < 59 且 23·x ≡ 1 (mod 59) 的数 x。
a = 23n = 59
23−1 mod 59 =
5.困难
用 RSA 公钥 (n, e) = (1457, 17) 加密消息 m = 1397。求密文 c。
n = 1457e = 17m = 1397
c =
6.困难
某个 RSA 密钥使用 p = 13，q = 41，e = 23。解密密文 c = 229：求消息 m。
p = 13q = 41e = 23c = 229
m =
答案
- 1. gcd(77, 56) = 7
- 2. gcd(583, 440) = 11
- 3. x = 17
- 4. 23−1 mod 59 = 18
- 5. c = 345
- 6. m = 356
完整分步解答：请在 examproblems.com 上练习本主题。