Integer

Arithmetic
• Consists of a set of Integers
and operations on it.
 Integer Division
• If b|a and b≠0, then a=q*b; where a,b,q ∈ Z
• If b∤a and b≠0, then a=q*b+r; where a,b,q,r ∈ Z
 • If b|a and a|b, then a=±b.
Properties of • If b|1, then b=±1.
Integer • If a|b and b|c, then a|c.
Division • If a|b and a|c, then a|(m*b+n*c), where a, b,
c, m, n ∈ Z.
MODULAR ARITHMETIC
Modular Arithmetic
• For a=q*b+r, a mod b = r; where a, b, q, r ∈ Z.
• Zn = {0, 1, 2, 3, 4, …… (n-1)}
Modular
Arithmetic
(Examples)

• 27 mod 5 = 2
• 36 mod 7 = 1
• -13 mod 6 = 5
• -29 mod 12 = 7
Basic
• If a,b ∈ Zn, then (a+b) mod n = c ∈ Zn
Operations • If a,b ∈ Zn, then (a-b) mod n = c ∈ Zn
in Modular • If a,b ∈ Zn, then (a*b) mod n = c ∈ Zn
Arithmetic
Basic • (17+19) mod 23 = 13 ∈ Z23
Operations in • (3-5) mod 6 = 4 ∈ Z6
• (13*14) mod 15 = 2 ∈ Z15
Modular
• (8*9) mod 13 = 7 ∈ Z13
Arithmetic
(Examples)
 Properties of Modular Arithmetic

(a+b) mod n = [(a mod n)+(b mod n)] mod n; a,b ∈ Z

(a-b) mod n = [(a mod n)-(b mod n)]

mod n; a,b ∈ Z
(a*b) mod n = [(a mod n)*(b mod n)]
mod n; a,b ∈ Z
Properties of Modular Arithmetic (Examples)

(8+7) mod 5 = [(8 mod 5) + (7 mod 5)] mod 5 = (3+2) mod 5 = 0 ∈ Z5

(28-16) mod 8 = [(28 mod 8) - (16 mod 8)] mod 8 = (4-0) mod 8 = 4 ∈ Z8

(23*25) mod 20 = [(23 mod 20)*(25 mod 20)] mod 20 = (3*5) mod 20 = 15 ∈ Z20
 Modular Additive Inverse
For a,b ∈ Zn, b is the additive inverse of a if (a+b) ≡ 0 (mod n)

Additive Inverse pairs of Z10 = {(0,0), (1,9), (2,8), (3,7), (4,6), (5,5)}

Additive Inverse pairs of Z9 = {(0,0), (1,8), (2,7), (3,6), (4,5)}

Additive Inverse pairs of Z11 = {(0,0), (1,10), (2,9), (3,8), (4,7), (5,6)}
Modular Multiplicative Inverse

For a,b ∈ Zn, b is the Multiplicative Inverse of a, if (a*b) ≡ 1 (mod n)

Multiplicative Inverse pairs in Z5 = {(1,1), (2,3), (4,4)}

Multiplicative Inverse pairs in Z6 = {(1,1), (5,5)}

Multiplicative Inverse pairs in Z7 = {(1,1),(2,4),(3,5),(6,6)}

Properties of Congruences
1) Reflexive Property:- a ≡ a (mod n)
2) Symmetric Property:- If a≡b (mod n), then b ≡ a (mod n)
3) Transitive Property:- If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)
4) Addition Property:- If a ≡ b (mod n) and c ≡ d (mod n), then (a+c) ≡ (b+d) mod n
5) Subtraction Property:- If a ≡ b (mod n) and c ≡ d (mod n), then (a-c) ≡(b-d) mod n
6) Multiplication Property:- If a≡b (mod n), then (a*c) ≡ (b*c) mod n; c ∈ Z
7) Exponential Property:- If a≡b (mod n), then am ≡ bm (mod n)
Properties of Congruences
(Examples)
• 7 ≡ 7 (mod 5)
• 8 ≡ 3 (mod 5); Hence, 3 ≡ 8 (mod 5)
• 18 ≡ 11 (mod 7); 11 ≡ 4 (mod 7); Hence, 18 ≡ 4 (mod 7)
• 19 ≡ 10 (mod 9); 25 ≡ 16 (mod 9); Hence, 44 ≡ 26 (mod 9)
• 44 ≡ 26 (mod 9); 25 ≡ 16 (mod 9); Hence, 19 ≡ 10 (mod 9)
• 18 ≡ 11 (mod 7); Hence, 90 ≡ 55 (mod 7)
• 8 ≡ 3 (mod 5); Hence, 64 ≡ 9 (mod 5);
PRIMES AND GCD
 • In Cryptography, only positive primes have significance, though
