Complete the encryption of cryptonomicon find all solutions

Question

Number Theory

What you will learn about in this tutorial:

1. Polynomial Congruences

2. Systems of Linear Congruences

3. Hill ciphers

Polynomial Congruences

In section 4.3, exercise 36, we were able to solve the congruence x² + 6x - 31 ≡ 0 (mod 72).  (We discovered that there were 4 congruence classes that gave solutions: 13, 17, 49, and 53.) We first noted that 72 = 2³3² = 8.9. Then we solved x² + 6x - 31 ≡ 0 (mod 8) and x² + 6x - 31 ≡ 0 (mod 9) by trial and error and pieced together those solutions using the Chinese Remainder Theorem.

This strategy can be generalized. Here is what we discovered:

Suppose that f(x) is a polynomial with integer coefficients and m is a positive integer with prime-power factorization m = p₁^a₁p₂^a₂···p_k^a_kl. In order to solve the polynomial congruence f(x) ≡ 0 (mod m) we could do the following:

1. For each i find all solutions to f(x) ≡ 0 (mod p_i^a_i).

2. For every combination of integers r₁, r₂,...., r_k such that, for each i,  f(r_i) ≡ 0 (mod p_i^a_i) use the Chinese Remainder Theorem to find x so that, for each i, x ≡ r_i (mod p_i^a_i). The congruence class mod mofx will be unique and a different combination of  r₁, r₂,...., r_k will result in a different mod m congruence class.

What if there are no solutions to one of the congruences?

Exercise 1:  Prove that if, for some i, f(x) ≡ 0 (mod p_i^a_i) has no solutions, then  f(x) ≡ 0 (mod m) has no solutions.

Let's illustrate the technique with a relatively simple example.

Exercise 2: Find all integer solutions to x² - 10x + 24 ≡ 0 (mod 35) by using the above steps. (Hint: There should be 4 congruence classesmod 35 that are solutions.)

We see from this that solving a general polynomial congruence can be reduced to solving congruences of the form f(x) ≡ 0 (mod p^a) where p is a prime. In the case of x² + 6x - 31 ≡ 0 (mod 72) we could do this relatively easily by just plugging in all possibilities, but there are two difficulties with this.

Many of you discovered the first problem the hard way. It is that, even if you can factor the polynomial, since arithmetic mod p^a does not have the "zero product" property, you can't get all solutions just by looking at the factors. (Recall that we found that, even though x² + 6x - 31 ≡ x² + 6x - 7 ≡ (x -1) (x +7) (mod 8),  we could not conclude that the only solutions mod 8 were 1 and -7 (which actually represent the same congruence class). 5 was another solution even though 5 is neither a solution to x - 1 ≡ 0 (mod 8) or (x +7) ≡ 0 (mod 8) because (5 - 1) (5 + 7) ≡ 0 (mod 8).)

The second problem is that powers of primes can get pretty large even if the primes themselves are relatively small. And, when the numbers get large, solution by trial and error becomes impractical.

It turns out that we can go even further and reduce the problem to that of solving congruences of the form f(x) ≡ 0 (mod p) where p is a prime number. In this setting we do have the zero product property.

Exercise 3: Suppose that f(x), g(x), and h(x) are polynomials with integer coefficients such that  f(x) = g(x) h(x). Suppose that p is a prime number and r is an integer such that  f(r) ≡ 0 (mod p). Then prove that g(r) ≡ 0 (mod p) or h(r) ≡ 0 (mod p).

Exercise 4: Use the result of exercise 3 above to prove that the only solutions to x² - 16x + 2 ≡ 0 (mod 37) are  x ≡ 3 (mod 37) or x ≡ 13 (mod 37) . (Hint: Note that 2 ≡ 39 (mod 37) .)

