Question 1.
(a) There are 8 points: (0,2), (0, 9), (2,0), (4,0), (5,0), (10, 3), (10, 8), O.
X	x3 + 5x + 4 mod 11	in Q^ll	y
0	4	/	(2,9)
1	10	X	
2	0	/	0
3	2	X	
4	0	/	0
5	0	/	0
6	8	X	
7	8	X	
8	a	X	
9	8	X	
10	10	/	(3,8)
Table 1: S.l.a
(b) What is the order of point P = (10,3)? Order k of point P is kP = 0.
• Eis non-singular: -16(4a3 + 2762) = -14912 ^ 0
• P is on E - see a).
• P • P = (xs,ys) = (5,0)
£3 = A2 — Xi — £2 = 5   mod 11 S/3 = A(a;i - 3:3) - 2/1 = 0   mod 11 . 2F + P = (t3,j/3) = (10,8)
A=^-^ = 5   mod 11 t2 - £1
£3 = A2 — £1 — xi = 10 mod 11 y:f = X(xi - S3) - yi = 8   mod 11
. 3P + P = (s3, J/3) = O
A = 3ft ~ i/i = 3-8 x2 - Xi     10 - 10
Order of point P = (10,3) is 4.
(c) P + P = O. When A is undefined.
• X\ = x-i but yi f y2
• P, = P2 but yi=0
Question 2.
(a) Factorize 3551, starting with xq = 2 and using pseudo-random function a:; + 1 = ar? + 3 mod 3551.
• Pollard's ^-method version 1. First factor is 53.
i	.1	Xj	x,	gcd(xt -xj,n)
2	1	52	7	1
3	1	2707	7	1
3	2	2707	52	1
4	1	2139	7	1
4	2	2139	52	1
4	3	2139	2707	1
5	1	1636	7	1
5	2	1636	52	3
5	3	1636	2707	1
5	4	1636	2139	i
6	1	2596	7	1
6	2	2596	52	53
Table 2: 8.2.a Pollard's ^method version 1
• Pollard's />method version 2. First factor is 53.
i	X	y	f)cd( \x - y |, 3551)
1	7		1
2	52	2139	1
3	2707	2596	1
4	2139	1 150	53
Table 3: 8.2.a Pollard's p-method version 2
(b) Pollard's p - 1 method, Factorize n = 178297- B - 23, a = 2.
m=     Yl     <Jl'ogajBJ = 24-32 ■ 51 ■ 71 ■ 11 ■ 13-17-19-23   mod 178297 = 148267
primes <v< B
gcd(2M - 1,178297) = gcd(165942,178297) = 7
First factor is 7. Question 3.
(a) Hash your UCO using a hash function h(x) = Fjx mod 1033 and label the result h.
h(x) = 5433fc2   mod 1033 = 1029 = h
(b) EC Elgamal signature scheme. E: y1 = x!i + 3a;+ 983 mod 997. Public points P = (325,345), Q = xP = (879,211) and secret key x = 140. Random component r = 339. Note that order of P hi E is 1034. Signed message (h, R, s) = (1029, (838,741), 511).
R = r ■ P = (838,741)
s = r-l(h - x ■ xR)   mod n = 973(1029 - 140 ■ 838)   mod 1034 = 511
Verification:
xRQ + sR = hP (815,880) + (248,445) = (569,100)/
Question 4.
Curve 1: y2 = x:i + ix. Has points: oo, (0,0),(1,0), (2,1), (2,4), (3,2), (3,3), (4,0). The sorted sequence of point orders is [1,2, 2,2,4,4, 4,4].
Curve 2: y2 = x* + ix + 1. Has points: oo, (0,1), (0,4), (1,1), (1,4), (3,0), (4,1), (4,4). The sorted sequence of point orders is [1,2, 4,4,8,8,8,8].
As the sorted sequences of point orders are different, the group structures are different.
8.5 Consider an elliptic curve E : y2 = x3 + 8 over R. Show that E docs not have multiple roots. Algebraically determine the number of roots E haw.
Solution: 0 = rr3 + 8 is equivalent to 0 = {x + 2)(j;2 — Ix 4- 4), therefore — 2 is a root, hut. not multiple root. Now wc calculate discriminant of quadratic equivalence 0 — x2 — 2x + 4:
D = (-2)2 -4- 1-4= -12.
We see that discriminant is < 0, therefore there is no more solution in R, but E has two more complex (non-real) conjugate solution (this means that it is not multiple solution). Therefore we prove that E does not have multiple root and have one root over M. □
Question 6.
(a) 5 points: ft is not possible for an elliptic curve over Zi j to have 5 points, because the lower bound according to Hesse's theorem is N > p —      + 1 > 11 — 6 + l>6
(b) 0 points: y2 = r'J + x + 8 mod 11 has 6 points: {(3, 4), (3, 7), (8, 0), (9, 3), (9, 8), oo}
(c) 14 points: y2 = T> + x + 1 mod 11 has 14 points: {(0, 1), (0, 10), (1, 5), (1, 6), (2, 0), (3, 3),
(3, 8), (4, 5), (4, 6), (6, 5), (6, 6), (8, 2), (8, 9), oo}
(d) 19 points: ft is not possible for an elliptic curve over Zn to have f9 points, because the upper bound according to Hesse's theorem is N < p + 2^/p + 1 < 11 + 6 + 1 < 18
8.7 Show that 42 | n7 - n for all integers n e N.
Solution: We know that n7 — n = n(ii3 — + 1) = (n — 1)ji(ti 4 — 714> + n-\-1). Now we prove three statements 2 | n7 — n. 3 | n7 — n and 7 \ n7 — n.
• 2 I n7 — n: We know that Vn : 2 | n(n +1), because n and n + 1 are consecutive numbers, therefore one of them is even. Therefore Vjt. : 2 | {n - l)n(n 4 1)("2 - ft + l)(rc2 + n + 1).
■ 3 I n7 — n: We know that Vn : 3 | (n —        + 1), because n — 1, n and ?i 4 1 are consecutive numbers, therefore one of them is divisible by 3. Therefore Vn ; 3 | (n - l)n(n + l)(n2 — n + l)(n2 + n + 1) +
* 7 I n7 - n: From the Format's Little Theorem we know that n6 — 1 mod 7     n7 — n mod 7 rjr — ji — 0 mod T- Therefore we show that Wt : 7 | n7 — n.
Finally we use Chinese Remainder Theorem for these three statements therefore we prove Vn : 42 | n7 — n. □
8.8 Recall the definition of a Fermat number:
Fn = 22" 4 1
where n is a non-negative integer. Prove the following claims:
(a) For n > 1, Fn = FG ■ ■ ■ Fn_i + 2.
Solution: Wc use mathematical induction: ■ Base step: n — 1 - We know that F$ — 3 and F\ — 5 and 5 — 3 + 2 therefore we prove that
/'i ~ iw - 2.
• Induction step: Let   be an integer > 1. The statements holds for n (Fn = Fq - ■ ■ Fn-j 4 2) and wc have to prove it for n 4- 1 (Fn+1 = F0 ■ ■ Fn 4 2).
Fn = Fv-Fn.1 + 2^=> Fn -2 = F0--Fn--l.
Fq - ■■ Fn + 2 = Fq - ■■ Fn—i ■ Fn + 2 = {FTt - 2)F7J 4 2
=        - l) (22" + l) +2
- (22")2-l + 2
= 2^+i + 1 = Fn+1
We prove Fn = F0 ■ ■ ■ Fn_i 4 2, □
(b) For n > % the last digit of Fn is 7. Solution: Wc use mathematical induction:
• Base step: n — 2 - F? — 17 so the statement is true.
• Induction step: Let n be an integer > 2. The statements holds for n (Fn = 7 mod 10) and wc have to prove it for n 4 L {Fn+i = 7 mod LÜ).
Fn = 7   mod 10       22?j 4 1 = 7   mod 10 ^ 22" = 6   mod 10. Fn+i = 22'L+' 4 1 = (22"Y 4 1 e 62 4 1 = 7   mod 10.
Therefore wc prove Fn = 7 mod 10 (last digit is 7), □ (<:) No Format number is a perfect square.
Solution: It is obvious that Fq = 3 and Fi — 5 are not perfect squares.
From part (b) wo know that Vn > 2 : Fn = 7 mod 10, so if any of Fermat numbers is perfect square (k2) then fc2 — Fn = 7 mod 10. All digits (we look only on last digit of k) have this last digit for k-2: 0, 1, 4, Gt 6, 5, 6, Q, 4, 1. Therefore Vfc : ft2 ^ 7 mod 10 therefore wc prove that no Fermat number is a. perfect square. Q
(d) Every Format number Fn for n > 1 has the form Gm — 1 for an integer m > 0.
Solution: The equivalent definition is G | Fn 4-1.
• 2 I Fn + 1: 2 I 22" +1 + 1, which is obviously true for all n > 1.
• 3 I Fj; 4 1- We want to show that Vtc > 1 : 22 + 1 | 1 e 0 mod 3 which is equivalent to Vn > 1 : 22t" = 1 mod 3.
22" - (22)2""1 - 4r'~J = I21'"' = 1   mod 3 Finally wc use Chinese Remainder Theorem for them therefore wc prove Vrc > 1 : 6 | Fn 4 1. □
Question 9.
To decrypt, calculate:
dR = (ci, c2) wil — j/i cjj~J   mod p "12 = 2/2^2 1   mod p
Since the encryptor used (ci,c2) = kQ, and Q — dP,R — kP, it holds (ci,c2) = kQ — kdP — dR. Thus the (01,02) obtained during decryption is the same as in encryption, thus we simply reverse the mod-multiplication by mod-multiplying by an inverse. Inverse is calculated easily, as p is a prime.