Prepared by:

Professor K M Akkas Ali

akkas_khan@yahoo.com, akkas@juniv.edu

Institute of Information Technology (IIT)

Jahangirnagar University, Dhaka-1342
 Lecture File-02
Mathematics for Cryptography
Objectives of this Lecture:
 To review integer arithmetic, concentrating on divisibility.
 To find the greatest common divisor using the Euclidean
algorithm.
 To understand how the extended Euclidean algorithm can be
used to solve linear Diophantine equations.
 To emphasize the importance of modular arithmetic and
the modulo operator, because they are extensively used in
cryptography.

Slide-2 IIT, JU
Why Mathematics is needed in Security?
 Modern security is heavily based on some areas of mathematics,
including number theory, linear algebra, and algebraic structures.
 Security algorithms are designed around computational hardness
assumptions using mathematical functions and formula, making such
algorithms hard to break in practice by any adversary.
 A list of mathematical fields used in network sedcurity is given below.
 Number theory:
It is used to understand why and how RSA works. Some algorithms use number
theory for the difficulty of factoring large numbers as their basis.
 Group theory:
Group theory is used to understand why and how El Gamal works.
 Probability theory:
It is used in analyzing many kinds of ciphers to better understand what
"statistical security" means.
 Algebraic structure:
The theory of finite fields is used in multiparty computation.
 Linear Algebra:
Lagrange interpolation is used in Shamir's Secret Sharing Scheme. Some linear
operations are also used in AES.

Slide-3 IIT, JU
Integer Arithmetic: The Set of Integers

 In integer arithmetic, we use a set and a few operations.

 We are already familiar with this set and the corresponding
operations, but they are reviewed here to create a background for
modular arithmetic.
 The set of integers, denoted by Z, contains all integral numbers (with
no fraction) from negative infinity to positive infinity.
 Figure below shows the set of integers.

Figure: The set of integers

Slide-4 IIT, JU
Binary Operations
 A binary operation takes two inputs (e.g. a and b) and creates one
output (e.g. c).
 In cryptography, we are interested in three binary operations applied
to the set of integers: addition, subtraction and multiplication.

Figure: Three binary operations for the set of integers

Slide-5 IIT, JU
Slide-6 IIT, JU
Binary Operations

 The following examples shows the results of the three binary

operations on two integers.
 Because each input can be either positive or negative, we can
have four cases for each operation.

Slide-7 IIT, JU
Integer Division

 In integer arithmetic, if we divide a by n, we can get q and r. The

relationship between these four integers can be shown as

a=q×n+r

Where,
 a  dividend
 n  divisor
 q  quotient
 r  remainder

Note:
 Division is not a binary operation, because it produces two output
instead of one (q and r). Instead, we can call it division relation.

Slide-8 IIT, JU
Integer Division
Example:

 Assume that a = 255 and n = 11. We can find q = 23 and r = 2

using the division algorithm.

Figure: Finding the quotient and the remainder

Slide-9 IIT, JU
Integer Division
 When we use the above division relationship in cryptography, we
impose two restrictions:
1. The divisor be a positive integer (i.e. n>0)
2. The remainder be a non-negative integer (i.e. r>=0)

Figure: Division algorithm for integers

Slide-10 IIT, JU
Integer Division
Example:
 When we use a computer or a calculator, r and q are negative
when a is negative.
 How can we apply the restriction that r needs to be positive?
 The solution is simple, we decrement the value of q by 1 and we
add the value of n to r to make it positive.

n r r=n+r

q q = q-1

Slide-11 IIT, JU
Divisibility
Division relation is: a=q×n+r
Where
a  dividend
n  divisor
q  quotient
r  remainder

If a is not zero and we let r = 0 in the division relation, we get:

a=q×n
We then say that
 n divides a
 or, n is a divisor of a
 or, a is divisible by n

Therefore, when a is divisible by If a is not divisible by n (i.e. if r

n and we are not interested in is not zero), then we can write
the value of q, we can write the the above relation as
above relation as a|n
Slide-12 IIT, JU
Divisibility
Example :