some Mathematicians extend the idea of primes and composites

Prime
to negative numbers as well.
• In Cryptography, large primes are required for algorithms like
RSA, Diffie Hellman, etc.
Numbers
 Prime Factorization
• Expressing a positive composite number as a product of primes.
• Prime factorization of a number is harder than multiplying the
primes to generate the number.
• 10 = 2 * 5
• 100 = 22 * 52
• 1000 = 23 * 53
• 120 = 23 * 3 * 5
• 5040 = 24 * 32 * 5 * 7
 • In Cryptography, typically only
positive numbers are used.
• If c|a and c|b, the GCD(a, b)=c;
where a,b,c ∈ N.

GCD (HCF) • GCD(5,10) = 5

• GCD(8,12) = 4
• GCD(24, 60) = 12
• GCD(10, 45) = 5
• GCD(28, 70) = 14
 • a and b are co-prime if
GCD(a,b) = 1; a,b ∈ N;
• 1 is co-prime with all the
Natural numbers.
Co-Primes • For a≡b (mod n), if
GCD(d,n)=1, then (a/d) ≡(b/d)
(mod n); where d∈N.
• Examples of some co-prime
pairs: (8,15), (12,25), (17,20)
EUCLIDEAN ALGORITHM
Euclidean Algorithm to
Calculate GCD (Pseudocode)
GCD(a,b)
{
if(b==0)
return a;
else
return GCD(b, a mod b)
}

• Here a,b ∈ N and a ≥ b.

GCD (48, 18) = ?

a b
48 18
18 12
12 6
6 0
GCD (198, 121) = ?

a b
198 121
121 77
77 44
44 33
33 11
11 0
GCD (584, 248) = ?

a b
584 248
248 88
88 72
72 16
16 8
8 0
GCD (66348, 18042) = ?

a b
66348 18042
18042 12222
12222 5820
5820 582
582 0
GCD (868, 795) = ?

a b
868 795
795 73
73 65
65 8
8 1
1 0
EXTENDED EUCLIDEAN
ALGORITHM (EEA)
 EEA for gcd(a,b)=d

EEA(a, b)
• Here d=a*x+b*y; where
{
x,y∈Z.
u1=1, u2=0, v1=0, v2=1;
while(b≠0)
{
q=a/b; r=a mod b; u=u1-q*u2; v=v1-q*v2; a=b; b=r;
u1=u2; u2=u; v1=v2; v2=v;
}
d=a; x=u1; y=v1;
return(d, x, y)
}
 Calculate GCD(48,18), x, y

q a b r u1 u2 u v1 v2 v
2 48 18 12 1 0 1 0 1 -2

1 18 12 6 0 1 -1 1 -2 3

2 12 6 0 1 -1 3 -2 3 -8

6 0 -1 3 3 -8

• GCD(48, 18) = 6 = 48 * (-1) + 18 * (3)

 Calculate GCD(848, 596), x, y

q a b r u1 u2 u v1 v2 v
1 848 596 252 1 0 1 0 1 -1
2 596 252 92 0 1 -2 1 -1 3
2 252 92 68 1 -2 5 -1 3 -7
1 92 68 24 -2 5 -7 3 -7 10
2 68 24 20 5 -7 19 -7 10 -27
1 24 20 4 -7 19 -26 10 -27 37
5 20 4 0 19 -26 149 -27 37 -212

4 0 -26 149 37 -212

• GCD(848, 596) = 4 = 848 * (-26) + 596 * (37)

 Calculate GCD(165,68), x, y

q a b r u1 u2 u v1 v2 v
2 165 68 29 1 0 1 0 1 -2
2 68 29 10 0 1 -2 1 -2 5
2 29 10 9 1 -2 5 -2 5 -12
1 10 9 1 -2 5 -7 5 -12 17
9 9 1 0 5 -7 68 -12 17 -165

1 0 -7 68 17 -165

• GCD(165,68) = 1 = 165*(-7)+68*(17)
• Hence, MI(165) mod 68 = -7 mod 68 = 61
 MI(485) mod 812 = ?

