Cryptography Reference
In-Depth Information
define the
amplitude
amp(
x
)
=
gcd(
P,x
−
R
) so that, if the
p
i
are coprime and
S
is the set
=
i
∈
S
p
i
. Write
F
(
x
)
of indices 1
≤
i
≤
n
such that
x
≡
r
i
(mod
p
i
), amp(
x
)
=
x
−
R
.
The problem is precisely to find an integer
x
such that
|
x
|
<X
and
F
(
x
)
≡
0(mod
M
)for
some large integer
M
P
. This is the problem solved by Coppersmith's algorithm in the
variant of Exercise
19.4.5
. Note that
p
1
≤
|
p
n
and so
n
log(
p
1
)
P
≤
≤
log(
P
)
≤
n
log(
p
n
).
Theorem 19.4.14
Let X,e,p
1
,...,p
n
,r
1
,...,r
n
be an instance of the Chinese remainder
with errors problem, where p
1
<p
2
<
···
<p
n
. Let P
=
p
1
···
p
n
. There is an algorithm
to compute all x
∈ Z
such that
|
x
|
<Xand x
≡
r
i
(mod
p
i
)
for all but e values
1
≤
i
≤
n
as long as
log(
p
1
)
log(
X
)
/
log(
P
)
.
The algorithm is polynomial-time in the input size.
n
log(
p
n
)
e
≤
n
−
Proof
Boneh [
70
] gives a direct proof, but we follow Section 4.7 of May [
371
] and derive
the result using Exercise
19.4.5
.
Let 0
≤
x<X
be an integer with
M
=
amp(
x
) being divisible by at least
n
−
e
of the
values
p
i
.Wehave
n
log(
p
1
)
≤
log(
P
)
≤
n
log(
p
n
) and (
n
−
e
)log(
p
1
)
≤
M
≤
n
log(
p
n
).
P
β
. Then Coppersmith's algorithm finds
x
if
X<P
β
2
in polynomial-time in
n
and log(
p
n
) (note that Exercise
19.4.5
states the result for
X<P
β
2
Write
M
=
−
, but we can remove
the
using the same ideas as Remark
19.1
.13
). Hence, it
is sufficient to give a bound on
e
so that log(
X
)
/
log(
P
)
<β
2
(i.e.,
β>
√
log(
X
)
/
log(
P
)). Now,
β
=
log(
M
)
/
log(
P
)
≥
(
n
−
e
)log(
p
1
)
/
(
n
log(
p
n
)). Hence, it is sufficient that
n
log(
X
)
/
log(
P
)
,
e
)
log(
p
1
)
(
n
−
log(
p
n
)
≥
which is equivalent to the equation in the theorem.
Exercise 19.4.15
Suppose
p
1
,
...,p
n
are the
first
n
primes. Show that the above algo-
rithm works when
e
−
√
n
log(
X
)log(
n
). Hence, verify that Boneh's algorithm is
polynomial-time in situations where the naive algorithm of Exercise
19.4.13
would be
superpolynomial-time.
≈
n
Bleichenbacher and Nguyen [
65
] discuss a variant of the Chinese remaindering with
errors problem (namely, solving
x
r
i
(mod
p
i
) for small
x
, where each
r
i
lies in a set
of
m
possible values) and a related problem in polynomial interpolation. Section 5 of [
65
]
gives some algorithms for this “noisy CRT” problem.
≡
Smooth integers in short intervals
The above methods can be used to find smooth integers in intervals. Let
I
=
[
U,V
]
={
x
∈
Z
:
U
≤
x
≤
V
}
and suppose we want to find a
B
-smooth integer
x
∈
I
if one exists (i.e.,
all primes dividing
x
are at most
B
). We assume that
V<
2
U
.
Exercise 19.4.16
Show that if
V
≥
2
U
then one can compute a power of 2 in [
U,V
].
