Cryptography Reference
In-Depth Information
and each relation, where the exponents
e
ij
are non-negative integers, has an associated
exponent vector:
e
(
z
t
)
=
(
e
t
1
,
e
t
2
,...,
e
tK
).
To find a set of values
z
t
whose product is a square, it is clear that we have to find
values such that the sum of the corresponding exponent vectors is even, because if
{
t
i
|
i
=
1
...
l
}
is a set of integers in the interval
[−
M
,
M
]
then:
l
K
p
i
=
1
e
t
i
j
j
z
t
i
=
,
i
=
1
j
=
1
(
i
=
1
z
t
i
)
=
i
=
1
(
and hence
e
. This was done by hand in our
examples but now it is easy to realize that finding a set of relations such that the sum
of their exponent vectors has all even components is the same as finding a set of
relations whose exponent vectors sum to the zero vector when regarded as vectors
modulo 2. Therefore, once we have generated a number of relations, we may consider
the associated vectors over the binary field
e
t
i
1
,
e
t
i
2
,...,
e
t
i
K
)
F
2
={
0
,
1
}
:
e
(
z
t
)
mod 2
=
(
e
t
1
mod 2
,
e
t
2
mod 2
,...,
e
tK
mod 2
),
and look for a subset of these vectors whose sum modulo 2 is the 0 vector. Thus we
are working in the
K
2
and we look for a way to write the 0 vector as a
nontrivial linear combination of these vectors (which is the same as a sum of a subset
of these vectors since the only nonzero coefficient in the field is 1). Such a linear com-
bination is called a
linear dependency
or, simply, a
dependency
and can be found by
using standard linear algebra algorithms such asGaussian elimination (althoughmore
efficient algorithms are known for the big sparse matrices that arise in the factoriza-
tion of large integers). Indeed, if we consider the
r
F
2
-vector space
F
F
2
whose rows
are the exponent vectors corresponding to
r
relations, then we want to find a linear
dependency between the rows of this matrix. These linear dependencies correspond
to the null space of the transpose
M
t
of this matrix, in the usual convention where
the null space of
M
t
consists of the column vectors
v
×
K
matrix
M
over
r
2
such that
M
t
0. We
will use Maple's command
MatBasis
from the
LinearAlgebra:-Modular
package to compute a basis of the null space of this matrix and each vector in this
basis will give a dependency and hence a congruence of the form
x
2
∈ F
·
v
=
y
2
.
There are, in general, many more dependencies in the null space of
M
t
—which can
be obtained as subset sums of the basis—but it can easily be shown that if one of
them gives a nontrivial factor of
n
then there is already a dependency in the basis that
also gives the nontrivial factor, so we will not need these additional dependencies.
We remark that the linear algebra approach also solves another of the problems
mentioned above because it provides an upper bound to the number of relations
needed to create a congruence between squares modulo
n
. Since the
r
rows of
M
live
in the
K
-dimensional vector space
≡
(
mod
n
)
K
F
2
, we know for sure that a linear dependency