Let's see how this works by looking at an example. We want to find all solutions to x² + 8x +8 ≡ 0 (mod 875). The first step is to find the prime-power factorization of 875 and we readily see that 875 = 5³·7. Next we want to solve x² + x + 8 ≡ 0 (mod 7) and x² + x + 8 ≡ 0 (mod 5³). I'll let you do the easy one.

Exercise 5: Find all the solutions to x² + x + 8 ≡ 0 (mod 7).

Now we want to solve x² + x + 8 ≡ 0 (mod 5³) and we would like to do it without testing out all 125 possible congruence classes. We begin by solving x² + x + 8 ≡ 0 (mod 5). We could either do it by trial and error or we could observe that

x² + x + 8 ≡ x² + x +3 ≡ x² + x - 2 ≡ (x +2) (x - 1) (mod 5)

Therefore the two solutions are x ≡ 1 (mod 5) or x ≡ -2 ≡ 3 (mod 5). More generally, any integer of the form x ≡ 1 + 5t or x ≡ 3 + 5t will be a solution to x² + x + 8 ≡ 0 (mod 5). Our strategy now will be to "lift" these solutions to solutions of x² + x + 8 ≡ 0 (mod 5²). I will do one and let you do the other one.

Let's look at x ≡ 1 + 5t. We want to choose t so that x is a solution to x² + x + 8 ≡ 0 (mod 5²). We substitute it in to get

(1 + 5t)² + (1 + 5t) + 8 ≡ 1 + 10t + 25t² + 1 + 5t + 8 ≡ 10 + 15t (mod 5²)

(Notice that we eliminated the 25t² term because it was 0.)

We want to choose t so that 10 + 15t ≡ 0 (mod 5²) or so that 15t ≡ -100 (mod 5²) ⇒ 3t ≡ -2 (mod5) (We used Theorem 4.5) This means that t ≡ 1 (mod 5²). We have now found that  x ≡ 1 + 5 (1) ≡ 6 (mod 5²) is a solution to x² + x + 8 ≡ 0 (mod 5²). 

Exercise 6: Do the same with the other solution to x² + x + 8 ≡ 0 (mod5). Find t so that x = 3 + 5t is a solution to x² + x + 8 ≡ 0 (mod5²).

But remember that we were actually wanting solutions to x² + x + 8 ≡ 0 (mod 5³) (so that we could put them together with our solutions to x² + x + 8 ≡ 0 (mod 7) to get solutions to x² + x + 8 ≡ 0 (mod 875).)  We will do it one more time!

We now know that x ≡ 6 (mod 5²) is a solution to x² + x + 8 ≡ 0 (mod 5²). So, for any integer u, x = 6 +5² u will be a solution. We now want to choose u so that x is a solution to x² + x + 8 ≡ 0 (mod 5³). Substituting in, we get

(6 +5² u)² + (6 + 5² u) + 8 ≡ 36 + 300 u + 625 u² + 25 u ≡ 50 + 325 u ≡ 50 + 75 u (mod 5³)

So we want 50 + 75u ≡ 0 (mod 5³) ⇒ 75u ≡ - 50 (mod 5³) ⇒ 3u ≡ -2 (mod 5).

The solution is u ≡ 1 (mod 5). Therefore, x = 6 + 5² (1) = 31 is a solution to x² + x + 8 ≡ 0 (mod 5³).

Exercise 7: Use your solution to Exercise 6 to get another solution to x² + x + 8 ≡ 0 (mod 5³).

Exercise 8: Use your solution to x² + x + 8 ≡ 0 (mod 5³) from Exercise 7 together with my solution of x = 31 together with your solution to Exercise 5 to generate all solutions to x² + x + 8 ≡ 0 (mod 875).

Here is the general technique to "lift" a solution mod p^k-1 to a solution mod p^k

Suppose that you have an integer r that satisfies f(r) ≡ 0 (mod p^k-1). 

1. Compute f(r + tp^k-1) ≡ 0 (mod p^k).

2. You will  get p^k-1 f'(r) t + f(r) (Where f' (r) is the derivative of the polynomial evaluated at r. )

