Cryptography Reference
In-Depth Information
A serious problem is that only rather weak results have been proven about smooth integers
in short intervals (see Section 4 of Granville [
243
], Sections 6.2 and 7.2 of Naccache and
Shparlinski [
404
]orSection
15.3
). Hence, we cannot expect to be able to prove anything
rigorous in this section. On the other hand, it is natural to conjecture that, at least most
of the time, the probability that a randomly chosen integer in an short interval [
U,V
]is
B
-smooth is roughly equal to the probability that a randomly chosen integer of size
V
is
B
-smooth. Multiplying this probability by the length of the interval gives a rough guide to
whether it is reasonable to expect a solution (see Remark
15.3.5
). Hence, for the remainder
of this section, we assume that such an integer
x
exists. We now sketch how the previous
results might be used to find
x
.
Let
W
=
+
=
−
=
−
+
(
U
V
)
/
2 and
X
(
V
U
)
/
2 so that
I
[
W
X,W
X
]. We seek all
W
(mod
p
e
i
) for certain prime powers where
p
i
≤
x
∈ Z
such that
|
x
|≤
X
and
x
≡−
B
.
Then
W
+
x
is a potentially smooth integer in the desired interval (we know that
W
+
x
has
a large smooth factor, but this may not imply that all prime factors of
W
+
x
are small if
W
=
l
i
=
1
p
e
i
i
where
p
1
,...,p
l
are the primes up to
B
and the
e
i
are suitably chosen exponents (e.g.
e
i
=
is very large). One therefore chooses
P
). One then
applies Boneh's algorithm. The output is an integer with a large common divisor with
P
(indeed, this is a special case of the approximate GCD problem considered in Section
19.6
).
Note that this yields rather “dense” numbers, in the sense that they are divisible by most of
the first
l
primes.
log(
W
)
/
(log(
B
) log(
p
i
))
Example
19.4.17
Let
P
=
2
4
·
3
2
·
5
·
7
·
11
·
13
·
17
·
19
=
232792560.
Let
W
=
10
8
10
6
. We want to find an integer
x
between
100000007
=
+
7 and
X
=
1000000
=
W
−
X
and
W
+
X
such that
x
is divisible by most of the prime powers dividing
P
.
4 and
a
=
Taking
R
=−
W
,
a
=
3 in the notation of Theorem
19.4.14
gives the lattice
given by the basis matrix
P
4
0
0
0
0
0
0
RP
3
P
3
X
−
0
0
0
0
0
R
2
P
2
2
RP
2
X
2
X
2
−
0
0
0
0
R
3
P
3
R
2
PX
3
RPX
2
PX
3
−
−
0
0
0
.
R
4
4
R
3
X
6
R
2
X
2
4
RX
3
X
4
−
−
0
0
R
4
X
4
R
3
X
2
6
R
2
X
3
4
RX
4
X
5
0
−
−
0
R
4
X
2
−
4
R
3
X
3
6
R
2
X
4
−
4
RX
5
X
6
0
0
The polynomial corresponding to the first row of the LLL-reduced basis is
7
4
(
x
231767)
4
F
(
x
)
=−
+
giving the solution
x
=−
231767. Indeed
2
4
3
3
−
=
·
·
·
·
·
·
W
231767
5
11
13
17
19
.
Note that the algorithm does not output 10
8
2
8
5
8
=
·
since that number does not have a
very large gcd with
P
.
