Cryptography Reference
In-Depth Information
mentioned in [115, pp. 399-400], it may even look downright stupid at first sight,
but notice what happens in our example if we multiply
n
by 2 and compute the factor
base corresponding to 2
n
:
> f2 := FactorBase(2*n);
f2 := Array(f2):
[-1, 2, 3, 5, 11, 13, 19, 31, 41, 43, 47, 53, 61, 67, 71, 73, 79, 83, 101, 109,
127, 137, 139, 149, 163, 173, 179, 193, 199, 211, 223, 239, 241, 251, 257, 269,
293, 311, 313, 347, 349, 367]
We see at a glance that the factor base looks much better now because it contains
many more small primes. We shall discuss how to choose the multiplier later but
now we shall factor
n
by factoring 2
n
instead, in order to appreciate the difference.
The relations obtained for 2
n
with the factor base
f2
are displayed in Table
6.2
.
Notice the dramatic decrease in the number of integers that we had to submit to
trial division: just 12826 against 2451834 without using the multiplier. The reason
is readily apparent if one inspects the first columns of the matrix and compares them
with those in the earlier relations matrix in which the multiplier was not used: now
the exponents of the first primes in the factor base are significantly larger making
their contribution to the factorization also larger, even taking into account the smaller
size of these primes. We may now use these relations to factor
n
as we did without
the multiplier.
Exercise 6.19
Use the relations matrix for 2
n
found in the previous example to
compute the linear dependencies and factor
n
.
Exercise 6.20
In his treatise on number theory published in 1926, M. Kraitchik used
the method sketched above (with a different way to obtain the relations) to factor the
number 193541963777. Use the previous Maple procedures to factor this number
without multiplier and also using the multiplier 2.
In the previous example we analyzed the factorization of an integer by means of
the factor base method and we saw the importance of using an appropriate multiplier
but we did not give any clues on how to choose this. We do it next.
6.4.6.1 The Multiplier
We want to select the multiplier
m
in such a way that
m
is square-free and the
contribution of the primes in the factor base to the factorization of the
z
-values is
maximized. In order to do that, we will first estimate the average number of times
that each prime in the factor base divides each of these
z
-values. Note that if we try to
factor
mn
instead of
n
, then we should add the prime divisors of
m
to the factor base
because a
z
-value of the form
x
2
mn
will be divisible by such a prime
p
whenever
x
is. This was already done in our previous code since when computing the factor
−
base we included not only the odd primes
p
such that
m
p
=
1 but also those that
satisfy
m
p
=
0, which are just the divisors of
m
because we are assuming that
n
