Information Technology Reference
In-Depth Information
Now consider the last equalities modulo
p
,thatis
p
(
c
p
2
(
p−
1)
/
2
(mod
p
)
2
(
p−
1)
/
2
(mod
p
)
.
1
≡
2
p
−
2
l
)
±
≡±
We have 2 is a square in
3(mod8)
(see any book on elementary number theory). Now if 2 is a square (resp. non-
square) equality with + (resp.
F
p
if
p
≡±
1 (mod 8), and non-square if
p
≡±
−
) holds. That is, if 2 is a square (resp. non-square)
H
H
d
=2
p−
2
+2
(
p−
3)
/
2
(resp.
H
H
d
=2
p−
2
2
(
p−
3)
/
2
), which implies
∩
∩
−
(using (4))
Θ
d
(1) = +2
(
p
+1)
/
2
2
(
p
+1)
/
2
if
p
≡±
1(mod8)(resp.
Θ
d
(1) =
−
if
p
≡±
3 (mod 8)).
ProofofTheorem1:
We will prove the claim by induction on the length
l
=
e
1
+
+
e
r
of the prime decomposition
m
=
p
e
1
p
e
r
r
of
m
.
Base case
l
=1
:
We have
m
prime. This case is proved by Theorem 3. We
also prove for
l
= 2, as an example of the inductive step. Consider
m
=
pq
,
where
p, q
are odd primes. Recall that the sets
···
···
C
k
⊂
F
have cardinalities
c
k
given
c
2
m
.Since
x
d
by (1) and (2). Also, by Lemma 1,
|
H
∩C
k
|
=
for all
k
|
is a
permutation not only on
F
, but also on the restrictions to
C
k
, the intersections
H
d
∩C
k
satisfy
=
H
d
∩C
k
,
for all
k
|
H
∩C
k
|
|
m
.
Let
h
:=
H
H
d
and
h
k
:=
(
H
∩C
k
)
.Thenwehave
H
(
H
d
H
d
=
∩
∩C
k
)
∩
∩
k|m
(
H
∩C
k
), and
h
=
k|m
h
k
. Note that the numbers
h
k
satisfy
∩C
k
)
∩
(
H
d
k
|
h
k
.Since
d
is AB on subfields
F
2
p
,
F
2
q
,weget
h
k
for all
k
|
m
and
k
=
m
by
Theorem 3.
Note that 3
F
2
m
.Let
g
:=
H
H
3
∈
Gold
for any finite field
∩
and
g
k
:=
(
H
∩C
k
)
. Then we know
g
by Theorem 2. Note that
g
=
k|m
g
k
,
and
g
k
=
h
k
for
k
(
H
3
∩C
k
)
∩
|
m
and
k
=
m
by Theorem 3 and Theorem 2. Hence
g
m
,g
m
+2
(
m−
3)
/
2
,g
m
+2
2
(
m−
3)
/
2
2
(
m−
3)
/
2
,g
m
−
h
m
∈{
·
}
(or
h
m
∈{
g
m
,g
m
−
2
·
, depending on
m
)by(4).Nowsince
pq
2
(
m−
3)
/
2
2
(
m−
3)
/
2
,then
h
m
=
g
m
}
±
and therefore
h
=
g
.Notethat
m
is the so-called Jacobi symbol and is equal
to +1 (resp.
Z
2
m
−
1
.
Inductive step:
Now let the theorem be true for all
k
−
1) if 2 is a square (resp. non-square) in
|
m
, but
k
=
m
.Then
∈
Gold
we get
g
:=
H
H
3
and
g
k
:=
(
H
∩C
k
)
∩
∩C
k
)
∩
(
H
3
since 3
for all
k
=
m
, again inductively (starting
from
k
's with simpler prime decomposition). The divisibility argument above is
employed to get
h
m
=
g
m
and consequently
h
=
g
.
|
m
.Wealsoget
h
k
=
g
k
for
k
|
m
and
k
Now we will prove that all known AB exponents, i.e. Gold, Kasami, Welch and
Niho satisfy the assumption of the Theorem 1, that is they are AB on all sub-
fields.
Lemma 2.
Let
F
=
F
2
m
be a finite field,
m
odd, and
K
=
F
2
k
F
be an
arbitrary subfield. If
d
is an AB exponent in
∈
Gold
∪
Kasami
∪
Niho
∪
Welch
,then
d
is also AB in
K
. Moreover
d
belongs to the same subclass
of AB exponents in the subfield.
F
such that
d