3. Choose t so that p^k-1 f'(r) t + f(r) ≡ 0 (mod p^k)or, in other words, so that f'(r) + f(r) / p^k-1 ≡ 0 (mod p).  (Note that, since f(r) ≡ 0 (mod p^k-1), f(r) / p^k-1 is an integer.) You can do this as long as f'(r) ≡ 0 (mod p).

4. r + tp^k-1 will be your solution.

Systems of Linear Congruences

As we have seen before, when working in modular arithmetic, we can often use the same techniques that have been successful in the real numbers, as long as we are careful. Two differences that we have observed are (1) unless the modulus is prime you can't assume that the product of two nonzero congruence classes is nonzero and (2) you can't divide-although you can accomplish the same result by multiplying by the multiplicative inverse if there is one.

Let's see how this works in solving systems of linear congruences. We will begin, as usual, with an example.

Suppose that we want to find all integers x and y such that

2x + 3y ≡ 4 (mod 17)

5x + 4y ≡ 24 (mod 17)

There are many techniques for solving a system like this in the real numbers. We can solve it by substitution, by elimination, or we can use matrices. The same thing holds true for modular arithmetic. The only difference is that, if we ever need to divide by a number, we should instead multiply by the multiplicative inverse mod 17. Let's illustrate the three techniques:

Substitution

The idea here is to solve one of the equations for one of the variables and substitute it into the other. For example, we could write the first equation as

3y ≡ -2x + 4 (mod 17)

then multiply both sides by the multiplicative inverse of 3, which is 6, to get

y ≡ -12x + 24 ≡ 5x + 7 (mod 17)

Substituting that into the second equation gives

5x + 4 (5x +7 ) ≡  2 (mod 17) 

which simplifies to

8x ≡ 8 (mod 17) or x ≡ 1 (mod 17)

We now substitute that back into the equation y ≡ 5x + 7 (mod 17) to find that  y ≡ 12 (mod 17)

Exercise 9: Use substitution to solve the same system by solving the first equation for x instead of for y.

Elimination

We will solve the same system:

2x + 3y ≡ 4 (mod 17)

5x + 4y ≡ 2 (mod 17)

Noticing  that 2·11 ≡ 5 (mod 17) we multiply the first equation on both sides by 11 to get

5x + 33y ≡ 44 (mod 17)

5x + 4y ≡ 2 (mod 17)

Now we subtract the second equation from the first to eliminate the x terms to get

29 y ≡ 42 (mod 17)   or  12y ≡ 8 (mod 17)

We note that the multiplicative inverse of 12 is 10 mod 17, so

Y ≡ 80 ≡ 12 (mod 17)

We can now substitute y = 12 into either equation and solve to find that x ≡ 1 (mod 17).

Exercise 10: Use elimination to solve the same system by eliminating the y terms.

Matrices

First let's quickly review the rules of matrix multiplication-at least for the 2 by 2 case.1. Given matrices

and

, we define the product AB by

2. We can easily check that if

, then, for any matrix A we have that A · I = I · A = A so I is the multiplicative identity for matrix multiplication.

3. A multiplicative inverse for the matrix A is a matrix A^-1 such that A · A^-1 = A^-1· A = I.

Not every matrix has a multiplicative inverse. If we let Δ = ad - bc then the matrix

will have an inverse if and only if Δ ≠ 0 and, in that case, the inverse is given by the formula

4. Matrix multiplication is associative, meaning that, for any matrices A, B, and C, (AB)C = A(BC). But it is not commutative, meaning that for some matrices A and B, AB ≠ BA.

Furthermore, if

we can multiply A by the 2 x 1 matrix

to get

.

The good news is that all of this carries over to modular arithmetic with one slight modification and that modification occurs to number 3 above.  We just need to understand that, by Δ^-1, we mean the multiplicative inverse of Δ  and that the requirement of Δ ≠ 0 should be replaced with the requirement that Δ has a multiplicative inverse.

