Cryptography Reference
In-Depth Information
p
a
p
≡
3(mod4)
−
1
p
≡
1(mod4),
p
≡
2(mod3)
3
√
−
p
≡
1(mod4),
p
≡
1(mod8)
1
+
√
−
1)
/
√
2
≡
≡
p
1(mod8),
p
1(mod16)
(1
Remark 2.4.8
The problem of computing quadratic non-residues has several algorith-
mic implications. One conjectures that the least quadratic non-residue modulo
p
is
O
(log(
p
) log(l
o
g(
p
))). Burgess proved that the least quadratic non-residue modulo
p
is
at most
p
1
/
(4
√
e
)
+
o
(1)
p
0
.
151633
+
o
(1)
, while Ankeny showed, assuming the extended Rie-
mann hypothesis, that it is
O
(log(
p
)
2
). We refer to Section 8.5 of Bach and Shallit [
21
]
for details and references. It follows that one can compute a quadratic non-residue in
O
(log(
p
)
4
) bit operations, assuming the extended Riemann hypothesis.
≈
∈ N
Exercise 2.4.9
Give a Las Vegas algorithm to test whether
a
is a square by computing
(
p
) for some random small primes
p
. What is the complexity of this algorithm?
Exercise 2.4.10
Let
p
be prime. In Section
2.8
we give algorithms to compute modular
exponentiation quickly. Compare the cost of computing (
p
) using quadratic reciprocity
versus using Euler's criterion.
Remark 2.4.11
An interesting computational problem (considered, for example, by
Damgard [
152
]) is: given a prime
p
, an integer
k
and the sequence (
p
)
,
(
a
+
p
)
,...,
(
a
+
k
−
p
)
to output (
a
+
p
). A potentially harder problem is to determine
a
given the sequence of values.
It is known that if
k
is a little larger than log
2
(
p
) then
a
is usually uniquely determined
modulo
p
and so both problems make sense. No efficient algorithms are known to solve
either of these problems. One can also consider the natural analogue for Jacobi symbols.
We refer to [
152
] for further details. This is also discussed as Conjecture 2.1 of Boneh and
Lipton [
78
].
Finally, we remark that one can compute the Legendre or Jacobi symbol of
n
-bit integers
in
O
(
M
(
n
) log(
n
)) operations using an analogue of fast algorithms for computing gcds. We
refer to Exercise 5.52 (also see pages 343-344) of Bach and Shallit [
21
] or Brent and
Zimmermann [
96
] for the details.
2.5 Modular arithmetic
In cryptography, modular arithmetic (i.e., arithmetic modulo
n
∈ N
) is a fundamental
building block. We represent elements of
Z
/n
Z
as integers from the set
{
0
,
1
,...,n
−
1
}
.
We first summarise the complexity of standard “school” methods for modular arithmetic.