q a b r v1 v2 v
1 812 485 327 0 1 -1
• MI(485) mod 812 = 221
1 485 327 158 1 -1 2
2 327 158 11 -1 2 -5
14 158 11 4 2 -5 72
2 11 4 3 -5 72 -149
1 4 3 1 72 -149 221
3 3 1 0 -149 221 -812
1 0 221 -812
 MI(608) mod 73 = ?

q a b r u1 u2 u
8 608 73 24 1 0 1
3 73 24 1 0 1 -3
24 24 1 0 1 -3 73
1 0 -3 73

• MI(608) mod 73 = -3 mod 73 = 70

MODULAR EXPONENTIAL
ALGORITHM
 13
7 mod 20 = ?

4
• 7 mod 20 = 1
• 713 mod 20 = [712 mod 20 * 7 mod 20] mod 20
• 713 mod 20 = (74 mod 20)3 mod 20 * 7 mod 20 = 7
 27
13 mod 48 = ?

• 27 = 16+8+2+1
• 132 mod 48 = 25
• 138 mod 48 = (132 mod 48)4 mod 48 = 254 mod 48 = 1
16 8 2 2
• 13 mod 48 = (13 mod 48) mod 48 = 1 mod 48 = 1
• 1327 mod 48 = (1316 mod 48 * 138 mod 48 * 132 mod 48* 13) mod 48 =
(1*1*25*13) mod 48 = 37
 239
106 mod 54 = ?

• 239 = 128 + 64 + 32 + 8 + 4 + 2 + 1
• 1062 mod 54 = 4
4 2 2 2
• 106 mod 54 = (106 mod 54) mod 54 = 4 mod 54 = 16
• 1068 mod 54 = (1064 mod 54)2 mod 54 = 162 mod 54 = 40
• 10632 mod 54 = (1068 mod 54)4 mod 54 = 404 mod 54 = 22
64 32 2 2
• 106 mod 54 = (106 mod 54) mod 54 = 22 mod 54 = 52
• 106128 mod 54 = (10664 mod 54)2 mod 54 = 522 mod 54 = 4
• 106239 mod 54 = (106128 mod 54 * 10664 mod 54 * 10632 mod 54 * 1068 mod 54 *
4 2
106 mod 54 * 106 mod 54 * 106) mod 54
 239
106 mod 54 = ? (Contd..)

• 106239 mod 54 = (4*52*22*40*16*4*106) mod 54

• 106239 mod 54 = [(4*52*22*40) mod 54 * (16*4*106) mod 54] mod 54
239
• 106 mod 54 = (34 * 34) mod 54 = 22
FERMAT’S THEOREM
 p-1
• a ≡ 1 (mod p); where a ∈N,
GCD(a,p)=1, and p is a prime.
18
• 7 mod 19 = 1
Fermat’s 28
• 48 mod 29 = 1
Theorem 96
• 65 mod 97 = 1
Fermat’s Theorem (Proof)
Fermat’s • Dividing both the sides of the equation by (p-1)!
p-1
(Since its coprime with p), we get a ≡ 1 (mod p),
which represents the Fermat’s theorem
Theorem • If we multiply both the sides of the equation
(Proof) representing the Fermat’s theorem by a, then we
also get ap ≡ a (mod p)
Fermat’s 19
Theorem • 7 mod 19 = 7
29
(Examples • 48 mod 29 = 48 mod 29 = 19
73
) • 140 mod 73 = 140 mod 73 = 67
 192
200 mod 97 = ?

96
• 200 mod 97 = 1
192 96 2 2
• 200 mod 97 = (200 mod 97) mod 97 = 1 mod 97 = 1
 1026
3 mod 103 = ?

102
• 3 mod 103 = 1
1020 102 10 10
•3 mod 103 = (3 mod 103) mod 103 = 1 mod 13 = 1
1026 1020 6
•3 mod 103 = (3 mod 103 * 3 mod 103) mod 103
1026
•3 mod 103 = (1*8) mod 103 = 8
EULER’S THEOREM
 Euler Totient Function (ϕ(n))

• ϕ(n) = Number of natural numbers less than n which are

relatively prime with n.
• ϕ(p) = p-1; p is a prime.
• If n = p*q, then ϕ(n) = (p-1)*(q-1), where p and q are
primes and p ≠ q
m m m-1
• If n=p , ϕ(n) = p -p
Proof for ϕ(n)=ϕ(p*q)=ϕ(p)*ϕ(q)
Proof for ϕ(n)=ϕ(p*q)=ϕ(p)*ϕ(q)(Contd..)
Euler’s Theorem
ϕ(n)
If GCD(a,n) = 1, then a ≡ 1 (mod n)
Euler’s
Theorem
(Proof)
Euler’s
Theorem
(Proof)
 40 • GCD(33,100) = 1