a. The integer 4 divides the integer 32 because 32 = 8 × 4. We

show this as

b. The number 8 does not divide the number 42 because

42 = 5 × 8 + 2. There is a remainder, the number 2, in the
equation. We show this as

Example:

Slide-13 IIT, JU
Properties of Divisibility

Property 1: if a|1, then a = ±1.

Property 2: if a|b and b|a, then a = ±b.

Property 3: if a|b and b|c, then a|c.

Example:
Since 3|15 and 15|45, then according to this property, 3|45

Property 4: if a|b and a|c, then

a|(m × b + n × c), where m
and n are arbitrary integers
Example:
Since 3|15 and 3|9, then according to this property, 3|
(15x2+9x4), which means 3|66

Slide-14 IIT, JU
GCD: Greatest Common Divisor
 A positive integer can have more than one divisor. For example, the
integer 32 has six divisors: 1, 2, 4, 8, 16, 32.
 We can mention two interesting facts about divisors of positive
integers:

Fact 1:
The integer 1 has only one divisor, itself.

Fact 2:
Any positive integer has at least two divisors, 1 and itself (but it can have more).

 The greatest common divisor (GCD) of two positive integers is the

largest integer that can divide both integers.
 GCD is often needed in cryptography.
 Two positive integers may have many common divisors, but only one is
the greatest of them.
 For example, the common divisors of 12 and 140 are: 1, 2, and 4.
However, the greatest common divisor is 4.
Slide-15 IIT, JU
GCD: Greatest Common Divisor

Figure: Common divisors of two integers

Slide-16 IIT, JU
GCD Using Euclidean Algorithm
 Finding the GCD of two positive integers by listing all common
divisors is not practical when the two integers are large.

 More than 2000 years ago, a mathematician named Euclid

developed an algorithm that can find the GCD of two large positive
integers.

 The Euclidian algorithm is based on the two facts:

Fact 1: When 2nd integer is zero, then gcd (a, 0) = a

Example: gcd(5, 0) = 5

