Cryptography Reference
In-Depth Information
Exercise 6.26
Modify the procedure
sieve
in order to make it compilable from
Maple by the external C compiler and also modify
QS
to include as an option the
use of the compiled version of the sieve.
Exercise 6.27
Modify
FindRelations
and
QS
so that the latter admits an op-
tional parameter where the value of the threshold used in
FindRelations
(therein
set to 14) can be modified (and perhaps set as proportional to the logarithm of
B
)
and use it to find the optimum threshold for integers of different sizes.
The basic QS algorithm admits many modifications that, without changing its
asymptotic running time, have a big impact in practice and permit the factorization
of numbers of more than 130 decimal digits. We will not go into the details of these
improvements as this would lead us too far into technical aspects of the algorithm
but we will give a brief summary of the more important ones.
6.4.9 Some Improvements on the Basic QS
Next we give a brief description of some modifications of the basic QS algorithm
that are relevant in practice.
6.4.9.1 Large Prime Variations
The idea of the large-prime variation is to increase, in an indirect way, the smoothness
bound
B
without increasing the size of the factor base, allowing the algorithm to
obtain more relations with little additional work. The method works by saving the
relations that have at most one prime factor larger than
B
(for example, in the interval
(
B
2
) with the idea of combining them to obtain more
B
-smooth numbers. These
relations are called
partial relations
or, simply,
partials
, in contrast to the ordinary
relations which are called
fulls
. The partials are stored and sorted in order of their large
primes. If one large prime factor appears only once in this list, then the corresponding
partial is discarded as it cannot be used to make a square. But as soon as the large
prime appears in two partials, these relations can be multiplied and the large prime
removed to form a full relation. Observe that it takes no extra effort to find partials
when the large prime is
B
,
]
B
2
because if all the prime factors
B
have been removed
from the prime factorization of a number and the remaining factor is larger than 1
but smaller than
B
2
, then it must necessarily be a prime. In addition, the birthday
paradox suggests that duplicate large primes will not be uncommon in the partials
and this is confirmed by practice.
The idea of considering primes larger than
B
when building the relations can be
pushed further and it has been found that better performance is obtained in very large
factorizations by considering two large primes instead of one; for example the factor-
ization of RSA129, a 129-digit number factored in 1994, was accomplished with this
≤
≤