33 mod 100 2 2 2 2
• ϕ(100)= ϕ(2 ) * ϕ(5 ) = (2 -2)*(5 -5) = 40
= ? 40
• Hence 33 mod 100 = 1
 • GCD(77, 240)=1
4
• ϕ(240) = ϕ(2 ) * ϕ(3) * ϕ(5) = 8*2*4 = 64
64
1218
77 mod 240 • 77 mod 240 = 1
1218 64 19 2
= ? • 77 mod 240 = [(77 mod 240) * 77
mod 240] mod 240
1218
• 77 mod 240 = (1*169) mod 240 = 169
PRIMALITY TESTING
Primality Testing (Properties)
Miller Rabin
Algorithm
(MLA)
Miller Rabin Algorithm (Proof)
 MLA on 105

• n = 105
k
• n-1 = 2 * q
3
• 104 = 2 * 13; where k=3 and q=13
• Select a = 2
• aq mod n = 213 mod 105 = 2
• a2*q mod n = (aq mod n)2 mod n = 22 mod 105 = 4
4*q 2*q 2 2
• a mod n = (a mod n) mod n = 4 mod 105 = 16
• Hence, 105 is composite
 MLA on 35

• n = 35
• n-1 = 2k * q i.e. 34 = 21 * 17; where k=1 and q=17
• Select a=2
• aq mod n = 217 mod 35 = 32
• Hence 35 is composite
 MLA on 233

• n = 233
• n-1 = 2k * q i.e. 232 = 23 * 29; where k=3 and q=29
• Select a = 2
• aq mod n = 229 mod 233 = 1
• Hence, 233 is a prime
 MLA on 61

• n = 61
• n-1 = 2k * q i.e. 60 = 22 * 15; where k=2 and q=15
• Select a = 2
• aq mod n = 215 mod 61 = 11
• a2*q mod n = (aq mod n)2 mod n = 112 mod 61 = 60
• Hence, 61 is prime
 MLA on 241

• n = 241
• n-1 = 2k * q i.e. 240 = 24 * 15; where k=4 and q=15
• Select a = 2
• aq mod n = 215 mod 241 = 233
• a2*q mod n = (aq mod n)2 mod n = 2332 mod 241 = 64
4*q 2*q 2 2
• a mod n = (a mod n) mod n = 64 mod 241 = 240
• Hence, 241 is prime
Probabilistic Considerations for MLA

• Probability that MLA detects a pseudo prime is (1/4) for a particular

base.
• When MLA is executed for ‘t’ bases, then the probability that it
detects a pseudo-prime is 4-t.
• For example, the probability that MLA detects a pseudo-prime when
10 bases are used = 9.5367*10-7
CHINESE REMAINDER THEOREM (CRT)
 • Let m1, m2, m3, …………. mk, be a pairwise relatively
prime integers. If a1, a2, …….ak ∈ Z, then there exists
x∈Z, which satisfies the linear set of congruences:-
x≡a1 (mod m1)
x≡a2 (mod m2)
………
CRT x≡ak (mod mk)
algorithm where M = m1*m2*……..*mk
• Mi = M/mi
• x= (a1*M1*N1 + a2*M2*N2 + …………+ak*Mk*Nk)
mod M
where Ni = MI(Mi) mod mi
 CRT Example 1:-
• Solve for x:-

• a1 = 1, a2 = 2, a3 = 3, m1 = 5, m2 = 6, m3 = 7;
• M = m1*m2*m3 = 5*6*7 = 210
• M1 = M/m1 = 210/5 = 42
• M2 = M/m2 = 210/6 = 35
• M3 = M/m3 = 210/7 = 30
 CRT Example 1 (Contd..)
• N1 = MI(M1) (mod m1)
• N1 = MI(42) (mod 5)

q a b r u1 u2 u
8 42 5 2 1 0 1
2 5 2 1 0 1 -2
2 2 1 0 1 -2 5
1 0 -2 5

• N1 = -2 (mod 5) = 3
 CRT Example 1 (Contd..)
• N2 = MI(M2) (mod m2)
• N2 = MI(35) (mod 6)