Fact 2: When both integer is positive, then gcd (a, b) = gcd (b, r),
where r is the remainder of dividing a by b (here the value
of first and second integer is changed until the second
integer becomes zero.
Example:
Gcd(36, 10) = gcd(10, 6) = gcd(6, 4) = gcd(4,2) = gcd(2, 0) = 2
Slide-17 IIT, JU
GCD Using Euclidean Algorithm
 Figure below shows how we use Fact 1 and Fact 2 to calculate gcd (a, b)

Figure: Euclidean Algorithm

Note:
When gcd (a, b) = 1, we say that a and b are relatively prime or they are
coprime.
Slide-18 IIT, JU
GCD Using Euclidean Algorithm
Example:
Find the greatest common divisor of 2740 and 1760.

Solution:

We have gcd (2740, 1760) = 20.

Slide-19 IIT, JU
GCD Using Euclidean Algorithm
Example:
Find the greatest common divisor of 25 and 60.

Solution:
We have gcd (25, 60) = 5.

Note:
The above example shows that it does not matter if the first number is
smaller than the second number. We immediately get our correct
ordering gcd(60, 25).
Slide-20 IIT, JU
Extended Euclidean Algorithm

 Given two integers a and b, we often need to find other two

integers, s and t, such that

 The extended Euclidean algorithm can calculate the gcd (a, b)

and at the same time calculate the value of s and t.

 Using extended Euclidean algorithm, we also can find the

solutions to the linear Diophantine equations of two variables, an
equation of type ax + by = c.

Slide-21 IIT, JU
Extended Euclidean Algorithm

Figure: Extended Euclidean algorithm, part a: Process

Note:
Figure shows that the extended Euclidean algorithm uses the same number of
steps as the Euclidean algorithm, however, in each step, we use three sets of
calculations and exchanges instead of one.
Here, three sets of variables are used: r’s, s’s and t’s.
Slide-22 IIT, JU
Extended Euclidean Algorithm

Figure: Extended Euclidean algorithm, part b: Algorithm

Slide-23 IIT, JU
Extended Euclidean Algorithm
Example:
Given a = 161 and b = 28, find gcd (a, b) and the values of s and t
such that gcd(a, b) = s × a + t × b.

Solution: r = r1 – q × r2 s = s 1 – q × s2 t = t1 – q × t2

We get gcd (161, 28) = 7, s = −1 and t = 6.

The result can be tested, because (-1) × 161 + 6 × 28 = 7

Slide-24 IIT, JU
Extended Euclidean Algorithm
Example:

Given a = 17 and b = 0, find gcd (a, b) and the values of s

and t.

Solution:

We get gcd (17, 0) = 17, s = 1, and t = 0.

Slide-25 IIT, JU
Extended Euclidean Algorithm
Example:

Given a = 0 and b = 45, find gcd (a, b) and the values of s

and t.

Solution:
We get gcd (0, 45) = 45, s = 0, and t = 1.

Slide-26 IIT, JU
Modular Arithmetic

 Given any positive integer n and any nonnegative integer a, if we

divide a by n, we get an integer quotient q and an integer
remainder r such that a = q × n + r.

 This division relation has two inputs (a and n) and two outputs (q
and r).

 In modular arithmetic, we are interested in only one of the

outputs, the remainder r. In other words, we want to know what
is the value of r when we divide a by n. This implies that, using
modular arithmetic, we can change the division relation into a
binary operator (called modulo operator) with two inputs a and n
and one output r.

 Several important cryptosystems make use of modular

arithmetic.

Slide-32 IIT, JU
Modular Arithmetic
 The modulo operator is shown as mod. The second input (n) is
called the modulus. The output r is called the residue.
 Figure below shows the division relation compared with the modulo
operator.
Figure: Division relation Vs. modulo operator

 In the figure we see that the modulo operator (mod) takes an

integer (a) from the set of integers (Z) and a positive modulus
(n). The operator creates a non-negative residue (r) where 0 <=
r <= n-1. We can say that:
a mod n = r

Slide-33 IIT, JU
Modular Arithmetic
Calculation of a mod n:
There are three cases:
Case-1: When both of a and n is positive integer where a<n:

In this case, we add as many multiples of n with a as necessary

to get a greater than n. Then divide a by n to get the remainder
r. The result will be in the range 0 to n-1.
For example, 2 mod 7 = 9 mod 7 = 2.

Case-2: When both of a and n is positive integer where a>=n:

In this case, just divide a by n to get the remainder r. The result
will be in the range 0 to n-1.
For example, 9 mod 7 = 2.

Case-3: When a is negative and n is positive integer:

In this case, we add as many multiples of n with a as necessary to
get a positive and greater than n. Then divide a by n to get the
remainder r. The result will be in the range 0 to n-1. The process
is known as modulo reduction.
For example, -12 mod 7 = -5 mod 7 = 2 mod 7 = 9 mod 7
Slide-34 IIT, JU
Modular Arithmetic
Example:

Find the result of the following operations:

a. 27 mod 5 b. 36 mod 12
c. −18 mod 14 d. −7 mod 10

Solution:
a. Dividing 27 by 5 results in r = 2. Therefore 27 mod 5 = 2
b. Dividing 36 by 12 results in r = 0. Therefore 36 mod 12 = 0
c. Dividing −18 by 14 results in r = −4. After adding the modulus
(14) with the result to make it non-negative, we have r = -4 +
14 = 10. Therefore -18 mod 14 = 10
d. Dividing −7 by 10 results in r = −7. After adding the modulus
(10) with the result to make it non-negative, we have r = -7 +
10 = 3. Therefore –7 mod 10 = 3

Slide-35 IIT, JU
  The result of a mod n is always an integer between 0 and n-1.

 Therefore, the modulo operation creates a set, which in modular

arithmetic is referred to as the set of least residues modulo n, or Zn.

 Figure below shows the set of residues Zn and three instances of the
set of residues Z2, Z6, Z11.

Figure: Some Zn sets

Slide-36 IIT, JU
  The result of 2 mod 10 = 2, 12 mod 10 = 2, 22 mod 10 = 2, 32 mod
10 = 2 and so on.
 In modular arithmetic, integers like 2, 12, 22 and 32 are called
congruent mod 10.
 To show that two integers are congruent, we use the congruence
operator ( ≡ ). For example, we write:

Slide-37 IIT, JU
 Figure below shows the idea of congruence.

Figure 2.11 Concept of congruence

Slide-38 IIT, JU
Residue Sets or Classes:
A residue class [a] or [a]n is the set of integers congruent modulo n. That
is, a residue class is the set of all integers such that x = a (mod n). For
example, if n = 5, we have five sets of residue classes [0], [1], [2], [3]
and [4] as shown below:

Note:
All the integers in the residue class [0] are reduced to 0 when we apply
the modulo 5 operation on them.
Similarly, all the integers in the residue class [1] are reduced to 1 when
we apply the modulo 5 operation on them, and so on.

In each residue set or class, there is one element called the least
residue. For example, in set [0], [1], [2], [3] and [4], this element (least
residue) is 1, 2, 3, and 4 respectively. The set of all of these least
residues is written as Z5 = {0, 1, 2, 3, 4}. In other words, the set Zn is
the set of all least residue modulo n.
Slide-39 IIT, JU
Modular Arithmetic: Inverse

 In cryptography, we often need to find the inverse of a number relative

to an operation e.g., encryption/decryption.
 For example, if the sender uses an integer as the encryption key, the
receiver uses the inverse of that integer as the decryption key.
 We are normally looking for two kinds of inverse:
 Additive Inverse
 If the operation is addition, we are normally looking for additive
inverse.

 The set of additive inverse is expressed as Zn

 Multiplicative Inverse
 If the operation is multiplication, we are normally looking for
multiplicative inverse.

 The set of multiplicative inverse is expressed as Zn*

Slide-40 IIT, JU
Modular Arithmetic: Additive Inverse
 In Zn, two numbers a and b are additive inverses of each other if

 In modular arithmetic, each integer has an additive inverse.

 The sum of an integer and its additive inverse is congruent to 0
modulo n.

Example:
Find all additive inverse pairs in Z10.

Solution:

The six pairs of additive inverses are:

(0, 0), (1, 9), (2, 8), (3, 7), (4, 6), and (5, 5).

Slide-41 IIT, JU
Modular Arithmetic: Multiplicative Inverse
 In Zn, two numbers a and b are the multiplicative inverse of each
other if

 In modular arithmetic, an integer may or may not have a

multiplicative inverse.
 When it does, the product of the integer and its multiplicative
inverse is congruent to 1 modulo n.

Example:
Find the multiplicative inverse of 8 in Z10.

Solution:
 There is no multiplicative inverse of 8 in Z10 because gcd
(10, 8) = 2 ≠ 1.
 In other words, we cannot find any number between 0 and 9
such that when multiplied by 8, the result is congruent to 1.
Slide-42 IIT, JU
Modular Arithmetic: Multiplicative Inverse
Example:
Find all multiplicative inverses in Z10.

Solution:
There are only three pairs: (1, 1), (3, 7) and (9, 9). The numbers 0,
2, 4, 5, 6, and 8 do not have a multiplicative inverse.

Example:
Find all multiplicative inverse pairs in Z11.

Solution:
We have seven pairs: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8), (9, 5), and
(10, 10).

