Homework 6 7 Xuenan Xu.md

Homework 6 & 7

by Xuenan Xu GWID G26980825

 

1

a)

y2	1	4	9	16	25	36	49	64	81
mod 19	1	4	9	16	6	17	11	7	5

y2	100	121	144	169	196	225	256	289	324
mod 19	5	7	11	17	6	16	9	4	1

So the quadratic residues of Z₁₉ is 1, 4, 9, 16, 6, 17, 11, 7 and 5.

b)

• 5^{(7 - 1)/2} = 6 mod p, so 5 is not a quadratic residue of 7
• 4^{(8 - 1)/2} = 0 mod p, so 4 is not a quadratic residue of 8
• 6^{(15 - 1)/2} = 6 mod 16, so 6 is a quadratic residue of 15
• 13^{(17 - 1)/2} = 1 mod 17, so 13 is a quadratic residue of 17

2

• (2/45) = (2/3)²(2/5) = -1
• (109/385) = (385/109) = (58/109) = (2/109)(29/109) = -(109/29) = -(22/29) = -(2/29)(11/29) = (29/11) = (7/11) = (11/7) = (4/7) = (2/7)² = 1
• (1009/2307) = (2307/1009) = (289/1009) = (1009/289) = (142/289) = (71/289) = (289/71) = (5/71) = (71/5) = (1/5) = 1
• (2663/3299) = (3299/2663) = (636/2663) = (159/2663) = (2663/159) = (119/159) = (159/119) = (40/119) = (2/119)³(5/119) = (119/5) = (4/5) = (2/5)² = 1

3

a)

a	0	1	2	3	4
0	1	1	1	1	1
1	0	1	2	3	4
2	0	1	4	9	16
3	0	1	8	27	64
4	0	1	16	81	256

b)

a	0	1	2	3	4	5
0	1	1	1	1	1	1
1	0	1	2	3	4	5
2	0	1	4	9	16	25
3	0	1	8	27	64	125
4	0	1	16	81	256	625
5	0	1	32	243	1024	3125

4

element	1	2	3	4	5	6
power 1 mod 7	1	2	3	4	5	6
power 2 mod 7	1	4	2	2	4	1
power 3 mod 7	1	1	6	1	6	6
power 4 mod 7	1	2	4	4	2	1
power 5 mod 7	1	4	5	2	3	6
power 6 mod 7	1	1	1	1	1	1

So the primitive elements of Z₇ are 3 and 5

5

By looking at the chart in Problem 4, we see that the power of 4 does not generate all of the elements of Z₇, so 4 is not a primitive element of Z₇

6

• p = 23, α = 6, a = 6, k = 3
• β = α^a mod p = 6⁶ mod 23 = 12
• (y₁, y₂) = (α^a mod p, xβ^k mod p) = (6³ mod 23, 10 * 12³ mod 23) = (9, 7)

7

• (y₁, y₂) = (6, 9), a = 8, k = 11
• x = y₂(y₁^a)^-1 mod p = 9 * (6⁸)^-1 mod 11 = 9 * 4 mod 11 = 3