Cryptography Reference
In-Depth Information
need the constant
c
to be raised in order to collect enough relations. Of course, many
other changes can be made to the parameters such as
B
,
M
or to the threshold value
of 14 used inside the function
FindRelations
, allowing much more flexibility
than is permitted by simply changing the value of
c
in
QS
. Numbers of over 40
decimal digits can be factored with this function but we cannot go much further
above this size before hitting storage limitations, due to the size of the sieve array
which grows very fast and requires a lot of memory. One straightforward way to
mitigate this difficulty is to segment the sieve by dividing the sieved interval into
smaller subintervals and, as we will mention later, this automatically happens when
the basic algorithm is replaced by the “multiple polynomial” one. Segmenting the
sieve also has the added benefit that, after sieving each subinterval, it may be checked
whether the number of relations collected is already sufficient, in which case there
is no need to go further. In the current simple version, if the relations found are not
sufficient, one has to start again from the beginning.
Exercise 6.25
Modify the function
sieve
and the function
QS
so that the sieve is
segmented. After sieving each subinterval it should be searched for smooth values
and the corresponding relations collected. At this point it should be checked whether
the collected relations are sufficient and, if not, go on with the remaining subintervals
until enough relations have been found.
Example 6.21
Let us factor the 45-digit number:
> n45 := 538096101322932978757272139986951552262989443:
If we try to factor
n
45 using
QS
with default values, the function uses a factor
base of size 3716 but finds only 2929 relations, which are insufficient to generate
any dependencies and hence no nontrivial factors are found. However, if we raise the
value of
c
to 1
4, the result is the following (with a 64-bit version of Maple, using
almost 1 GB of memory; some versions of Maple may give here an '
object too
large
' error):
.
> QS(n45, c = 1.4);
Using multiplier:
5
Using smoothness bound:
86177
Size of factor base:
4242
Sieving interval of length:
384109867
Sieving done, searching for smooth values ...
Number of smooth values found:
4213
Solving a matrix of size:
4213, 4242
Number of linear dependencies found:
244
Factors:
(53296307643824213501501) (10096311078789820074943)
