Cryptography Reference
In-Depth Information
'
z
-values' of the form
x
2
−
n
. Each column of the matrix corresponds, in order, to a
member of the factor base, and the rows are the exponent vectors of the relations.
For example, the numbers in the first row mean that if
x
=
22721368, then
z
=
x
2
−
n
=−
117513808903
=
(
−
1
)
·
29
·
181
·
239
·
283
·
331 and, similarly, the numbers
in the ninth rowmean that 22838412
2
199
2
.
As already mentioned, a high number of trials was expected in this case to obtain
the required number of 38
B
-smooth integers. Now we see that the number of trials
was 2451834 which is indeed high taking into account the size of
n
. Later we will
see how to deal with this difficulty but now we continue the process of factoring
n
.
37
2
−
n
=
5214985081417
=
29
·
31
·
·
107
·
> d := Dependencies(r[3]): d;
[[01011001000010110110000000111011000000],
[10100110100101110001011111100110100000],
[00111111100010001000110010000110010000],
[10101100000000010111011111110110001000],
[01000000000000000000100000000000000100],
[01110111000100001000100000110010000010],
[01011000110101001001101000001010000001]]
We have obtained 7 linear dependencies which form a basis of the null space of the
relations matrix. The entries with value 1 in each of these dependencies correspond
to the rows (i.e., the relations) used to obtain a congruence between squares modulo
n
. For example, the first of these relations has value 1 entries corresponding to the
following rows: 2, 4, 5, 8, 13, 15, 16, 18, 19, 27, 28, 29, 31, 32. The
x
-values and the
z
-
values corresponding to these rows give a congruence of the form
x
2
y
2
.
Now we can search for nontrivial factors of
n
with the function
FindFactors
using these dependencies and the relations previously produced.
≡
(
mod
n
)
> FindFactors(n, r, d);
(30778453) (16777259)
We have used the list of all the dependencies to factor the number but, as we
have noticed before, it is possible that some of these dependencies give a congruence
x
2
y
2
that does not produce a nontrivial factor. In
order to appreciate what happens in more detail we may also check the dependencies
one by one. For example, if we try with the third dependency we have:
≡
(
mod
n
)
with
x
≡±
y
(
mod
n
)
> FindFactors(n, r, [d[3]]);
No nontrivial factors found
This dependency produced no factors but if we use the first one instead we obtain
the factorization of
n
:
> FindFactors(n, r, [d[1]]);
(30778453) (16777259)
When the factor base has, as happens in this case, few small primes, there is a
trick that serves to speed up the process considerably. The idea is to use a
multiplier
,
i.e., to multiply the integer being factored by a small square-free integer
m
, so that
we will factor
mn
instead of
n
. This seems a rather peculiar way to proceed and, as
