Page 18 - Hardware Implementation of Finite-Field Arithmetic
P. 18
CHAPTER 1
Mathematical
Background
his chapter presents some topics in mathematics; it is intended to
make this book self-contained. For further details the reader can
Trefer to textbooks on Algebra ([Coh93], [GN03], [Her75],
[Hun74]), Number Theory ([Kob94], [Ros92], [Ros00], [Gar59]), Finite
Fields ([LN83], [LN94], [McC87], [Men93]), and Cryptography [MOV96],
from where the following material has been mainly extracted.
1.1 Number Theory
1.1.1 Basic Definitions
Definitions 1.1
1
1. The set of natural numbers N = {0, 1, 2, 3, . . .}.
2. The set of integers Z = { . . . , −3, −2, −1, 0, 1, 2, 3, . . . }.
Definition 1.2 Given two integers x and y, y divides x (y is a divisor of x)
if there exists an integer z such that x = zy.
Definition 1.3 Given two integers x and y, with y > 0, there exist two
integers q (the quotient) and r (the remainder ) such that
x = qy + r where 0 ≤ r < y
It can be proven that q and r are unique.
Then (notation)
r = x mod y q = x div y
An alternative definition:
1 For convenience, the element zero has been included in N.
1
