本次加拿大代写是一个数论相关的限时测试的练习题
Math 312 Practice Problems for Test 3
关于符号的提示：N = f1; 2; 3; :::g 表示所有正整数的集合。
问题 1. 证明 (n) pn
每 n 2 N 2。
问题 2. 让 k 2 N。证明方程 (n) = k 只有有限多个解 n 2 N。
问题 3. 找出所有正整数 n 使得 (n) j n。
问题 4. 证明不存在模 12 的原始根。
问题 5.（Rosen，第 8.1 节中的问题 12）消息MJMZK CXUNMGWIRY VCPUW
MPRRW GMIOP MSNYS RYRAZ PXMCD WPRYE YXD 使用仿射传输加密
地层 C aP + b (mod 26)。使用字母的频率来确定值 a 和 b。什么
是明文消息吗？
问题 6.（Rosen，第 8.1 节中的问题 16）给定两个密码，可以加密明文
首先使用其中一个密码，然后在此结果上使用另一个密码。这个程序
产生乘积密码。找到使用变换 C 获得的乘积密码
aP + b (mod 26) 后跟变换 C cP + d (mod 26) 我们假设
gcd(a; 26) = 1 and gcd(c; 26) = 1。乙； C; d 出现在里面。
问题 7. 使用 Fermat 的分解方法分解 n = 9313。
问题 8.（Rosen，第 8.4 节中的问题 14）证明如果使用加密指数 3
对于三个不同模数的不同人的 RSA 密码系统，一条明文消息 P
可以从这三个密文消息中恢复使用他们的每个密钥加密的密码。
这是 Hastad 广播攻击的一个示例。
提示：假设这三个键中的模数是 n1、n2 和 n3。首先找到一个通用的解决方案
到同余 xi P3
(mod ni) 对于 i = 1; 2; 3.
问题 9. 设 p 为素数，设 a 为整数，满足 ordp(a) = 3。证明
a2
+ a + 1 0 (mod p)
Reminder about the notation: N = f1; 2; 3; :::g denotes the set of all positive integers.
Problem 1. Prove that (n) pn
2 for each n 2 N.
Problem 2. Let k 2 N. Show that the equation (n) = k has only finitely many solutions n 2 N.
Problem 3. Find all positive integers n such that (n) j n.
Problem 4. Show that there are no primitive roots modulo 12.
Problem 5. (Rosen, Problem 12 in Section 8.1) The messageMJMZK CXUNMGWIRY VCPUW
MPRRW GMIOP MSNYS RYRAZ PXMCD WPRYE YXD was encrypted using an affine trans-
formation C aP + b (mod 26). Use frequencies of letters to determine the values a and b. What
is the plaintext message?
Problem 6. (Rosen, Problem 16 in Section 8.1) Given two ciphers, plaintext may be encrypted
by first using one of the ciphers, and then using the other cipher on this result. This procedure
produces a product cipher. Find the product cipher obtained by using the transformation C
aP + b (mod 26) followed by the transformation C cP + d (mod 26) where we assume that
gcd(a; 26) = 1 and gcd(c; 26) = 1. The final answer you obtain may have a; b; c; d appearing in it.
Problem 7. Use Fermat’s factorization method to factor n = 9313.
Problem 8. (Rosen, Problem 14 in Section 8.4) Show that if the encryption exponent 3 is used
for the RSA cryptosystem by three different people with different moduli, a plaintext message P
encrypted using each of their keys can be recovered from these resulting three ciphertext messages.
This is an example of a Hastad broadcast attack.
Hint: Suppose that the moduli in these three keys are n1, n2, and n3. First find a common solution
to the congruences xi P3
(mod ni) for i = 1; 2; 3.
Problem 9. Let p be a prime number, and let a be an integer such that ordp(a) = 3. Prove that
a2
+ a + 1 0 (mod p)