# Hints for exercises

### 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.