Slide-43 IIT, JU
Modular Arithmetic: Multiplicative Inverse
Multiplicative Inverse Using Extended Euclidean Algorithm:
 The extended Euclidean algorithm finds the multiplicative
inverses of b in Zn when n and b are given and gcd (n, b) = 1.
 The multiplicative inverse of b is the value of t after being
mapped to Zn.

Figure: To find multiplicative inverse using extended Euclidean algorithm

Slide-44 IIT, JU
Modular Arithmetic: Multiplicative Inverse
Example-1:
Find the multiplicative inverse of 11 in Z26 using extended Euclidean
algorithm.

Solution:

The gcd (26, 11) is 1; the inverse of 11 is -7 or 19.

Slide-45 IIT, JU
Modular Arithmetic: Multiplicative Inverse
Example-2:
Find the multiplicative inverse of 23 in Z100 using extended Euclidean
algorithm

Solution:

The gcd (100, 23) is 1; the inverse of 23 is -13 or 87.

Slide-46 IIT, JU
Modular Arithmetic: Multiplicative Inverse
Example-3:
Find the inverse of 12 in Z26 using extended Euclidean algorithm.

Solution:

The gcd (26, 12) is 2; the inverse does not exist.

Slide-47 IIT, JU
Modular Arithmetic: Multiplicative Inverse
Multiplicative Inverse Using Fermat’s Little Theorem:
 If the modulus is a prime, then multiplicative inverse of an
