Modular arithmetic is a kind of integer arithmetic that reduces all numbers to one of a fixed set [0, . . . , n - 1] for some number n. Any integer outside this range is reduced to one in this range by taking the remainder after divi- sion by n.

Chapter 4 **BASIC**** ****CONCEPTS IN NUMBER THEORY
****AND FINITE FIELDS**

**
****Divisibility and The Division
Algorithm**

**
****The**** ****Euclidean Algorithm**

**
****Modular Arithmetic**

**
****Groups,
Rings, and Fields**

**
****Finite Fields of the Form GF( p)**

**
****Polynomial**** ****Arithmetic**

**
****Finite Fields of the Form GF(2***n***)**

**KEY POINTS**

◆
Modular arithmetic is a kind of integer
arithmetic that reduces all numbers to one of a fixed set [0, . . . , *n *- 1] for some number *n*. Any integer
outside this range is reduced
to one in this range by taking the remainder
after divi- sion by *n*.

◆
The greatest common
divisor of two integers is the largest
positive integer that exactly
divides both integers.

◆
A field is a set of elements
on which two arithmetic operations (addition and
multiplication) have been defined
and which has the properties of ordinary arithmetic,
such as closure, associativity,
commutativity, distributivity, and
having both additive
and multiplicative inverses.

◆
Finite fields are important in several areas
of cryptography. A finite
field is simply a field with
a finite number of elements. It can
be shown that the order of a finite field
(number of elements
in the field) must be a power
of a prime *p**n*, where
*n
*is a positive integer.

◆
Finite fields of order *p *can
be defined using
arithmetic mod *p*.

◆
Finite fields of order *p**n*, for *n *> 1, can be defined using
arithmetic over polynomials.

Finite fields have become increasingly important in cryptography. A number
of crypto- graphic algorithms rely heavily on properties of finite fields, notably
the Advanced Encryption Standard (AES) and elliptic curve cryptography. Other examples
include the message authentication code CMAC and the authenticated encryption scheme GMC.

This chapter provides the reader with sufficient
background on the concepts of
finite fields to be able to understand the design of AES and other cryptographic algorithms that use finite
fields. The first three sections introduce basic concepts from number theory that are needed
in the remainder of the chapter; these
include divisibility, the Euclidian algorithm, and modular arithmetic. Next comes a brief overview of the concepts of
group, ring, and field. This section is somewhat abstract; the reader may
prefer to quickly skim this section on a first reading. We

are then ready to discuss finite fields of
the form GF(*p*),
where *p *is a prime num-

ber. Next,
we need some additional background,
this time in polynomial arith- metic. The chapter concludes with a
discussion of finite fields of the form GF(2*n*), where *n *is a positive integer.

The concepts and techniques of
number theory are quite abstract, and it is often difficult to grasp them intuitively
without examples. Accordingly, this chapter and Chapter 8 include a number of examples, each of which is highlighted
in a shaded box.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : One Symmetric Ciphers : Basic Concepts in Number Theory and Finite Fields : Basic Concepts in Number Theory and Finite Fields |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.