Exercise 11:Let

. Find A^-1 mod 7. (In other words, find a matrix with integer values so that the product matrix with A is congruent to the identity matrix mod 7)

Now that we know how to work with matrices let's revisit out system of equations

2x + 3y ≡ 4 (mod 17)

5x + 4y ≡ 2 (mod 17)

To solve it, we write it in matrix form as

Note that, if

, then Δ = 2 (4) - 3 (5) = -7 ≡ 10 (mod 17). Then Δ^-1 ≡ 12 (mod 17) so

and

Therefore

The solutions are the congruence classes corresponding to x = 1 and y = 12.

Exercise 12: Use matrices to solve the system

2x + 3y ≡ 4 (mod 17)

5x + 4y ≡ 2 (mod 17)

Cryptography

As we have discovered before a single substitution cipher is vulnerable to frequency analysis which uses the fact that certain letters of the alphabet occur more frequently than others. We can make this more difficult by grouping words into blocks of letters and encrypting each of those blocks. One of the ways of doing this is the Hill Cipher in which the key is a matrix and the encryption procedure is to multiply an appropriately sized block by that matrix. To illustrate this we will begin with the usual assignment of numbers to characters.

A	B	C	D	E	F	G	H	I	J
00	01	02	03	04	05	06	07	08	09

K	L	M	N	O	P	Q	R	S	T
10	11	12	13	14	15	16	17	18	19

U	V	W	X	Y	Z		.	,	?	!
20	21	22	23	24	25	26	27	28	29	30

 

Now suppose that we want to encrypt the message

CRYPTONOMICON

(Cryptonomicon is a novel about cryptography by Neal Stephenson.) We want to encrypt using the matrix

as the key. To prepare it for encryption we divide our message up into blocks of 2 (called digraphs)

CR YP TO NO MI CO NX

(We added the dummy letter X on the end so that we could break it up into digraphs.) Now we convert each pair of letters into a pair of numbers

, etc.

Exercise 12: Finish the conversion.

Then we encrypt each of the pairs by multiplying by our encryption matrix and reducing mod 31. I will do the first two and you can do the rest

and

So the first 4 letters of the encrypted message would be PSXP.

Remember that you can create a function on your calculator that will find the remainder mod 31. You use the greatest integer function.

x - int (x/31)·31

Exercise 13: Complete the encryption of CRYPTONOMICON. (Convert the encrypted message into letters.)

Exercise 14: The same encryption matrix

was used to encrypt another message. The encrypted message is

YDE.WBKW!C

Decrypt the message. (Hint: The inverse would be helpful here.)

Assignment: After completing the above read 4.4, and 4.5 of the text. You are responsible for 4.4: (1,2,5,6),  4.5:(1,2,4,8,9,10) but you only need to turn in the exercises on the following pages.

Section 4.4, #2: Find all solutions of each of the following congruences,

(a) x³ + 8x² - x - 1 ≡ 0 (mod 11)

(b) x³ + 8x² - x - 1 ≡ 0 (mod 121)

(c) x³ + 8x² - x - 1 ≡ 0 (mod 1331)

Section 4.5, #2:Find the solutions of each of the following congruences.

(a) 2x + 3y ≡ 5 (mod 7)

x + 5y ≡ 6 (mod 7)

(b) 4x + y ≡ 5 (mod 7)

x + 2y ≡ 4 (mod 7)

Section 4.5, #8:Find an inverse modulo 5 of each of the following matrices.

(a)

(b)

(c)

Section 4.5, #9(a):  Find an inverse modulo 7 for:

You can check your answer in the back of the book, but you should show your work.

Section 4.5, 10(a): Using exercise 9 find all the solutions of the following system.

x + y ≡ 1 (mod 7)

x + z ≡ 2 (mod 7)

y + z ≡ 3 (mod 7)