Cryptography Reference
In-Depth Information
The Algorithm
We make some initial simplifying assumptions the reasons for which the
reader may find in [50]. We assume that a smoothness bound
B
and the degree
d
of the polynomial
f
have been chosen from experimental data.
C.7
Now, we
n
1
/d
let
m
=
and write
n
in base
m
,
n
=
m
d
+
c
d
−
1
m
d
−
1
+
···
≤
≤
−
+
c
0
, with 0
c
j
m
1 for
j
=0
,
1
,...,d.
(C.10)
Now if we set
f
(
x
)=
x
d
+
c
d
−
1
x
d
−
1
+
···
+
c
0
∈
Z
[
x
]
,
then we have a monic polynomial with
f
(
m
)=
n
. However, we wanted
f
to
be irreducible. If it is not, then we have no need of the number field sieve,
since then
f
(
x
)=
g
(
x
)
h
(
x
) where
g
and
h
have unequal positive degrees, so
g
(
x
)
h
(
x
)=
f
(
m
)=
n
, and we have a nontrivial factor of
n
. Hence, we may
assume that
f
is irreducible (as are most monic polynomials over
Z
). Thus, we
have our polynomial
f
,
B
, and
d
values, and a number field
F
=
Q
(
α
) of degree
d
over
.
In the following, we have to extend our definition of
smooth
given on page
511. We call
a
+
bα
Q
∈
Z
[
α
]
B
-smooth
if
|
N
F
(
a
+
bα
)
|
is
B
-smooth where
N
F
is
the norm map from the field
F
to
Q
. Also, for a given prime
p
≤
B
, set
R
(
p
)=
{
r
∈
Z
:0
≤
r
≤
p
−
1 and
f
(
r
)
≡
0 (mod
p
)
}
.
Then whenever (
a,b
) are coprime,
p
N
F
(
a
bα
) if and only if
p
(
a
−
−
br
) for
some
r
∈
R
(
p
) with
p
b
. Then
r
is called the (unique)
signature
of
N
(
a
−
bα
)
modulo
p
.
Hence, for each coprime (
a,b
)-pair, there exist
|
R
(
p
)
|
= r primes
p
≤
B
dividing
N
(
a
−
bα
). We will let these be denoted by
p
1
,p
2
,...,p
r
. Then
if
a
−
bα
is
B
-smooth, we have
r
1)
a
(0)
p
a
(
p
i
)
, where
a
(0)
N
(
a
−
bα
)=(
−
∈{
0
,
1
}
.
i
=1
Based on this we can now define exponent vectors. Let
v
(
a
−
bα
)=(
a
(0)
,a
(
p
1
)
,a
(
p
2
)
,...,a
(
p
r
))
.
However, based on our goal set above, we want not only
a
−
bα
to be
B
-
smooth, but also
a
−
bm
to be
B
-smooth.
If the latter is the case, then let
q
r+1
,q
r+2
,...,q
s
be all the primes less than or equal to
B
dividing
a
−
bm
, and
write
s
q
b
(
q
i
)
i
1)
b
(0)
−
−
a
bm
=(
,
i
=r+1
C.7
Heuristiccomplexityargumentsdeterminethechoicestobeoptimalwhen
B
=
L
n
(1
/
3
,c
)
for
c
=(8
/
9)
1
/
3+
, and
d
= ((2
/c
)
1
/
2
[ln
n/
(lnln
n
)]
1
/
3
)=ln(
L
n
(1
/
3
,
(2
/c
)
1
/
2
)). These
choices ensure that
B
d
≈ n
2
/d
. Hence,
n>
2
d
2
, which is needed to ensure that
n
is monic in
(C.10), a straightforward exercise to verify.
Search WWH ::
Custom Search