MAT 3343, APPLIED ALGEBRA, FALL 2003

Answers to Problem Set 3 (due Oct. 10)

Problem 1 Suppose we want to encrypt “Applied Algebra”, or 0116; 1612; 0905; 0400; 0112; 0705; 0218; 0100. Each message M is encoded as C = M^{e}(mod 65). Exponentiation modulo 65 is easy to calculate by the method of repeated squaring, e.g. for M = 116, we have

M = 116
M^{2} = 116^{2} = 13456 = 1817 (mod 11639)
M^{4} = 13456^{2}  = 3301489 = 7652 (mod 11639)
M^{8} = 3301489^{2} = 58553104 = 8934 (mod 11639)
M^{16} = 58553104^{2} = 79816356 = 7733 (mod 11639)
M^{32} = 79816356^{2} = 59799289 = 9746 (mod 11639)
M^{64} = 59799289^{2} = 94984516 = 10276 (mod 11639)
M^{65} = 10276 · 116 = 1192016 = 4838 (mod 11639)

This method requires only about 8 digits of accuracy and can be done on a normal calculator. Of course, you could also calculate the exponentiation in a single step, and then reduce modulo 11639:

116^{65} = 154799409523344334074993461813540527506892338871507199

315763363264668645961962753402002709347078669374262285 069522260484535042730622976

= 4838(mod 11639)

However, this is more than most calculators can handle, and it is not very efficient computationally either.

The complete encryption of the above message is 4838; 5646; 6555; 8036; 2485; 10062; 6384; 11391.

Problem 2 We are given x ∈ ℤ_{N} such that x^{2} = x, thus x^{2} − x = 0, thus x(x − 1) = 0 in ℤ_{N}. This means that N|x(x − 1). On the other hand, x ≠ 0, 1, so N |̸x and N |̸(x − 1). Now consider a = gcd(N, x). Then a|N and a|x by definition of gcd. But we cannot have a = 1, or else N and x are relatively prime, and N|(x − 1) by Theorem 5(2), p.41. Also, we cannot have a = N, or else N|x. It follows that a is a non-trivial factor of N (and thus a prime factor, since N = pq is a product of two primes).

Problem 3 The generalized Chinese Remainder Theorem: Let n_{1}, …, n_{k} be integers such that gcd(n_{i}, n_{j}) = 1 for all i ≠ j, and let n = n_{1}n_{2} ⋯ n_{k}. Given integers a_{1}, …, a_{k}, there exists a unique a ∈ ℤ_{n} such that a ≡ a_{i}(mod n_{i}) for all i = 1, …, k.

Proof. Existence: By induction on k. If k = 1, there is nothing to show, and if k = 2, this is just the ordinary Chinese Remainder Theorem. For k > 2, let n′ = n_{1}n_{2} ⋯ n_{k−1}. By induction hypothesis, we can find a′ ∈ ℤ_{n′} such that a′ ≡ a_{i}(mod n_{i}) for all i = 1, …, k − 1. Now observe that gcd(n′, n_{k}) = 1, and use the ordinary Chinese Remainder Theorem to find a ∈ Z_{n} such that a ≡ a′(mod n′) and a ≡ a_{k}(mod n_{k}). Then a ≡ a_{i}(mod n_{i}) for all i = 1, …, k as required.

Uniqueness: Suppose a, a′ ∈ ℤ_{n} such that a ≡ a_{i}(mod n_{i}) and a′ ≡ a_{i}(mod n_{i}) for all i = 1, …, k. Then a ≡ a′(mod n_{i}) for all i, hence n_{i}|(a − a′) for all i, hence n_{1}n_{2} ⋯ n_{k}|(a − a′) (because all the n_{i} are relatively prime to each other, by repeated application of Theorem 5(1), p.41). Therefore a ≡ a′(mod n), so a = a′ in ℤ_{n}. □

Problem 4 (a) From the Chinese Remainder Theorem, we know that we can find elements a_{1}, …, a_{8} ∈ ℤ_{N} such that

