一高中的高考模拟大题

这据说是河南一高中模拟考试的最后大题：

在密码学领域,欧拉函数是非常重要的,其中最著名的应用就是在RSA加密算法中的应用.设 p,q 是两个正整数,若 p,q 的最大公约数是1,则称 p,q 互素,对于任意正整数 n ,欧拉函数是不超过 n 且与 n 互素的正整数的个数,记为 φ(n).

(1)试求 φ(3),φ(9),φ(7),φ(21)的值;

(2)设 n 是一个正整数 p,q 是两个不同的素数,试求φ(3ⁿ), φ(pq)与 φ(p)和φ(q)的关系

(3)RSA算法是一种非对称加密算法,它使用了两个不同的密钥:公钥和私钥,具体而言:
①准备两个不同的、足够大的素数p,q;
②计算n=pq,欧拉函数 φ(n);
③求正整数k,使得kq除以φ(n)的余数是1;
④其中(n,q)称为公钥,(n,k)称为私钥.
已知计算机工程师在某 RSA 加密算法中公布的公钥是(187,17).若满足题意的正整数k从小到大排列得到一列数记为数列{b_n)，数列{c_n)满足80c_n=b_n十47,求数列{tanc_n·tanc_n+1}的前项和T_n

答案如下：

(1) 套公式：φ(p^k) = p^k – p^k-1 (p为质数，k为大于等于1的整数)

① φ(3)= 3¹ – 3⁰ = 3 – 1 = 2 (1,2)

② φ(9) = φ(3²) = 3² -3^2-1 = 9-3 = 6 (1,2,4,5,7,8)

③ φ(7) = 7¹ – 7⁰ = 7 – 1 = 6 (1,2,3,4,5,6)

④ φ(21) = φ(3*7) = φ(3) * φ(7) = 2 * 6 = 12 (1,2,4,5,8,10,11,13,16,17,19,20)

(2)

① φ(3ⁿ) = 3ⁿ – 3^n-1 = 3ⁿ(1-1/3)= 2 * 3^n-1

验证，如果n = 1, φ(3¹) = 2 * 3⁰ = 2

如果 n = 2, φ(3²) = 2 * 3^2-1 = 2 * 3¹ = 6

如果 n = 3, φ(3³) = 2 * 3^3-1 = 2 * 3² = 18 (1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26)

② φ(pq) = φ(p)* φ(q)

(3) 因为 n = 187, q = 17 得 p = 11

φ(187) = φ(17) * φ(11) = 16 * 10 = 160

求 b_n

17k % 160 ≡ 1

17k + 160y = 1

求两个数最大公约数的辗转相除法

160 / 17 = 9 … 7, 所以 7 = 160 – 17 * 9

17 / 7 = 2 … 3, 所以 3 = 17 – 7 * 2

7 / 3 = 2 … 1， 所以 1 = 7 – 3 * 2

所以 1 = 7 – 3 * 2 = 7 – (17 – 7 * 2) * 2

= 7 + 4 * 7 – 17 * 2 = 5 * 7 -17 * 2

= 5 * (160 – 17 * 9) -17 * 2 +

= 5 * 160 -17 * (2 + 45)

= 5 * 160 -17 * 47

得，5 * 160 – 17 * 47 = 1

得 y = 5, k = -47

要求k 是正整数，可以

-17 * 47 = 1 + (- 5 * 160)

两边加上 17 * 160

17 * (160 – 47) = 1 + (17 – 5) * 160

17 * 113 = 1 + 12 * 160

第一个 k值 是 113

求第二个k值，第一个k值 + φ(187) = 113 + 160 = 273

求第三个k值，是第二个k值 + φ(187) = 273 + 160 = 433

求第四个k值，是第三个k值 + φ(187) = 433+ 160 = 593

b_n = b_n-1 + 160

b_n = 113 + (n -1) * 160 = 160n – 47

求 c_n

c_n = (b_n + 47 = 160n – 47 + 47)/80 = 160n / 80 = 2n

求 T_n

tanc_n·tanc_n+1 = tan2n * tan2(n+1)

tan(2)= tan((2n+2)-2n)

tan(n) = tan[2(n+1)]−tan(2n)​/(1+tan[2(n+1)]tan(2n))

T_n​= tan[2(n+1)]−tan(2)​/(tan(2)−1)