Cryptography Reference
In-Depth Information
We see that this is a generator of the multiplicative group of the field. To check
in a more explicit way that this is indeed the case, we would apply Proposition 2.6
as follows:
> ifactor(255);
(3) (5) (17)
> F256:-'ˆ'(a, 85);
(xˆ7 + xˆ5 + xˆ4 + xˆ3 + xˆ2 + 1) mod 2
> F256:-'ˆ'(a, 51);
(xˆ3 + xˆ2) mod 2
> F256:-'ˆ'(a, 15);
xˆ5 + xˆ4 + xˆ2 + 1) mod 2
We see that when a is raised to the exponents obtained by dividing the order of
the group, 255, by each of its prime factors, an element different from the identity
is obtained. Thus the order of a must be equal to the order of the multiplicative
group, i.e., 255, and hence a is a generator. If we want to obtain a generator, we just
compute:
> randomize():
F256:-PrimitiveElement();
(xˆ7 + xˆ4) mod 2
Exercise 2.39 Write a Maple function that tests whether a given element of a finite
field defined by means of the GF package is a generator of the multiplicative group
of the field and another one that finds a generator by pseudo-randomly selecting
elements of the field and applying the previous function to check whether they
are generators. (Hint: One may have a look at Maple's code for the correspond-
ing functions by printing the module GF ; this requires executing interface
(verboseproc = 2) and then print(GF) .)
2.9 Quadratic Residues and Modular Square Roots
In this section we study quadratic residues and some related algorithms that have
interesting cryptographic applications.
2.9.1 Quadratic Residues and the Legendre and Jacobi
Symbols
Definition 2.26 Let a be an integer and n
>
1. We say that a is a quadratic residue
1 and the congruence x 2
modulo n if gcd
has a solution. In
other words, a is a quadratic residue if and only if a mod n is a square in
(
a
,
n
) =
a
(
mod n
)
Z n .If a
is not a quadratic residue modulo n then we say that a is a quadratic non - residue
modulo n .
 
Search WWH ::




Custom Search