a_{1} ≡ +1(mod p) a_{1} ≡ +1(mod q) a_{1} ≡ +1(mod r)
a_{2} ≡ +1(mod p) a_{2} ≡ +1(mod q) a_{2} ≡ −1(mod r)
a_{3} ≡ +1(mod p) a_{3} ≡ −1(mod q) a_{3} ≡ +1(mod r)
a_{4} ≡ +1(mod p) a_{4} ≡ −1(mod q) a_{4} ≡ −1(mod r)
a_{5} ≡ −1(mod p) a_{5} ≡ +1(mod q) a_{5} ≡ +1(mod r)
a_{6} ≡ −1(mod p) a_{6} ≡ +1(mod q) a_{6} ≡ −1(mod r)
a_{7} ≡ −1(mod p) a_{7} ≡ −1(mod q) a_{7} ≡ +1(mod r)
a_{8} ≡ −1(mod p) a_{8} ≡ −1(mod q) a_{8} ≡ −1(mod r)

Clearly, each such element satisfies a_{i}^{2} ≡ 1 modulo p, q, r, and thus modulo N; thus, each a_{i} is a square root of unity. On the other hand, any square root of unity b in ℤ_{N} must also be a square root of unity in ℤ_{p}, ℤ_{q}, and ℤ_{r}, and must therefore satisfy b ≡ ±1 modulo p, q, r, and must thus be one of the a_{i}. Finally, all the a_{i} are different, since +1 ≠ −1 modulo an odd prime. Therefore, there are precisely 8 square roots of unity.

(b) The Chinese Remainder Theorem, along with the equations in part (a), allows us to compute a_{1}, …, a_{8} efficiently.

(c) To compute this efficiently, we first compute the solutions x, y, z to the following equations:

x ≡ 1(mod 7) x ≡ 0(mod 11) x ≡ 0(mod 13)
y ≡ 0(mod 7) y ≡ 1(mod 11) y ≡ 0(mod 13)
z ≡ 0(mod 7) z ≡ 0(mod 11) z ≡ 1(mod 13)

This can be done by Euclid’s algorithm, and we find x = −286, y = 364, and z = −77. Then a_{1}, …, a_{8} can be rapidly computed in this basis:

\begin{aligned}a_{1} & = & x + y + z & = & 1 \\ a_{2} & = & x + y − z & = & 155 \\ a_{3} & = & x − y + z & = & −727 \\ a_{4} & = & x − y − z & = & −573 \\ a_{5} & = & −x + y + z & = & 573 \\ a_{6} & = & −x + y − z & = & 727 \\ a_{7} & = & −x − y + z & = & −155 \\ a_{8} & = & −x − y − z & = & −1 \end{aligned}

(d) Let x be a square root of unity in ℤ_{N} with x ≠ ±1. Then x^{2} = 1 in ℤ_{N}, thus N|(x − 1)(x + 1). Let a = gcd(x + 1, N). Then a|N. We cannot have a = 1, or else x + 1 and N are relatively prime, thus N|(x − 1), contradicting x ≠ 1(mod N). On the other hand, we cannot have a = N, or else N|(x + 1), contradicting x ≠ −1(mod N). Thus, a is a non-trivial factor of N. Since N = pqr is the product of three primes, either a or N/a is prime, thus we have found one of the prime factors of N. We cannot do any better with the given information.

Problem 5 (a) This problem is most fun (and most realistic) if we actually pick random numbers b ∈ {1, …, 118} to do the test.

Random number: Test:  Result:
b = 74  b^{118} = 25(mod 119) fail

The test has already failed on our first random choice of b. Therefore, 119 is not prime. In order not to spoil our fun, we continue testing some more numbers:

Random number: Test:  Result:
b = 77  b^{118} = 21(mod 119) fail
b = 109  b^{118} = 60(mod 119) fail
b = 102  b^{118} = 102(mod 119) fail

As we can see, the probability of failing the test seems to be very much in our favor; indeed we did not find any b which passed the test.

(b) Again, we pick our candidates b ∈ {1, …, 560} at random. Note that 560 = 2^{4} · 35. All calculations are modulo 560.

b (random) b^{35} b^{70} b^{140} b^{280} b^{560} Result:
344 353 67 1 1 1 fail
297  495 429 33 528 528 fail
300  243 144 540 441 375 fail
224 452 100 463 67 1 fail
468  219 276 441 375 375 fail
545  494 1  1  1  1  fail

Again, the test failed with the first random number we picked; we could have stopped right there. (We continued just for the fun of it). Again, the odds seemed to be heavily stacked in our favor, as we could not in fact find any b which passed the test in the first 6 trials.

Note that 3 of our 6 random number would have passed the Fermat pseudoprime test.