Cryptography Reference
In-Depth Information
For some choice of
k
of the
g
-primes where 1
≤
i
1
<i
2
<
···
<i
k
≤
r
, let
a
=
g
i
1
g
i
2
···
g
i
k
.
Now, solve for
b
i
with
i
=1
,
2
,...,r
in
b
i
≡
n
(mod
g
i
)
.
Then use the Chinese remainder theorem A.12 on page 478, to solve the
system of congruences, for a specific choice of signs:
b
i
1
(mod
g
i
1
);
b
b
i
2
(mod
g
i
2
);
b
i
k
(mod
g
i
k
)
.
b
≡±
≡±
···
b
≡±
For this solution
b
, set
c
=(
b
2
n
)
/a
2
. Then we select
−
W
(
x
)=
a
2
x
2
+2
bx
+
c,
where the above generation guarantees that
a
,
b
,
c
satisfy
√
2
n/M, b
2
<a
2
/
2
.
(C.6)
(4) (
Test W
(
x
)
for divisibility by factor base elements
): If
q
i
W
(
j
) for
some
j
a
2
n
=
a
2
c,
≈
−
|
b
|
M,M
], called a
sieve number
, then
q
i
(
a
2
j
+
b
)
2
∈
[
−
−
n
,so
a
−
2
(
j
≡
±
t
q
i
−
b
) (mod
q
i
)
,
since gcd(
a,q
i
) = 1 from step (3). We compute
a
−
2
(mod
q
i
) for all such
q
i
via
a
−
2
g
−
2
i
1
g
−
2
g
−
2
i
k
(mod
q
i
)
.
Thus, for eGciency, with the calculation of
g
-primes by the methodology
in in step (3), we also compute and save, for
i
=1
,
2
,...,r
, all the numbers
g
−
2
i
≡
···
i
2
(mod
q
i
) for each
q
i
=
p
a
i
<B
where
p
i
∈
F
.
i
(5) (
Sieving
C.4
): Define a (2
M
+ 1)-tuple:
s
=(
s
(
−
M
)
,s
(
−
M
+1)
,...,s
(
j
)
,...,s
(
M
))
,
which we initialize by setting
s
(
j
) = 0 for all
j
∈
[
−
M,M
]. For each sieve
M,M
], i.e., those for which some prime power
q
i
=
p
a
i
i
number
j
∈
[
−
W
(
j
), reset
s
(
j
)=ln
p
i
+
s
(
j
)
.
(6) (
Selection of factor candidates
): Define the
report threshold
C.5
to be
RT
=ln
1
2
M
n/
2
.
C.4
In general with the MPQS, the amount of time spent on sieving takes more than 85% of
the total computing time.
C.5
The report threshold is the average of ln
|W
(
j
)
|
for
j ∈
[
−M,M
]. When
s
(
j
)
≥ RT
,
W
(
j
)
is a good candidate for factoring over the factor base.
Search WWH ::
Custom Search