Cryptography Reference
In-Depth Information
Algorithm 6.5. Quadratic sieve.
Input
: An odd composite integer
n
which is not a perfect power.
Output
: Either a nontrivial factorization of
n
or a message informing that no nontrivial
factors were found.
Initialization
:
Select a multiplier
m
and for
B
1
/
2
=
c
·
L
(
mn
)
,where
c
is a small constant, compute
m
p
m
p
FB
}
(excluding perhaps some small primes) and, for each
p
∈
SP
compute the values
t
ip
∈ Z
p
,
i
:= {−
1
,
2
}∪{
p
|
p
odd prime,
p
≤
B
,
=−
1
}
.Let
SP
={
p
∈
FB
|
=
1
=
√
mn
2
=
1
,
2 such that
Q
(
t
ip
)
≡
0
(
mod
p
)
,where
Q
(
t
)
=
(
t
+
b
)
−
mn
, with
b
.
Initialize a one-dimensional
[−
M
,
M
]
array
SA
where
SA
[
t
]=
log
2
(
Q
(
t
))
.
Sieving
:
Sieve the array
SA
by subtracting
round
(
log
2
(
p
))
, for each
p
∈
SP
, from the values
SA
[
t
ip
+
sp
]
such that
s
is an integer and
t
ip
+
sp
∈[−
M
,
M
]
.
Collecting Relations
:
Find
K
+
hB
-smooth numbers, where
K
=|
FB
|
and
h
is a small integer, by trial dividing
the values
Q
(
t
)
by the primes in
FB
for those
t
∈[−
M
,
M
]
such that the value of
SA
[
t
]
falls
below a certain threshold
T
. This way values
t
j
∈[−
M
,
M
]
,
j
=
1
,...,
K
+
h
, are found
x
j
−
such that
Q
(
t
j
)
=
mn
(with
x
j
=
t
j
+
b
)is
B
-smooth and has an associated modulo 2
K
2
. The exponent vectors
e
1
,
e
2
,...,
e
K
+
h
are
=
(
e
j
1
,
e
j
2
,...
e
jK
)
∈ F
exponent vector
e
j
the rows of a
(
K
+
h
)
×
K
matrix over
F
2
called the relations matrix.
Linear Algebra
:
Compute the dependencies, i.e., a basis
{
d
1
,
d
2
,...,
d
j
}
of the null space of the transpose of
h
2
is one of these dependencies then
the sum modulo 2 of the rows of the relations matrix corresponding to the indices
j
such that
u
j
K
+
the relations matrix. If
d
=
(
u
1
,
u
2
,...,
u
K
+
h
)
∈ F
1 is equal to 0.
Factorization
:
Each of the dependencies obtained in the Linear Algebra step is used to get a congru-
ence between squares modulo
mn
.If
d
=
K
+
h
=
(
u
1
,
u
2
,...,
u
K
+
h
)
∈
F
is a dependency
2
with the
1-components in positions
j
1
,
j
2
,...,
j
q
, then compute
x
=
x
j
1
x
j
2
···
x
j
q
and
x
j
1
−
x
j
2
−
x
j
q
−
y
=
(
mn
)(
mn
)
···
(
mn
)
(
y
may also be computed from the prime
factorizations of the
x
j
i
−
mn
, given by the corresponding relations) and obtain a factor of
n
by computing
g
.If
g
is a nontrivial factor then return
g
else try with another
relation. If none of the relations produces a nontrivial factor print an informative message.
=
gcd
(
x
−
y
,
n
)
6.4.8 The Basic QS Algorithm in Maple
We are now ready to implement in Maple the basic QS algorithm described above.
We will take advantage of the previous implementation of the factor base method,
some of whose functions will be used without modification. When selecting the
value of parameters like the smoothness constant
B
we will follow the guidelines
explained in the discussion of the complexity of the algorithm. In particular,
B
will
be of the form
c
1
/
2
but we point out that often somewhat lower values are
·
L
(
n
)