q a b r u1 u2 u
5 35 6 5 1 0 1
1 6 5 1 0 1 -1
5 5 1 0 1 -1 6
1 0 -1 6

• N2 = -1 mod 6 = 5
 CRT Example 1 (Contd..)
• N3 = MI(M3) (mod m3)
• N3 = MI(30) (mod 7)

q a b r u1 u2 u
4 30 7 2 1 0 1
3 7 2 1 0 1 -3
2 2 1 0 1 -3 7
1 0 -3 7

• N3 = -3 mod 7 = 4
 CRT Example 1 (Contd..)
• x = (a1*M1*N1 + a2*M2*N2 + a3*M3*N3) mod M
• x = (1*42*3 + 2*35*5 + 3*30*4) mod 210 = 206
 CRT Example 2:-
• Solve for x:-

• a1 = 3, a2 = 4, a3 = 11, a4 = 6 m1 = 5, m2 = 8, m3 = 13, m4 = 17;

• M = m1*m2*m3*m4 = 5*8*13*17 = 8840
• M1 = M/m1 = 8840/5 = 1768
• M2 = M/m2 = 8840/8 = 1105
• M3 = M/m3 = 8840/13 = 680
• M4 = M/m4 = 8840/17 = 520
 CRT Example 2 (Contd..)
• N1 = MI(M1) (mod m1)
• N1 = MI(1768) (mod 5)

q a b r u1 u2 u
353 1768 5 3 1 0 1
1 5 3 2 0 1 -1
1 3 2 1 1 -1 2
2 2 1 0 -1 2 -5
1 0 2 -5
• N1 = 2
 CRT Example 2 (Contd..)
• N2 = MI(M2) (mod m2)
• N2 = MI(1105) (mod 8)

q a b r u1 u2 u
138 1105 8 1 1 0 1
8 8 1 0 0 1 -8
1 0 1 -8

• N2 = 1
 CRT Example 2 (Contd..)
• N3 = MI(M3) (mod m3)
• N3 = MI(680) (mod 13)

q a b r u1 u2 u
52 680 13 4 1 0 1
3 13 4 1 0 1 -3
4 4 1 0 1 -3 13
1 0 -3 13

• N3 = -3 mod 13 = 10
 CRT Example 2 (Contd..)
• N4 = MI(M4) (mod m4)
• N4 = MI(520) (mod 17)

q a b r u1 u2 u
30 520 17 10 1 0 1
1 17 10 7 0 1 -1
1 10 7 3 1 -1 2
2 7 3 1 -1 2 -5
3 3 1 0 2 -5 17
1 0 -5 17

• N4 = -5 mod 17 = 12
 CRT Example 2 (Contd..)
• x = (a1*M1*N1 + a2*M2*N2 + a3*M3*N3 + a4*M4*N4) mod M
• x = (3*1768*2 + 4*1105*1 + 11*680*10 + 6*520*12) mod 8840 = 3508
DISCRETE LOGARITHMS
 Order of an Integer a mod n
• Ordern(a)= smallest natural number k such that ak mod n = 1; where
GCD(a,n)=1, 1≤a<n, and 1≤k≤ϕ(n).
• Order7(2) = 3
• Order5(3) = 4
• Order15(8) = 4
• Order9(8) = 2
• Order8(1) = 1
 Ord11(8) = ?
• GCD(8,11) = 1
• ϕ(11) = 10
1
• 8 mod 11 = 8
2
• 8 mod 11 = 9
3
• 8 mod 11 = 6
4
• 8 mod 11 = 4
5
• 8 mod 11 = 10
6
• 8 mod 11 = 3
7
• 8 mod 11 = 2
8
• 8 mod 11 = 5
9
• 8 mod 11 = 7
10
• 8 mod 11 = 1
• Therefore Ord11(8) = 10
 Ord9(4) = ?
• GCD(4,9) = 1
• 41 mod 9 = 4
• 42 mod 9 = 7
3
• 4 mod 9 = 1
• Therefore Ord9(4) = 3
 Ord12(8) = ?

• GCD(8,12) = 4.
• Therefore Ord12(8) doesn’t exist.
 Primitive Roots of n
