KMB, 28/11/99

M3/4P14 Elementary Number Theory—Problem Sheet 4

Some of this is assessed coursework. Please hand in solutions to the starred questions (i.e., to questions 2, 5, 9, 11, 12) at the end of the lecture on Thursday December 9th.

1) Here is how the RSA code is implemented “in practice”. First of all, let’s choose an “alphabet” of characters which we can encode. For simplicity, let’s just take our alphabet as being the letters A–Z, a “space”, a comma, a full stop and an exclamation mark. This alphabet has size 30. Now let’s number our alphabet thus: let’s set “space” = 0, A = 1, B = 2,…,Z = 26, comma = 27, full stop = 28 and exclamation mark = 29. Next we have to choose two large primes, and in practice we would choose these primes to have, say, 100 digits— but in this exercise we may as well choose some three-digit primes or else the whole thing will become a big mess of calculations.

So let’s choose p = 347 and q = 701. Their product, N, will be N = 243247. Also we have to choose an integer e prime to ϕ(N), and let’s choose e = 11 because it’s not too big. In fact, it seems that in practice, e doesn’t have to be taken very large, so e = 11 is fine.

Now we have a map (ℤ/Nℤ)^{×} → (ℤ/Nℤ)^{×}, defined by m ↦ m^{e} mod N. And of course, the whole point is that if I told you just N and e and m^{e}, you would (hopefully) not be able to work out m without first factoring N, which we think is hard (well, would be hard, if we had chosen 100 digit primes).

Now here’s an easy trick to actually encode messages: our alphabet has size 30, and 30^{3} < N < 30^{4}. So what we do is take our message, break it up into blocks of size 3, and use “base 30” to change each of these blocks into a number between 0 and 30^{3} − 1. For example, the block “THE” would become 20 × 30^{2} + 8 × 30 + 5 × 1, because T = 20, H = 8 and E = 5. We work out that 20 × 30^{2} + 8 × 30 + 5 × 1 = 18245.

So now we encode 18245 by raising it to the power e mod N. We get 149248. Now because N < 30^{4}, we can encode this as a 4-digit number in base 30. We get

149248 = 5 × 30^{3} + 15 × 30^{2} + 24 × 30 + 28,

which decodes to “EOX.”

Decoding is similar—break the message up into 4-letter combinations and then raise them to the power d, where d has been chosen such that de ≡ 1 mod ϕ(N). Note of course that the point is that to work out d, you have to know ϕ(N), and to work out ϕ(N), you have to factor N.

Of course, you can (and probably should) use a computer to do this question.

a) Use the set-up above to encode the word “WOMBAT”.

b) Find d such that de ≡ 1 mod ϕ(N).

c) Now decode the code you got in part (a) and check that you get your wombat back.

2^{∗}) Here is a more reasonable (i.e., you won’t need a computer to do it) RSA question. Using a calculator is fine, but why not keep your brains in trim by doing this question in your head?

Say you are told the pair (N, e) = (69, 5).

(a) Encode the number 3 using this pair.

(b) Crack the code by factoring N and working out d.

(c) Say you’ve intercepted the number 2 that has been sent using this code. Decrypt it using the d you have discovered in (b). Check your answer by encrypting what you get. [OK, so I used a calculator for this last part…]

3) Let p > 2 be a prime. Work out (notation as in lectures) a formula for r_{p}(−1) and check that the formula (−1)^{r_{p}(−1)} does indeed give (\frac{−1}{p}).

4)

a) Let p > 2 be a prime. Work out r_{p}(−2).

b) Recall that (\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p}). Check that indeed (−1)^{r_{p}(−2)} does equal

(\frac{−1}{p}) (\frac{2}{p}).

5^{∗})

a) Work out (\frac{7}{17}) by brute force—that is, work out all squares mod 17 and see if 5 shows up.

b) Work out (\frac{7}{17}) using the law of quadratic reciprocity (twice).

6)

a) Using whatever method you like, show that for p > 3 a prime, −3 is a square mod p if and only if p ≡ 1 mod 3.

b) Show that there are infinitely many primes congruent to 1 mod 3. [Hint: if there were only finitely many, multiply them together, square, and add twelve].

7)

a) How many non-zero squares are there mod 257?

b) How many primitive roots are there mod 257?

c) Use Euler’s criterion to show that an integer coprime to 257 is a square mod 257 if and only if it’s not a primitive root mod 257.

8) Let p be an odd prime and let a be an integer. Show that the number of solutions mod p to the equation

X^{2} ≡ a mod p

is 1 + (\frac{a}{p}).

9^{∗})

a) How many solutions does the equation X^{2} ≡ 3 have in ℤ/97ℤ?

b) How many solutions does X^{2} + X + 1 have in ℤ/13ℤ? Hint: Don’t use the formula for roots of a quadratic because we haven’t proved that it works in ℤ/pℤ. Just complete the square.

10) (for those of you who have done some group theory). Let p > 3 be a prime.

a) Using the fact that (ℤ/pℤ)^{×} is cyclic, work out a general formula for the number of solutions to X^{3} ≡ 1 in ℤ/pℤ. Your answer should depend on p mod 3.

b) Factor X^{3} − 1 and complete the square to deduce that if −3 is a square mod p, then p ≡ 1 mod 3.

c) Deduce that, for p > 3, we have that −3 is a square mod p if and only if p is a square mod 3.

11^{∗}) Let p be a prime with p ≡ 3 mod 4, and let q ≠ p be any odd prime. Show that

(\frac{−p}{q}) = (\frac{q}{p}) .

This is some kind of variant of quadratic reciprocity that is sometimes useful to know.

12^{∗}) Compute the Jacobi symbols (\frac{355}{113}), (\frac{123}{789}), and (\frac{34}{39}). Using a calculator to help is fine. Using results that we have proved in the course is fine. Using some Mathematica function that does this automatically for you is not at all fine.

Can you deduce, just from your answers, whether 355 is a square mod 113, whether 123 is a square mod 789, and whether 34 is a square mod 39?