Discrete Mathematics - Contemporary Cryptography - page 91

where all b i ∈ Z 2 (0 7). Thus, any element in this field can be represented as

a word of 8 binary digits (bits), or a byte. Conversely, any byte can also be viewed
as an element in the field

≤ i ≤

F 2 [ x ] f . For example, the byte 11010111 can be viewed as
polynomial x 6 + x 4 + x 2 + x +1.

3.3.7 Quadratic Residuosity

In integer arithmetic, an x such that

x = y 2 .Ifsucha y exists, then it is called a square root of x . For example, 25 is a
square with square root 5, whereas 20 is not a square. Similarly, all negative numbers
are not squares. If an integer x is a square, then it has precisely two square roots, and
these values can be computed efficiently from x (even if x is very large).
In modular arithmetic, things are more involved. Similar to perfect squares
and square roots in

∈ Z is a perfect square if there is a y ∈ Z

,weusetheterms quadratic residues (corresponding to perfect
squares) and square roots in

Z

Z n . Quadratic residues play an important role in number
theory. For example, many integer factoring algorithms employ quadratic residues
(see Section 7.3), and quadratic residues also have applications in asymmetric
encryption systems and cryptographic protocols. The notions of a quadratic residue
and a square root are formally introduced in Definition 3.31.

∈ Z n is a

Definition 3.31 (Quadratic residue and square root) An element x

∈ Z n such that x =
y 2 (mod n ) .Ifsucha y exists, then it is called a square root of x modulo n .

quadratic residue modulo n if there exists an element y

Z n , denoted by QR n , is formally

The resulting set of quadratic residues in

defined as follows:

∈ Z n |∃ ∈ Z n : y 2

QR n := { x y ≡ x (mod n ) }

Z n .If x 1 ,x 2 ∈

Note that QR n is a multiplicative subgroup of QR n with

(because ( y 1 y 2 ) 2

square roots y 1 and y 2 , then the square root of x 1 x 2 is y 1 y 2 ≡

(mod n )) and the square root of x − 1
1

is y − 1
1

(because ( y − 1
1

y 1 y 2 ≡ ) 2 x 1 x 2 ≡

x − 1
1

( y 1 ) − 1 Z n is either a quadratic

residue or a quadratic nonresidue. Consequently, the set of all quadratic nonresidues
in

≡ (mod n )). Also note that every element in

Z n is the complement of QR n (with respect to Z n ). It is commonly referred to

Z n \

as QNR n (i.e., QNR n = QR n ). In order to further discuss the properties of

quadratic residues, one must distinguish the situation in which n is a prime or n is a
composite number. These two cases are discussed separately.