integer can be found quickly without using the Extended
Euclidean’s algorithm:
 If p is a prime and a is an integer such that p does not divide a (p†a), then

a-1 mod p = ap-2 mod p

Example:
Find the multiplicative inverse of 8 in Z17 using Fermat’s Little
Theorem.

Solution:
Since, the modulus 17 is a prime, so according to Fermat’s Little theorem,

8-1 mod 17 = 817-2 mod 17 = 815 mod 17 = 15

Slide-48 IIT, JU
Set of Additive and Multiplicative Inverse
Set of Additive Inverse Zn :
 Zn is a set that contains all integers from 0 to n-1.

 In Zn , each integer has an additive inverse. Therefore Zn can also

be used as the set of additive inverse.
 Each member of Zn has an additive inverse.

Set of Multiplicative Inverse Zn* :

 In Zn, an integer may or may not have a multiplicative inverse.
Only some members of Zn have a multiplicative inverse.

 Therefore, for multiplication operation, we need another set Z n*

which is a subset of Zn that includes only those integers from Zn
that have a unique multiplicative inverse.
Note:
 Each member of Zn has an additive inverse, but only some members of Z n
have a multiplicative inverse.

 On the other hand, Each member of Zn* has a multiplicative inverse, but only
some members of Zn* have an additive inverse.
4.49
Slide-49 IIT, JU
Set of Additive and Multiplicative Inverse
Finding the number of elements in Zn :
 Zn is a set that contains all integers from 0 to n-1.

Finding the number of elements in Zn* :

 We can determine the number of elements in the set Zn* using
Euler’s Phi-Function (sometimes called the Euler’s Totient
function), Φ(n) that finds the number of integers that are both
smaller than n and relatively prime to n.
 The following rules helps to find the value of Φ(n):

Slide-50 IIT, JU
Set of Additive and Multiplicative Inverse
Example-1:
Find the number of elements in Z13* using Euler’s Phi-Function.
Solution:
Since 13 is a prime, so according to the second rule,

Φ(13)=(13-1)=12
Example-2:
Find the number of elements in Z10* using Euler’s Phi-Function.

Solution:
Since 10 is not a prime, so according to the third rule,

Φ(10)= Φ(5x2)= Φ(2) x Φ(5)=(2-1) x (5-1)= 1 x 4 =4

Example-3:
Find the number of elements in Z49* using Euler’s Phi-Function.

Solution:
Since 49 is not a prime and it can not be factored as the product of two
relatively primes, so according to the fourth rule,

Slide-51 Φ(49)= Φ(72)= 72 – 72-1= 49 – 7 = 42 IIT, JU

Set of Additive and Multiplicative Inverse

Some Instances of Zn and Zn*

Figure: Some Zn and Zn* sets

