Cryptography Reference
In-Depth Information
Select from step (5) all those values
j
for which
s
(
j
)
RT
, test
W
(
j
),
and save
a,b,j
, (and thus tacitly
c
via the choice in step (3)) only if
W
(
j
)
factors over
≈
. If the number of
W
(
j
) selected is less than
L
+2, go to
step (3). Otherwise, go to step (7).
F
(7) (
Creation of exponent vector
): Since we have
L
+ 2 sieve values
j
,we
form
L
p
b
j
i
, and
b
j
i
≤
1)
b
j
0
W
(
j
)=(
−
a
i
, for
j
=1
,
2
,...,L
+2
i
=1
and associate with
W
(
j
) the exponent vector,
v
j
=(
b
j
0
,b
j
1
,...,b
j
L
) (mod 2)
,
so we have a binary
L
+ 1-tuple for each
j
=1
,
2
,...,L
+ 2. Since we have
L
+ 2 vectors with
L
+ 1 coordinates, then there is at least one subset,
C.6
,
S
⊆{
1
,
2
,...,L
+2
}
such that
v
j
≡
0 (mod 2)
,
j
∈
S
so
z
2
(mod
n
)
.
W
(
j
)
≡
j
∈
S
(8) (
Factor n
): Since (
a
2
x
+
b
)
2
a
2
W
(
x
) (mod
n
), then
≡
z
2
j
∈
S
X
2
(
a
2
j
+
b
)
2
a
2
Y
2
(mod
n
)
,
≡
≡
≡
j
∈
S
−
so if 1
<
gcd(
X
Y,n
)
<n
, then we have a nontrivial factor of
n
.
One big advantage of the MPQS over the ordinary quadratic sieve is that
one can generate many
a,b,c
values, and switch polynomials when the residues
grow too large. In step (3), we see that if we have a fixed
k
and set of
rg
-primes,
the number of polynomials that may be calculated is
2
k
−
1
r
k
=2
k
−
1
r
!
k
)!
k
!
.
(
r
−
Analysis
To see why the conditions in (C.6) hold, we present the following
verification. Since (a) holds, then
i
=1
(1
/k
)
√
2
n
M
2(1
/
2
k
)
=
√
2
n
M
=
√
2
n
M
,
k
a
2
≈
i
=1
C.6
We can use Gaussian elimination modulo 2 on the matrix whose columns are
v
j
to find a
set
S
. See Appendix A on page 494.
Search WWH ::
Custom Search