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(2n)
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 pn, where
n
is a positive integer.
◆
Finite fields of order p can
be defined using
arithmetic mod p.
◆
Finite fields of order pn, 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(2n), 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.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.