Cryptography Reference
In-Depth Information
Let
α
∈ F
q
m
.The
trace
and
norm
with respect to
F
q
m
/
F
q
are
m
−
1
m
−
1
α
q
i
α
q
i
.
Tr
F
q
m
/
F
q
(
α
)
=
and
N
F
q
m
/
F
q
(
α
)
=
i
=
0
i
=
0
=
m
−
1
i
=
0
α
q
i
)
The
characteristic polynomial
over
F
q
of
α
∈ F
q
m
is
F
(
x
)
(
x
−
∈ F
q
[
x
].
∈ F
q
m
are (up to sign) the coefficients of
x
m
−
1
The trace and norm of
α
and
x
0
in the
characteristic polynomial.
An element
α
∈ F
q
is a
square
or
quadratic residue
if the equation
x
2
=
α
has a
F
q
then
g
a
is a square if and only if
a
is even.
solution
x
∈ F
q
.If
g
is a primitive root for
F
q
if and only if
α
(
q
−
1)
/
2
=
Hence,
α
is a square in
1.
Lemma A.8.4
Let g
∈ F
q
m
, where m>
1
, be chosen uniformly at random. The probability
that g lies in a proper subfield K
⊂ F
q
m
such that
F
q
⊆
K is at most
1
/q.
2 then the probability is
q/q
2
Proof
If
m
=
=
1
/q
so the result is tight in this case.
l
i
is a power of a prime
l
When
m
=
≥
2 then all proper subfields of
F
q
m
that contain
F
q
l
i
−
1
so the probability is
q
l
i
−
1
/q
l
i
1
/q
l
i
−
1
(
l
−
1)
F
q
are contained in
=
≤
1
/q
. Finally, write
nl
i
where
l
m
=
≥
2isprime,
i
≥
1,
n
≥
2 and gcd(
n,l
)
=
1. Then every proper subfield
containing
F
q
lies in
F
q
l
i
or
F
q
nl
i
−
1
. The probability that a random element lies in either of
these fields is
≤
q
l
i
/q
nl
i
q
nl
i
−
1
/q
nl
i
1
/q
l
i
(
n
−
1)
1
/q
nl
i
−
1
(
l
−
1)
1
/q
2
1
/q
2
+
=
+
≤
+
≤
1
/q.
A.9 Ideals
If
R
is a commutative ring then an
R
-
ideal
is a subset
I
⊂
R
that is an additive group and is
such that, for all
a
∈
I
and
r
∈
R
,
ar
∈
I
.An
R
-ideal
I
is proper if
I
=
R
and is non-trivial
if
I
={
0
}
.A
principal ideal
is (
a
)
={
ar
:
r
∈
R
}
for some
a
∈
R
.If
S
⊂
R
then (
S
)is
{
i
=
1
s
i
r
i
:
n
the
R
-ideal
∈ N
,s
i
∈
S,r
i
∈
R
}
. An ideal
I
is
finitely generated
if
I
=
(
S
)
R
:
r
n
for a finite subset
S
⊂
R
.The
radical
of an ideal
I
inaring
R
is rad
R
(
I
)
={
r
∈
∈
I
for some
n
(see Definition VIII.2.5 and Theorem VIII.2.6 of Hungerford [
271
]). If
I
1
and
I
2
are ideals of
R
then
∈ N}
n
.
I
1
I
2
=
a
i
b
i
:
n
∈ N
,a
i
∈
I
1
,b
i
∈
I
2
i
=
1
Note that
I
1
I
2
⊆
(
a
)(
b
).
Let
I
1
,...,I
n
be ideals in a ring
R
such that the ideal (
I
i
∪
I
1
∩
I
2
.For
a,b
∈
R
one has (
ab
)
=
I
j
)
=
R
for all 1
≤
i<j
≤
n
(we call such ideals pairwise-coprime). If
a
1
,...,a
n
∈
R
then there exists an element
a
∈
R
such that
a
n
.Thisisthe
Chinese
remainder theorem
for rings; see Theorem III.2.25 of [
271
] or Theorem II.2.1 of [
329
].
The following result gives three equivalent conditions for an ideal to be prime.
≡
a
i
(mod
I
i
) (in other words,
a
−
a
i
∈
I
i
) for all 1
≤
i
≤
Lemma A.9.1
Let I be an ideal of R. The following conditions are equivalent and, if they
hold, I is called a
prime ideal
:
1. If a,b
I.
2. R/I is an integral domain (i.e., has no zero divisors).
3. If I
1
and I
2
are ideals of R such that I
1
I
2
⊆
∈
R are such that ab
∈
I then a
∈
I or b
∈
I then I
1
⊆
I or I
2
⊆
I.
