Cryptography Reference
In-Depth Information
Exercise 2.9.7
(Cipolla) Let
p
be prime and
a
∈ Z
. Show that if
t
∈ Z
is such that
(
t
2
−
4
a
p
1 then
x
(
p
+
1)
/
2
F
p
[
x
]
/
(
x
2
a
) is a square root of
a
modulo
p
. Hence,
write down an algorithm to compute square roots modulo
p
and show that it has expected
running time
O
(log(
p
)
M
(log(
p
))) bit operations.
)
=−
in
−
tx
+
We remark that, in some applications, one wants to compute a Legendre symbol to test
whether an element is a square and, if so, compute the square root. If one computes the
Legendre symbol using Euler's criterion as
a
(
p
−
1)
/
2
(mod
p
) then one will have already
computed
a
q
(mod
p
) and so this value can be recycled. This is not usually faster than using
quadratic reciprocity for large
p
, but it is relevant for applications such as Lemma
21.4.9
.
A related topic is, given a prime
p
and an integer
d>
0, to find integer solutions (
x,y
),
if they exist, to the equation
x
2
dy
2
p
.The
Cornacchia algorithm
achieves this.
The algorithm is given in Section 2.3.4 of Crandall and Pomerance [
150
], and a proof
of correctness is given in Section 4 of Schoof [
477
] or Morain and Nicolas [
393
]. In
brief, the algorithm computes
p/
2
<x
0
<p
such that
x
0
≡−
+
=
d
(mod
p
), then runs the
Euclid
ean algorith
m on 2
p
and
x
0
stopping at the first remainder
r<
√
p
, then computes
s
(
p
(
r,s
). The complexity is dom-
inated by computing the square root modulo
p
, and so is an expected
O
(log(
p
)
2
M
(log(
p
)))
bit operations. A closely related algorithm finds solutions to
x
2
=
−
r
2
)
/d
if this is an integer. The output is (
x,y
)
=
dy
2
+
=
4
p
.
2.10 Polynomial arithmetic
Let
R
be a commutative ring. A polynomial in
R
[
x
]ofdegree
d
is represented
6
as a (
d
+
1)-
tuple over
R
. A polynomial of degree
d
over
bits
for its representation. An algorithm on polynomials will be polynomial-time if the number
of bit operations is bounded above by a polynomial in
d
log(
q
).
Arithmetic on polynomials is analogous to integer arithmetic (indeed, it is simpler as
there are no carries to deal with). We refer to Chapter 2 of [
220
], Chapter 18 of [
497
],
Section 4.6 of [
308
] or Section 9.6 of [
150
] for details.
F
q
therefore requires (
d
+
1)
log
2
(
q
)
∈
Lemma 2.10.1
Let R be a commutative ring and F
1
(
x
)
,F
2
(
x
)
R
[
x
]
.
1. One can compute F
1
(
x
)
)
additions in R.
2. One can compute F
1
(
x
)
F
2
(
x
)
in O
(deg(
F
1
)deg(
F
2
))
additions and multiplications
in R.
3. If R is a field then one can compute the quotient and remainder of division of F
1
(
x
)
by
F
2
(
x
)
inO
(deg(
F
2
)(deg(
F
1
)
+
F
2
(
x
)
in O
(max
{
deg(
F
1
)
,
deg(
F
2
)
}
−
deg(
F
2
)
+
1))
operations (i.e., additions, multiplications
and inversions) in R.
4. If R is a field then one can compute F
(
x
)
=
gcd(
F
1
(
x
)
,F
2
(
x
))
and polynomi-
als s
(
x
)
,t
(
x
)
t
(
x
)
F
2
(
x
)
, using the extended
Euclidean algorithm in O
(deg(
F
1
)deg(
F
2
))
operations in R.
∈
R
[
x
]
such that F
(
x
)
=
s
(
x
)
F
1
(
x
)
+
6
We restrict attention in this and the following section to univariate polynomials. There are alternative representations for sparse
and/or multivariate polynomials, but we do not consider this issue further.