Slide-52 IIT, JU
Set of Additive and Multiplicative Inverse
Two More Sets: Zp and Zp* :
 Cryptography often uses two more sets: Zp and Zp*. The modulus
in these two sets is a prime number.

 The set Zp is the same as Zn except that n is a prime.

 Zp contains all integers from 0 to p-1.
 Each member in Zp has an additive inverse; each member except
0 has a multiplicative inverse.

 The set Zp* is the same as Zn* except that n is a prime.

 Zp* contains all integers from 1 to p-1.
 Each member in Zp* has an additive and a multiplicative inverse.
 Zp* is a very good candidate when we need a set that supports
both additive and multiplicative inverse.

Slide-53
Figure: The set Zp and Zp* when p=13
IIT, JU
Matrices

In cryptography we need to handle matrices. Although

this topic belongs to a special branch of algebra called
linear algebra, the following brief review of matrices is
necessary preparation for the study of cryptography.

Topics discussed in this section:

Definitions
Operations and Relations
Determinants
Residue Matrices

Slide-54 IIT, JU
Matrices

 A matrix is a rectangular array of l×m elements, in which l is

the number of rows and m is the number of columns.
 It is normally denoted with a boldface uppercase letter such
as A.
 The element aij is located in the ith row and jth column.

Figure: A matrix of size l  m

Slide-55 IIT, JU
Matrices

Example of Matrices:

 Row matrix:
If a matrix has only one row (l), then it is called a row matrix.

 Column matrix:
If a matrix has only one column (m), then it is called a
column matrix.

Slide-56 IIT, JU
Matrices
Example of Matrices:
 Square matrix:
If a matrix has same number of rows and columns (l = m), then it is called
a square matrix. In a square matrix, the elements a11, a22, ….. ,amm make
the main diagonal.
 Additive Identity matrix:
It is a kind of matrix with all rows and columns set to 0’s. It is denoted as
O.
 Identity matrix:
It is a kind of square matrix with 1’s on the main diagonal and 0’s
elsewhere. It is denoted as I.

Slide-57 IIT, JU
Matrices

Operations and Relations in Matrices:

In linear algebra, one relation (equality) and four operations (addition,

subtraction, multiplication and scalar multiplication) are defined for matrices.

Equality:
Two matrices are equal if they have the same number of rows and columns and
the corresponding elements are equal. In other words, A = B if we have aij = Bij
for all i’s and j’s.

3 5 7  3 5 7 

A  2 2 1    
B  2 2 1 
1 4 3  1 4 3 
Slide-58 IIT, JU
Matrices

Addition and Subtraction:

Two matrices can be added if they have the same number of rows and columns.
The resulting matrix has also the same number of rows and columns, e.g. A + B =
C.

Example:

Figure: Addition and subtraction of matrices

Slide-59 IIT, JU
Matrices

Multiplication:
Two matrices can be multiplied if the number of columns of the first matrix is the
same as the number of rows of the second matrix. If A is an l×m matrix and B is
an m×p matrix, then their product is a matrix C of size l×p.

Example: Figure 2.21 shows the product of a row matrix (1 × 3) by a

column matrix (3 × 1). The result is a matrix of size 1 × 1.

Figure: Multiplication of a row matrix by a column matrix

Slide-60 IIT, JU
Matrices
Example:

Figure 2.22 shows the product of a 2 × 3 matrix by a

3 × 4 matrix. The result is a 2 × 4 matrix.

Figure: Multiplication of a 2 × 3 matrix by a 3 × 4 matrix

Slide-61 IIT, JU
Matrices

Scalar Multiplication:
We can multiply a matrix by a number (called a scalar). If A is an l×m matrix and
x is a scalar, then C = xA is a matrix of size l×m.

Example: Figure below shows an example of scalar multiplication.

Figure: Scalar multiplication

Slide-62 IIT, JU
Matrices
Transpose of a Matrix:
A matrix which is formed by turning all the rows of a given matrix into
columns and vice-versa is called the transpose of the original matrix. The
transpose of matrix A is written AT.

