Course: Cryptography and Network Security
Code: CS-34310
Branch: M.C.A - 4th Semester
Lecture – 3: Introduction to Cryptography Mathematics
Faculty & Coordinator : Dr. J Sathish Kumar (JSK)
Department of Computer Science and Engineering
Motilal Nehru National Institute of Technology Allahabad,
Prayagraj-211004
Integer Arithmetic
• In integer arithmetic, we use a set and a few operations.
• 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
Binary Operations
• In cryptography, we are interested in three binary operations applied
to the set of integers.
• A binary operation takes two inputs and creates one output.
Example #1
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
Example #2
Integer Division
Integer Division
• 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.
Integer Division
• Graph of division algorithm
Divisibility
• If a is not zero and we let r = 0 in the division relation, we get
• If the remainder is zero, n | a
• If the remainder is not zero, n | a
Example #3
Divisibility
• Properties
Divisibility
Divisibility
Divisibility
Example #4
Divisibility
Divisibility
Example #5
Divisibility
Class Exercise #1
Divisibility
• 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.
Divisibility
Divisibility
Divisibility
Divisibility
Divisibility
Divisibility
Linear Diophantine Equations
• A linear Diophantine equation of two variables is,
ax + by = c.
• We want to find integer values for x and y that satisfy the equation.
• Either no solution or an infinite number of solutions
• Let d = gcd(a,b); if d | c, the equation has no solution.
• If d | c, the equation has infinite number of solutions : one of them
is particular and the rest are general
Linear Diophantine Equations(cont.)
Linear Diophantine Equations(cont.)
Linear Diophantine Equations(cont.)
• d = gcd (21, 14) = 7.
• Since 7| 35, the equation has an infinite number of solutions.
• We can divide both sides by 7 to find the equation 3x + 2y = 5.
• Using the extended Euclidean algorithm, we find s and t such as 3s + 2t = 1. We
have s = 1 and t = −1.
Linear Diophantine Equations(cont.)
Linear Diophantine Equations(cont.)
Modular Arithmetic
Preliminary
• The division relationship (a = q × n + r) discussed in the previous
section 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.
• We use modular arithmetic in our daily life;
• for example, we use a clock to measure time.
• Our clock system uses modulo 12 arithmetic. However, instead of a 0 we use
the number 12
Modulo Operator
• The modulo operator is shown as mod.
• The second input (n) is called the modulus.
• The output r is called the residue.
Modulo Operator(cont.)
• 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
b. Dividing 36 by 12 results in r = 0
c. Dividing −18 by 14 results in r = −4. After adding the modulus r = 10
d. Dividing −7 by 10 results in r = −7. After adding the modulus to −7, r = 3
Set of Residues
• The modulo operation creates a set, which in modular arithmetic is
referred to as the set of least residues modulo n, or Zn.
Congruence
• To show that two integers are congruent, we use the congruence
operator ( ≡ ).
• For example, we write:
Congruence
Congruence
• Residue Classes
– A residue class [a] or [a]n is the set of integers congruent modulo n.
– It is the set of all integers such that x=a(mod)n
– E.g. for n=5, we have five sets as shown below:
Congruence
• Comparison of Z and Zn using graphs
Operation in Zn
• The three binary operations that we discussed for the set Z can also
be defined for the set Zn.
• The result may need to be mapped to Zn using the mod operator.
Operation in Zn
• Perform the following operations (the inputs come from Zn):
a. Add 7 to 14 in Z15.
b. Subtract 11 from 7 in Z13.
c. Multiply 11 by 7 in Z20.
• Solution
Operation in Zn
• Perform the following operations (the inputs come from either Z or Zn):
a. Add 17 to 27 in Z14.
b. Subtract 43 from 12 in Z13.
c. Multiply 123 by −10 in Z19.
• Solution
a. Add 17 to 27 in Z14: (17+27)mod 14 = 2
• Subtract 43 from 12 in Z13 : (12-43)mod 13 = 8
• Multiply 123 by −10 in Z19. : (123 x (-10)) mod 19 = 5
Operation in Zn(cont.)
Operation in Zn(cont.)
Operation in Zn(cont.)
• The following shows the application of the above properties:
1. (1,723,345 + 2,124,945) mod 11 = (8 + 9) mod 11 = 6
2. (1,723,345 − 2,124,945) mod 11 = (8 − 9) mod 11 = 10
3. (1,723,345 × 2,124,945) mod 11 = (8 × 9) mod 11 = 6
Operation in Zn(cont.)
• In arithmetic, we often need to find the remainder of powers of 10
when divided by an integer.
Inverses
• When we are working in modular arithmetic, we often need to find the
inverse of a number relative to an operation.
• We are normally looking for an additive inverse (relative to an addition
operation) or a multiplicative inverse (relative to a multiplication
operation).
Additive Inverses
• In Zn, two numbers a and b are additive inverses of each other if
Additive Inverses
• 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).
Multiplicative Inverses
• In Zn, two numbers a and b are the multiplicative inverse of each
other if,
Multiplicative Inverses
• Find the multiplicative inverse of 8 in Z10.
• There is no multiplicative inverse 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.
• Find all multiplicative inverses in Z10.
• 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.
Multiplicative Inverses
• Find all multiplicative inverse pairs in Z11.
• Solution
• We have seven pairs: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8), and
(10, 10).
