## Math 312 Practice Problems for Test 3

MPRRW GMIOP MSNYS RYRAZ PXMCD WPRYE YXD 使用仿射传输加密

aP + b (mod 26) 后跟变换 C cP + d (mod 26) 我们假设
gcd(a; 26) = 1 and gcd(c; 26) = 1。乙； C; d 出现在里面。

(mod ni) 对于 i = 1; 2; 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 ﬁnitely 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 afﬁne 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 ﬁrst 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 ﬁnal 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.