Cryptography Reference
In-Depth Information
n
,n
). Then we construct a set of integers
i
for
x
∈
(
−
∈
S
so that
g
(
x
i
) factors
over the factor base and
y
2
(mod
n
)
.
b
i
≡
g
(
x
i
)
≡
x
i
∈
S
x
i
∈
S
For a single choice of
g
(
x
), there is an unreasonable amount of time required to
generate a suGciently large enough set
S
over which
g
(
x
) will factor. The reason
n
,n
) is also large since
g
(
x
)=
O
(
n
1
/
2+
)
is large as well, and so we will probably not be able to factor most of the
g
(
x
) over a small set of primes. The following version, taken from [170], solves
this problem by establishing an eGcient means of using several polynomials so
that the
x
values may be chosen from smaller intervals rather than one large
interval. This means that the average polynomial values are smaller than the
average of
g
and have a higher probability of factoring over small primes than
the
g
(
x
) values in the ordinary quadratic sieve. This then is a way of running
the ordinary quadratic sieve in parallel.
is that for large
n
, the interval (
−
C.6 Multipolynomial Quadratic Sieve (MPQS)
In this algorithm,
n
∈
N
is assumed to be a large composite number. The
goal is to split
n
.
(1)
(
Select
bo
unds
): Choose a large smoothness bound
B
and an
M
∈
N
with (
√
2
n/M
)
1
/
4
>B
.
(2)
(
Select a factor base
): Choose a set of
L
primes as a factor base
(see the discussion on page 534) that is fixed for the algorithm:
∈
N
p
i
:
p
i
is prime and
n
p
i
= 1 for
i
=1
,
2
,...,L
F
=
{
}
,
with
q
i
=
p
a
i
i
<B
,
where the symbol is the Legendre symbol. For
p
i
∈
F
compute solutions
t
q
i
to the congruences,
t
q
i
≡
n
(mod
q
i
)
,
for 0
<t
q
i
≤
q
i
/
2.
with 1
<k<r
.
C.3
Generate primes
g
1
,g
2
,...,g
r
, which are called
g
-primes
, satisfying:
(3) (
Create a quadratic polynomial
): Choose
r, k
∈
N
(
√
2
n/M
)
1
/
(2
k
)
,
(b) (
g
i
) = 1, and
(c) for each
i
=1
,
2
,...,r
, gcd(
g
i
,q
) = 1 for all
q
≈
(a)
g
i
∈
F
.
C.3
Wechooseasmallvaluesof
r
forpedagogicalpurposesbutinpractice,theMPQStypically
uses a value such as
r
= 30, for instance.
Search WWH ::
Custom Search