Scribd
Upload
22 views34 pages

UNit-1 - CHAPTER 3

The document discusses basic concepts in number theory and finite fields. It covers topics like the Euclidean algorithm for finding the greatest common divisor of two numbers, modular arithmetic, groups, rings and fields, polynomial arithmetic, and finite fields of the form GF(2n). Examples are provided to illustrate key concepts like using the Euclidean algorithm to find the GCD of large numbers, addition and multiplication tables modulo 8, and representing an 8-bit word as a polynomial.

Uploaded by

gomajaf572
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
22 views34 pages

UNit-1 - CHAPTER 3

The document discusses basic concepts in number theory and finite fields. It covers topics like the Euclidean algorithm for finding the greatest common divisor of two numbers, modular arithmetic, groups, rings and fields, polynomial arithmetic, and finite fields of the form GF(2n). Examples are provided to illustrate key concepts like using the Euclidean algorithm to find the GCD of large numbers, addition and multiplication tables modulo 8, and representing an 8-bit word as a polynomial.

Uploaded by

gomajaf572
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 34

Information Security

Chapter-3

BASIC CONCEPTS INNUMBER THEORY AND FINITE FIELDS

1
Information Security

2
Information Security

3
Information Security

Example:
Find the GCD of 270 and 192

 A=270, B=192
 A ≠0
 B ≠0
4
Information Security
 Use long division to find that 270/192 = 1 with a remainder of 78. We can write this as: 270 = 192 * 1
+78
 Find GCD(192,78), since GCD(270,192)=GCD(192,78)

A=192, B=78

 A ≠0
 B ≠0
 Use long division to find that 192/78 = 2 with a remainder of 36. We can write this as:
 192 = 78 * 2 + 36
 Find GCD(78,36), since GCD(192,78)=GCD(78,36)

A=78, B=36

 A ≠0
 B ≠0
 Use long division to find that 78/36 = 2 with a remainder of 6. We can write this as:
 78 = 36 * 2 + 6
 Find GCD(36,6), since GCD(78,36)=GCD(36,6)

A=36, B=6

 A ≠0
 B ≠0
 Use long division to find that 36/6 = 6 with a remainder of 0. We can write this as:
 36 = 6 * 6 + 0
 Find GCD(6,0), since GCD(36,6)=GCD(6,0)

A=6, B=0

 A ≠0
 B =0, GCD(6,0)=6

So we have shown:
GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6
GCD(270,192) = 6

Let us now look at an example with relatively large numbers to see the power of this algorithm:

5
Information Security

6
Information Security
MODULAR ARITHMETIC

7
Information Security

8
Information Security

Thus, the rules for ordinary arithmetic involving addition, subtraction, and multiplication carry over into
modular arithmetic.

9
Information Security
Table 4.2 provides an illustration of modular addition and multiplication modulo 8.

10
Information Security

11
Information Security

12
Information Security

13
Information Security

14
Information Security
GROUPS, RINGS, AND FIELDS

15
Information Security

16
Information Security

17
Information Security

18
Information Security

19
Information Security

POLYNOMIAL ARITHMETIC

20
Information Security

21
Information Security

22
Information Security

Euclidean Algorithm for Polynomials

23
Information Security

FINITE FIELDS OF THE FORM GF(2n)

24
Information Security

Representation of 8-bit word by a Polynomial

25
Information Security

26
Information Security

27
Information Security

28
Information Security

29
Information Security

30
Information Security

31
Information Security

32
Information Security

33
Information Security

34

You might also like