Book: Cryptology -Theory and Practice (3rd Edition) Page: 40 Problem: 1.12 (a) a
ID: 663110 • Letter: B
Question
Book: Cryptology -Theory and Practice (3rd Edition) Page: 40 Problem: 1.12 (a) and (b) and 1.13 1.12 (a) Let p be prime. Prove that the number of 2 x 2 matrices that are invertible over Zp is (p 1)(p2 p) HINT: Since p is prime, Zp is a field. Use the fact that a matrix over a field is invertible if and only if its rows are linearly independent vectors e.. there does not exist a non-zero linear combination of the rows whose sum is the vector of all 0's) 1.12 (b) For p prime and m e 2 an integer, find a formula for the number of m X m matrices that are invertible over Z 1.13 For n 6,9, and 26, how many 2 x 2 matrices are there that are invertible over ZnExplanation / Answer
1)
Now we have to count that the number of ways the invertible 2x2 matrix can be constructed
with entries of zp. For this we need 2 linearly independent rows.
So the row ( first one) be any nonzero vector. so p2-1 choices.
now for second row p2 possibilities are there. although we have already p possibilities scalars
so omit that p multiples. so for second row (p2-p)
combinely (p2-1)(p2-p)
2)
our required answer is (p2-1)(p2-p), since for first rows can choose (p2-1) ways as it is non zero and then for second column we have to remove p ways..so (p2-p)
3)
for n=6,n=9,n=26
formula is (p2-1)(p2-p)
n=6 ==>(36-1)(36-6) ==>(35)(30) ===>1050
n=9 ===>n=9==>(81-1)(81-9)===>(80)(72)
n=26 ===>n=26==>(26^2-1)(26^2 - 26)