Hints for exercises
Exercise set 7 and later
Exercise set 5
6.13
(a) can be a bit tricky. Hasse's theorem along with Theorem 6.1 gives 11 possible candidates, which is way to much. There are two main strategies you can follow:
1. Compute all the points. It's a small curve anyway. Remember to include the point at infinity.
2. We want to find all solutions of the equation \(y^2 = x^3 + x + 28\). For each x, we can have a look at the Jacobi symbol (MA1301 or Tueday's lecture)
\[ \left(\frac{x^3 + x + 28}{71}\right) \]
If the symbol is 0, then we have found a root, so y is 0. If it is 1, then there are solutions to the relevant equation, and there are two solutions, y and -y. Finally, if the symbol is -1 if there exists no solutions. Including the point at infinity, we are therefore interested in the sum
\[\#E = 1 + \sum_{x \in \mathbb{Z}_{71}} \left(1 + \left(\frac{x^3 + x + 28}{71}\right) \right)\]
However, this sum is tricky to compute. Note that 28 + 43 is 0, so we add 43 on both sides of the defining equation. If 43 is a square (show it!), then we have the equivalent curve \(\left(y^\prime\right)^2 = x^3 + x\). Let \(f(x) = x^3 + x\). You can then show that \(\left(\frac{f(x)}{71}\right) = -\left(\frac{f(-x)}{71}\right)\). Use the fact that \(\left(\frac{-1}{71}\right) = -1\). This paragraph turns out to contain a rookie error. It's left for shame, but use the first strategy.
This will give rise to a similar sum as above. Show that the sum of all the Jacobi symbols is 0, and hence that the number of points is 72.
Note: This was the easiest mathematical solution we could find. Any suggestions for better solutions are highly appreciated!
1.21d
A: 17 23:S B: 17 23:L C: 18 22:Y D: 9 21:V E: 20 21:M F: 17 20:E G: 16 18:C H: 16 17:F I: 16 17:B J: 12 17:A K: 13 16:I L: 23 16:H M: 21 16:G N: 5 15:R O: 7 13:K P: 8 12:U Q: 6 12:T R: 15 12:J S: 23 11:W T: 12 9:X U: 12 9:D V: 21 8:P W: 11 7:Z X: 9 7:O Y: 22 6:Q Z: 7 5:N
There is no strong pattern. Which cipher is most likely used? Points at Vigenère. Key: THEORY.
1.21b
You might want to look for HJV. Key length: 6. Key: CRYPTO.
2: ['0.038', '0.047'] 3: ['0.056', '0.048', '0.048'] 4: ['0.037', '0.043', '0.038', '0.049'] 5: ['0.043', '0.043', '0.033', '0.035', '0.043'] 6: ['0.063', '0.084', '0.049', '0.065', '0.043', '0.073'] 7: ['0.031', '0.044', '0.043', '0.041', '0.044', '0.044', '0.041'] 8: ['0.033', '0.041', '0.034', '0.041', '0.039', '0.045', '0.041', '0.055'] 9: ['0.051', '0.043', '0.064', '0.075', '0.041', '0.035', '0.044', '0.048', '0.042'] 10: ['0.041', '0.043', '0.036', '0.039', '0.032', '0.045', '0.034', '0.028', '0.030', '0.049'] 11: ['0.034', '0.056', '0.043', '0.034', '0.030', '0.037', '0.039', '0.060', '0.062', '0.032', '0.039'] 12: ['0.071', '0.069', '0.048', '0.066', '0.040', '0.063', '0.063', '0.111', '0.042', '0.045', '0.034', '0.071'] 13: ['0.058', '0.040', '0.052', '0.037', '0.031', '0.034', '0.037', '0.031', '0.055', '0.055', '0.043', '0.028', '0.043'] 14: ['0.023', '0.036', '0.040', '0.047', '0.051', '0.054', '0.043', '0.040', '0.036', '0.054', '0.040', '0.051', '0.051', '0.036'] 15: ['0.040', '0.071', '0.040', '0.036', '0.051', '0.055', '0.063', '0.022', '0.026', '0.069', '0.035', '0.043', '0.048', '0.022', '0.061']
1.21a
A: 5 37:C B: 0 24:G C: 37 20:S D: 8 18:K E: 12 15:Y F: 9 15:I G: 24 14:U H: 5 13:Z I: 15 13:N J: 7 12:E K: 18 10:O L: 7 9:F M: 5 8:D N: 13 7:X O: 10 7:L P: 6 7:J Q: 1 6:P R: 0 5:W S: 20 5:M T: 0 5:H U: 14 5:A V: 0 1:Q W: 5 0:V X: 7 0:T Y: 15 0:R Z: 13 0:B ZC: 7 CG: 7 NC: 5 CN: 5 CK: 5 AC: 5 CY: 4 XC: 3 IC: 3 CJ: 3 CI: 3 CC: 3 UC: 2 JC: 2 CS: 2 CF: 2 YC: 1 SC: 1 OC: 1 HC: 1 FC: 1 EC: 1 DC: 1 CZ: 1 CU: 1 CO: 1
FZCCNDGYYSF occurs twice, so it might be a word. A dictionary search suggests that it could be WHEELBARROW.