Slide-63 IIT, JU
Matrices
Determinant
The determinant of a square matrix A of size m × m denoted as det (A) is a
scalar calculated recursively as shown below:

The determinant is defined only for a

square matrix.
Slide-64 IIT, JU
Matrices
Example:
Figure below shows how we can calculate the determinant of
a 2 × 2 matrix based on the determinant of a 1 × 1 matrix.

Figure: Calculating the determinant of a 2  2 matrix

Slide-65 IIT, JU
Matrices
Example:

Figure below shows the calculation of the determinant

of a 3 × 3 matrix.

Figure: Calculating the determinant of a 3  3 matrix

Slide-66 IIT, JU
Matrices
More Example
Calculate the determinant of the following matrix.

 2  2 0
0  2  4 
 
 2  2 0
1 1  1 
det 0  2  4
1 1  1 
 2{[(2)  (1)]  [(4)  (1)]}  (2){[(0)  ( 1) ]  [(4)  (1)]}  (0){[(0)  ( 1) ]  [(2)  (1)]}
 2{[2]  [4]}  (2){[0 ]  [4]}  (0){[0]  [2]}

 2{2  4 }  (2){0  4}  (0){0  2}

 2  6  (2  4)  0  2

 12  8  0  20

Slide-67 IIT, JU
Matrices
Cofactor Matrix of a Given Matrix

Slide-68 IIT, JU
Matrices
Adjoint of a Given Matrix
The matrix formed by taking the transpose of the cofactor matrix of a
given original matrix is called the adjoint of the given matrix. The
adjoint of matrix A is often written adj A.

Finally the adjoint of A is

the transpose of the
cofactor matrix:

Slide-69 IIT, JU
Matrices
Inverse of Matrix

For an n×n square matrix A, the inverse of A (written as

A-1) is another n×n square matrix such that when A is
multiplied by A-1 the result is an n×n identity matrix I. Not
all n×n matrices are invertible. Non-square matrices do
not have inverses.
AA-1 = A-1A = I

 A matrix which is not invertible is sometimes called a

singular matrix.

 An invertible matrix is called a nonsingular matrix.

Slide-70 IIT, JU
Matrices

Examples:

Slide-71 IIT, JU
Matrices
Determining the Inverse of Matrix

When A is a 2×2 Matrix:

1  d b 
det( A)  c a 

Example-1:

Slide-72 IIT, JU
Matrices

When A is a 2×2 Matrix:

Example-2:

Slide-73 IIT, JU
Matrices
When A is an m×m Matrix:

To find the inverse of an m×m matrix, follow the steps given below:

1. Find the adjoint of the given matrix.

2. Find the determinant of the given matrix.

3. Now, determine the inverse using the above formula.

Slide-74 IIT, JU
Matrices

Solution:
The adjoint of A
is :

1 2 3
The determinant of A is : Det A  Det 0 4 5   22
1 0 6

The inverse of A is :

Slide-75 IIT, JU
Matrices
Additive & Multiplicative Inverse of Matrix
Matrices have both additive and multiplicative inverses.

Additive Inverse of a Matrix:

The additive inverse of a matrix A is another matrix B such that A + B = 0. In

other words, we have aij = - bij for all values of i and j. Normally the additive
inverse of A is denoted by –A.

Slide-76 IIT, JU
Matrices

Multiplicative Inverse of a Matrix:

The multiplicative inverse of a square matrix A is another square matrix B

such that A × B = B × A = I. Normally the multiplicative inverse of A is
denoted by A-1.
The multiplicative inverse exists only if the det(A) has a multiplicative inverse
in the corresponding set.

Multiplicative inverses are only defined

for square matrices.

Slide-77 IIT, JU
Matrices
Residue Matrices
Cryptography uses residue matrices: matrices where all elements are
in Zn. A residue matrix has a multiplicative inverse if gcd (det(A), n) =
1.

Example:

Figure: A residue matrix and its multiplicative inverse

Slide-78 IIT, JU