• ‘a’ is a primitive root of n if Ordn(a) = ϕ(n).
α
• All αn don’t have primitive roots. For n to have primitive roots, n=2, 4, p ,
2*p , where p is any odd prime, α is a natural number
• Examples of natural numbers having primitive roots are 2,3,4,5,6,7,9,10,11,
etc.
• Examples of natural numbers which don’t have primitive roots are 8, 12, 15,
etc.
• Primitive roots of 7 are 3 and 5.
• Primitive roots of 5 are 2 and 3.
 Primitive Roots of 11
• ϕ(11) = 10
a=1:-
1
• 1 mod 11
• Ord11(1) = 1
• Hence 1 is not a primitive root of 11
a=2:-
1
• 2 mod 11 = 2
2
• 2 mod 11 = 4
3
• 2 mod 11 = 8
4
• 2 mod 11 = 5
5
• 2 mod 11 = 10
6
• 2 mod 11 = 9
 Primitive Roots of 11 (Contd..)
• 27 mod 11 = 7
• 28 mod 11 = 3
• 29 mod 11 = 6
• 210 mod 11 = 1
• Ord11(2) = 10
• Hence 2 is a primitive root of 11
a=3:-
• 31 mod 11 = 3
• 32 mod 11 = 9
• 33 mod 11 = 5
• 34 mod 11 = 4
• 35 mod 11 = 1
• Ord11(3) = 5
• Hence, 3 is not a primitive root of 11
 Primitive Roots of 11 (Contd..)
a=4:-
1
• 4 mod 11 = 4
2
• 4 mod 11 = 5
3
• 4 mod 11 = 9
4
• 4 mod 11 = 3
5
• 4 mod 11 = 1
• Ord11(4) = 5
• Hence 4 is not a primitive root of 11

a=5:-
• Ord11(5) = 5
• Hence , 5 is not a primitive root of 11.
 Primitive Roots of 11 (Contd..)
a=6:-
• Ord11(6) = 10
• Hence , 6 is a primitive root of 11.
a=7:-
• Ord11(7) = 10
• Hence , 7 is a primitive root of 11.
a=8:-
• Ord11(8) = 10
• Hence , 8 is a primitive root of 11.
 Primitive Roots of 11 (Contd..)
a=9:-
• Ord11(9) = 5
• Hence , 9 is not a primitive root of 11.
a=10:-
• Ord11(10) = 2
• Hence , 10 is not a primitive root of 11.

• Therefore, the primitive roots of 11 are 2, 6, 7, and 8

 Primitive Roots of 2
•n=2
• ϕ(2) = 1
• 11 mod 2 = 1
• Hence, Ord2(1) = 1
• The primitive root of 2 is 1.
 Primitive Roots of 4
•n=4
• ϕ(4) = 2
• Ord4(1) = 1
• GCD(2,4) = 2; Hence 2 can’t be a primitive root of 4
• Ord4(3) = 2
• Hence 3 is a primitive root of 4
 Primitive Roots of 9
• n = 9 = 32; Here p = 3, and α=2
2
• ϕ(9) = 3 – 3 = 6
• Ord9(1) = 1
• Ord9(2) = 6; Hence 2 is a primitive root
• GCD(3,9) = 3
• Ord9(4) = 3
• Ord9(5) = 6; Hence 5 is a primitive root
• GCD(6,9) = 3
• Ord9(7) = 3
• Ord9(8) = 2
• The primitive roots of 9 are 2 and 5.
 Primitive Roots of 20
• 20 cannot be expressed as pα or 2*pα
• Hence 20 doesn’t have any primitive root.
 Observations Regarding Primitive Roots
• If a is a primitive root of n, then the set {a1, a2, ………, aϕ(n)} (mod n)
contain unique elements and are relatively prime to n.
1 2 3 4 5 6
• For example, the set {2 , 2 , 2 , 2 , 2 , 2 } (mod 9) = {2, 4, 8, 7, 5, 1}
contains unique elements which are relatively prime to 9.
 Discrete Logarithms
• If b = ax mod n, then discrete logarithm is given by x = dloga,n(b),
where GCD(b,n) = 1 and ‘a’ is a primitive root of n.
• Calculating Discrete Logarithms is a relatively harder problem than
exponentiation.

x
Calculate the Discrete logarithm x, where 3 mod 7 = 4:-
• GCD(4,7) = 1
• Ord7(3) = 6;
• Min value of x = 4.
• Therefore, x = 4+6*k, where k ∈ W.
 x
Solve for x:- 5 (mod 18) = 11
• GCD(11,18) = 1
• Ord18(5) = 6
• Min value of x = 5
• Therefore, x = 5+6*k, where k ∈ W.