Cryptography Reference
In-Depth Information
App.23. If
K
is a field extension of
F
and
α
∈
Aut
(
K
), such that
α
(
f
)=
f
for all
f
F
, then
α
is called an
F
-automorphism of
K
. Prove that the
group of all
F
-automorphism of
K
is a subgroup of
Aut
(
F
). This group
is denoted by
∈
G
al
(
K/F
), called the
Galois group
of
K
over
F
.
App.24.
With reference to Exercise App.23, determine
G
al
(
C
/
R
).
(For a
detailed view of Galois theory and its ramifications, see [168].)
Exercises App.25-App.29 pertain to continued fractions. See pages 496-498.
App.25.
Suppose t
ha
t the period length
of the simple continued fraction
expansion of
√
D
is even. Prove that all (positive) solutions of the Pell
equation
x
2
−
Dy
2
= 1 for
D
∈
N
not a perfect square are given by
x
=
A
k
−
1
and
y
=
B
k
−
1
for
k
.
(
Hint: See Corollary A.3 on page 498.
)
∈
N
App.25. Prove that in the situation given in Exercise App.24, there are no
solutions to the Pell equation
x
2
Dy
2
=
−
−
1.
App.26.
Suppose t
ha
t the period length
of the simple continued fraction
expansion of
√
D
for nonsquare
D
∈
N
is odd.
Prove that all positive
solutions of
x
2
Dy
2
−
= 1 are given by
x
=
A
2
k
−
1
,
y
=
B
2
k
−
1
for
; and all solutions of
x
2
Dy
2
k
∈
N
−
=
−
1 are given by
x
=
A
(2
k
−
1)
−
1
,
y
=
B
(2
k
−
1)
−
1
for
k
∈
N
.
App.27. With reference to Theorem A.32 on page 498, prove that
G
k
−
1
=
P
k
B
k
−
1
+
Q
k
B
k
−
2
,
for any nonnegative integer
k
.
App.28.
If
is the period length of the simple continued fraction expansion
of
√
D
, show that
Q
j
=
Q
−
j
for 0
≤
j
≤
, and
P
−
j
=
P
j
+1
for
0
≤
j
≤
−
1.
App.29.
If
D
=
pq
whe
re
p
≡
q
≡
3 (mod 4) are primes with
p<q
, and
√
D
=
, prove that
is even. Also, verify that the following
Legendre symbol identity holds:
G.4
p
q
q
0
;
q
1
,...,q
=(
1)
/
2
.
−
App.30.
F
p
by
y
2
=
x
3
+
ax
+
b
for integers
a,b
. Prove that the number of points on
E
counting the point at infinity is given by the following Legendre symbol
formula.
Let
p
be a prime and define and elliptic curve
E
(
F
p
) over
x
3
+
ax
+
b
p
.
p
+1+
x
∈
F
p
(See pages 498 and 499.)
G.4
This idea and related issues have been substantially generalized by this author in [171].
Search WWH ::
Custom Search