# Introduction to finite fields: Fields and rings

Fields and rings

To understand IDEA, AES, and some other modern crypto systems , it is necessary to
understand a bit about finite fields.

A field is an algebraic object . The elements of a field can be added and subtracted and
multiplied and divided (except by 0). Often in undergraduate mathematics courses (e.g.,
calculus and linear algebra ) the numbers that are used come from a field. The rational
numbers: form a field; fractions can be added (and
subtracted) and multiplied (and divided). The real numbers form a field. The
complex numbers form a field. RC

Number theory studies the integers Z. The integers do not form a field. Integers can be
added (and subtracted) and multiplied, but integers cannot always be divided. Sure, 6
divided by 3 is 2; but 5 divided by 2 is not an integer; is a rational number . The
integers form a ring, but the rational numbers form a field.

Similarly the polynomials with integer coefficients form a ring. We can add (and
subtract) polynomials with integer coefficients, and the result will be a polynomial with
integer coefficients. We can multiply polynomials with integer coefficients, and the
result will be a polynomial with integer coefficients. But, we cannot always divide
polynomials with integer coefficients: , but is not a
polynomial – it is a rational function. The polynomials with integer coefficients do not
form a field, they form a ring. The rational functions with integer coefficients form a
field.

A field has two operations ; they are usually written as addition and multiplication.
Subtraction is just the inverse of addition; it is adding the additive inverse
(e.g., 5 – 4 = 5 + (-4) = 1). Division is just the inverse of multiplication; it is multiplying
by the multiplicative inverse (e.g., ). A ring also has two
operations
– addition and multiplication – and, although addition is as sumed to have an
inverse
, in a ring it is not assumed that multiplication has an inverse. (Addition and
multiplication are also assumed to have several other properties . For both a ring and a
field, it is assumed that addition commutes and is associative. For both a ring and a field,
it is assumed that multiplication distributes over addition. For a field but not for a ring,
multiplication is assumed to be commutative.)

The fields that we commonly used in mathematics courses (, , and C) are infinite.
For crypto logical purposes , finite fields are useful.

Finite field of p elements

Recall that the integers mod 26 do not form a field. The integers modulo 26 can be added
and subtracted, and they can be multiplied (so they do form a ring). But, recall that only
1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25 have multiplicative inverses mod 26; these are
the only numbers by which we can divide. These twelve numbers are the positive
integers that are less than or equal to 26 and relatively prime to 26.

Recall that given an integer that is less than or equal to n and relatively prime to n we
can use the extended Euclidean algorithm to find its inverse mod n. So, it is possible to
construct the multiplicative inverses of 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25 modulo
26. If the modulus is prime, we can construct an inverse for each positive integer that is
less than or equal to the modulus.. So, for each prime p we can construct a finite field of
p elements – the integers mod p.

The integers mod 5 is a field of 5 elements {0, 1, 2, 3, 4}. Here are the addition and
multiplication tables:

 number additive number multiplicative inverse

The identity for addition is 0, and the identity for multiplication is 1. This is a field. We
denote the field of 5 elements by

Here is the finite field of 3 elements.

Here is the finite field of 2 elements .

Viewing 0 and 1 as bits, + is just XORing bits, and multiplication is … well,
multiplication is not too interesting.

The American mathematician E.H. Moore (1862 – 1932) proved in 1893 that the number
of elements of a finite field must be for some prime p and positive integer n, and he
proved that for each prime p and positive integer n there is an essentially unique field of
elements.

 Prev Next

Start solving your Algebra Problems in next 5 minutes!

 Algebra Helper Download (and optional CD) Only \$39.99 Click to Buy Now: OR
2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of June 18th you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!

 Algebra Helper Download (and optional CD) Only \$39.99 Click to Buy Now: OR
2Checkout.com is an authorized reseller
of goods provided by Sofmath

 "It really helped me with my homework.  I was stuck on some problems and your software walked me step by step through the process..." C. Sievert, KY

 Sofmath 19179 Blanco #105-234San Antonio, TX 78258 Phone: (512) 788-5675Fax: (512) 519-1805
 Home   : :   Features   : :   Demo   : :   FAQ   : :   Order Copyright © 2004-2018, Algebra-Answer.Com.  All rights reserved.