Cryptography Reference
In-Depth Information
Let
G
be a finite Abelian group. The classification of finite Abelian groups (see Theorem
II.2.1 of [
271
] or Section I.8 of [
329
]) states that
G
is isomorphic to a direct sum of cyclic
groups of orders
m
1
,m
2
,...,m
t
such that
m
1
|
m
2
|···|
m
t
.
A.3 Rings
All rings in this topic have a multiplicative identity 1. For any ring
R
, the smallest positive
integer
n
such that
n
1
0 is called the
characteristic
of the ring and is denoted char(
R
).
If there is no such
n
then we define char(
R
)
=
=
0.
If
R
is a ring and
n
∈ N
then we write
M
n
(
R
) for the ring of
n
×
n
matrices with entries
in
R
.
If
R
is a ring then
R
∗
is the multiplicative group of invertible elements of
R
.The
Euler
phi function
ϕ
(
n
) is the order of (
)
∗
. One has
Z
/n
Z
1
.
n
p
|
n
1
p
ϕ
(
n
)
=
−
Theorem A.3.1
There exists N
∈ N
such that ϕ
(
n
)
>n/
(3 log(log(
n
)))
for all n
∈ N
>N
.
Proof
Theorem 328 of [
250
] states that
ϕ
(
n
) log(log(
n
))
n
e
−
γ
lim inf
n
→∞
=
0
.
57721566 is the Euler-Mascheroni constant. Since
e
−
γ
where
γ
≈
≈
0
.
56
>
1
/
3, the
result follows from the definition of lim inf.
∈
∈
R
∗
and
a
=
∈
∈
R
∗
or
An element
a
R
is
irreducible
if
a
bc
for
b,c
R
implies
b
R
∗
. We write
a
c
∈
|
b
for
a,b
∈
R
if there exists
c
∈
R
such that
b
=
ac
. An element
a
∈
R
is
prime
if
a
|
bc
implies
a
|
b
or
a
|
c
.
An integral domain
R
is a
unique factorisation domain
(UFD) if each
a
R
can be
written uniquely (up to ordering and multiplication by units) as a product of irreducibles.
In a UFD, an element is prime if and only if it is irreducible.
∈
A.4 Modules
Let
R
be a ring. An
R
-module
M
is an Abelian group, written additively, with an operation
rm
for
r
∈
R
and
m
∈
M
such that (
r
1
+
r
2
)
m
=
r
1
m
+
r
2
m
and
r
(
m
1
+
m
2
)
=
rm
1
+
rm
2
.An
R
-module
M
is
finitely generated
if there is a set
{
m
1
,...,m
k
}⊂
M
such that
={
i
=
1
r
i
m
i
:
r
i
∈
M
.
A finitely generated
R
-module
M
is a
free module
if there is a set
R
}
{
m
1
,...,m
k
}
that
=
i
=
1
r
i
m
i
if and only if
r
i
=
generates
M
and is such that 0
0 for all 1
≤
i
≤
k
. Such
an
R
-module is said to have
rank
k
.
Let
R
be a commutative ring,
M
an
R
-module and
k
a field containing
R
. Consider the set
of all symbols of the form
m
⊗
a
where
m
∈
M
,
a
∈ k
under the equivalence relation
rm
⊗
a
≡
m
⊗
ra
for
r
∈
R
,(
m
1
+
m
2
)
⊗
a
=
(
m
1
⊗
a
)
+
(
m
1
⊗
a
) and
m
⊗
(
a
1
+
a
2
)
=
(
m
⊗
a
1
)
is the set of all equivalence classes of such
symbols. If
M
is a finitely generated free
R
-module with generating set
+
(
m
⊗
a
2
). The
tensor product
M
⊗
R
k
{
m
1
,...,m
k
}
then
M
⊗
R
k
is a
k
-vector space of dimension
k
with basis
{
m
1
⊗
1
,...,m
k
⊗
1
}
.
