Problem 9: Linear Diophantine Equations (3.13.1)

(a) This problem can be directly solved by using the extended Euclidean algorithm or just the basic Euclidean algorithm as follows:

(b) From (a), we immediately know 17^-1 (mod 101) ≡ 6.

Problem 10: Euclidean Algorithm (3.13.5)

(a) Using Euclidean algorithm, we have

(b) From (a), fortunately 257 is a prime itself. So 4883 = 257 * 19 and 4369 = 257 * 17.

Problem 11: Quadratic Diophantine Equation (3.13.8)

The conclusion of 7(a) needs to be proved first if used in this problem, and that p is a prime is definitely a necessary condition which must be used in the proof.

Now we prove 7(a) first.

7(a) Let p be prime. Suppose a and b are integers such that ab ≡ 0 (mod p). Show that either a ≡ 0 or b ≡ 0 (mod p).

Proof : Since ab ≡ 0 (mod p), we have p∣ab. Since p is prime, we obtain that either p∣a or p∣b holds and is also necessary for p∣ab. So either a ≡ 0 or b ≡ 0 (mod p) holds and is necessary and also obviously sufficient.

Coming back to our problem, we know that p is a prime and x² ≡ 1 (mod p). We rewrite the above equation to x² - 1 ≡ (x + 1)(x - 1) ≡ 0 (mod p). From the conclusion of 7(a), we get that either x + 1 ≡ 0 (mod p) or x - 1 ≡ 0 (mod p) holds and is necessary and sufficient for (x + 1)(x - 1) ≡ 0 (mod p). Since p ≥ 3, x ≡±1 (mod p) are two different solutions and also the only solutions because they are necessary and sufficient for the problem.

Problem 12: Chinese Remainder Theorem (3.13.10)

This problem can be formatted into a remainder problem as the following:

Following the procedure of Exercise 24, we can solve the above problem as the following:

and

So we have x = 1 * y₁ * z₁ + 2 * y₂ * z₂ + 3 * y₃ * z₃ = 238. To get the smallest solution, we obtain 238 ≡ 58 (mod 3 * 4 * 5), and the next solution is 58 + (3 * 4 * 5) = 118.

Problem 13: RSA Encryption (6.8.2)

(a) Since φ(n) = (5 - 1) * (11 - 1) = 40, we just simply calculate the inverse of e as d ≡ e^-1 ≡ 27 (mod φ(n)) using extended Euclidean algorithm.

(b) We try to prove a more general case that if c ≡ m^e (mod n), then m ≡ c^d ≡ m^ed (mod n) in which gcd(m,n) = 1. From (a), we know that ed ≡ 1 (mod φ(n)), so ed = 1 + k * φ(n), in which k is an integer. So we obtain that m^ed ≡ m^1+k*φ(n) ≡ m * m^k*φ(n) (mod n). From Euler’s theorem, we know that if gcd(m,n) = 1, m^φ(n) ≡ 1 (mod n). So m^k*φ(n) ≡ 1 (mod n) and m * m^k*φ(n) ≡ m (mod n) and the proposition is proved.

Problem 14: RSA Attack (6.8.3)

We know c = 75, e = 3 and n = 437, so just try possible plaintext 8 and 9. And we get 8³ ≡ 75 (mod 437), so 8 is the plaintext.

Problem 15: RSA Decryption Exponent (6.8.5)

Assume e0 and ep- 1 since it is ’suitably chosen’, otherwise, y will be a constant independent of x and then there is no hope for us to recover x. Now we need to find d so that y^d ≡ x^ed ≡ x (mod p). According to Fermat’s Little Theorem, we know that if ed ≡ 1 (mod (p - 1)), then x^ed ≡ x (mod p) which satisfies our requirement. So we can let d = e^-1 (mod (p - 1)) if e^-1 (mod (p - 1)) does exist.

Problem 16: Factoring (6.8.12)

From the problem, we have