tough Cryptography Questions on “Number Theory”.
1. Find the order of the group G = <Z12*, ×>?
a) 4
b) 5
c) 6
d) 2
Answer: a
Clarification: It can be obtained using Euler Phi function, i.e. f(n).
2. Find the order of the group G = <Z21*, ×>?
a) 12
b) 8
c) 13
d) 11
Answer: a
Clarification: |G| = f(21) = f(3) × f(7) = 2 × 6 =12
There are 12 elements in this group:
G = <Z21*, ×> = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}. All are relatively prime with 21.
3. Find the order of group G= <Z20*, x>
a) 6
b) 9
c) 10
d) 8
Answer: d
Clarification: |G| = f(20) = f(4) × f(5) = f(22) × f(5) = (22-21)(51-50) = 8.
G = = { 1, 3, 7, 9, 11, 13, 17, 19 }.
4. Find the order of group G= <Z7*, x>
a) 6
b) 4
c) 3
d) 5
Answer: a
Clarification: |G| = f(7) = (71-70) = 6
G = <Z20, x> = { 1, 2, 3, 4, 5, 6 }.
5. In the group G = <Zn*, ×>, when the order of an element is the same as order of the group (i.e. f(n)), that element is called the Non – primitive root of the group.
a) True
b) False
Answer: b
Clarification: Such a group is called the primitive root of the group.
6. In the order of group G= <Z20*, x>, what is the order of element 17?
a) 16
b) 4
c) 11
d) 6
Answer: b
Clarification:
17 17 9 13 1 ord(17) = 4
n? 1 2 3 4 5 6 7 order
7. The order of group G= <Z9, x> , primitive roots of the group are –
a) 8 , Primitive roots- 2,3
b) 6 , Primitive roots- 5
c) 6 , Primitive roots- 2,5
d) 6 , Primitive roots- 5,7
Answer: c
Clarification: |G| = f(9) = (32-31) = 6
G = <Z20, x> = { 1, 2, 4, 5, 7, 8 }.
8. Which among the following values: 17, 20, 38, and 50, does not have primitive roots in the group G = <Zn*, ×>?
a) 17
b) 20
c) 38
d) 50
Answer: b
Clarification: The group G = <Zn*, ×> has primitive roots only if n is 2, 4, pt, or 2pt
‘p’ is an odd prime and‘t’ is an integer.
G = <Z17*, ×> has primitive roots, 17 is a prime.
G = <Z20*, ×> has no primitive roots.
G = <Z38*, ×> has primitive roots, 38 = 2 × 19 prime.
G = <Z50*, ×> has primitive roots, 50 = 2 × 52 and 5 is a prime.
9. Find the number of primitive roots of G=<Z11*, x>?
a) 5
b) 6
c) 4
d) 10
Answer: c
Clarification: Number of primitive roots = f(f(11))=f((111-110)) = f(10) = f(2). f(5)
= (21-20)(51-50) = 1 x 4 = 4
The primitive roots of this set {2, 6, 7, 8}.
10. Find the primitive roots of G=<Z11*, x>?.
a) {2, 6, 8}
b) {2, 5, 8}
c) {3, 4, 7, 8}
d) {2, 6, 7, 8}
Answer: d
Clarification: Number of primitive roots = f(f(11))=f((111-110)) = f(10) = f(2). f(5)
= (21-20)(51-50) = 1 x 4 = 4
The primitive roots of this set {2, 6, 7, and 8}.
11. If a group has primitive roots, it is a cyclic group
a) True
b) False
Answer: a
Clarification: Yes, a group which has primitive roots is a cyclic group.
12. Find the primitive roots of G = <Z10*, ×>.
a) {2, 6, 8}
b) {3,6 ,9}
c) {3, 7, 8}
d) {3, 7}
Answer: c
Clarification: Number of primitive roots = f(f(11))=f((111-110)) = f(10) = f(2). f(5)
= (21-20)(51-50) = 1 x 4 = 4
The primitive roots of this set are {3, 7}.
13. The group G = <Zp*, ×> is always cyclic.
a) True
b) False
Answer: a
Clarification: G = <Zp*, ×> is always cyclic.