Information Technology Reference
In-Depth Information
Number Theory.
The
Euler totientfunction
,
ˆ
(
n
),counts the number of integers in
the interval [1
,n
−
1] that are relatively prime to
n
. It can be calculated from the prime
factorization
n
=
p
r
i
i
by the formula
ˆ
(
n
)=
p
r
i
−
1
i
(
p
i
−
1)
.
A
Sophie Germain prime
is a prime number
p
such that 2
p
+1is also prime [17]. It
has been conjectured that there are infinitely many of them, but the conjecture remains
unsolved. The significance of these primes for usisthat,when
p
is a Sophie Germain
prime,
ˆ
(2
p
+1)has the large prime factor
p
. An easy construction gives a number
n
for which
ˆ
(
n
) has a prime factor of size
ʩ
(
√
n
):simplylet
n
=
p
2
for a prime
p
, with
ˆ
(
n
)=
p
(
p
−
1). Baker and Harman [18] proved the following stronger bound.
Lemma 4 (Baker and Harman [18]).
Fo r i nfinitely many prime numbers
p
,thelargest
primefactor of
ˆ
(
p
)
is atleast
p
0
.
677
.
Field Theory.
A
field
is a system of values and arithmetic operations over them
(addition, subtraction, multiplication, and division) obeying similar axioms to those of
rational arithmetic, real number arithmetic, and complex number arithmetic: addition
and multiplication are commutative and associative, multiplication distributes over ad-
dition, subtraction is inverse to addition, and division is inverse to multiplication by
any value except zero. A field
K
is an
extension
of a field
F
,and
F
is a
subfield
of
K
(the
base field
), if the elements of
F
are a subset of those of
K
andthetwofields'
operations coincide for those values.
K
can be viewed as a vector space over
F
(values
in
K
can be added to each other and multiplied by values in
F
)andthe
degree
[
K
:
F
]
of the extension is its dimension as a vector space. For an element
ʱ
of
K
the notation
F
(
ʱ
) represents the set of values that can be obtained from rational functions (ratios
of univariate polynomials) with coefficients in
F
by plugging in
ʱ
as the valueofthe
variable.
F
(
ʱ
) is itself a field, intermediate between
F
and
K
. In particular, we will
frequently consider field extensions
Q
(
ʱ
) where
Q
is the field of rational numbers and
ʱ
is an
algebraic number
, the complex root of a polynomial with rational coefficients.
Lemma 5.
If
ʱ
can be computed byaroot computation tree of degree
f
(
n
)
,then
[
Q
(
ʱ
):
Q
]
is
f
(
n
)
-smooth, i.e., it has noprimefactor
>f
(
n
)
.In particular, i f
ʱ
can be computed byaquadratic computation tree, then
[
Q
(
ʱ
):
Q
]
is a power of two.
Proof.
See the full version of the paper.
A
primitive root of unity
ʶ
n
is a root of
x
n
1 whose powers give all other roots of
the same polynomial. As a complex number we can take
ʶ
n
=exp(2
iˀ/n
).
−
Lemma 6 (Corollary 9.1.10 of [19], p. 235).
[
Q
(
ʶ
n
):
Q
]=
ˆ
(
n
)
.
Galois Theory.
A
group
is a system of values and a single operation (written as
multiplication) that is associative and in which every element has an inverse. The set
of permutations of the set [
n
]=
,multiplied by function composition, is a
standard example of a group and is denoted by
S
n
.A
permutationgroup
is a subgroup
of
S
n
; i.e., it is a set of permutations that is closed under the group operation.
{
1
,
2
,...,n
}
