Cryptography Reference
In-Depth Information
factors the ideal (
a
−
bθ
) by factoring its norm in
Z
), say
r
℘
e
i
.
(
a
−
bθ
)
=
i
=
1
Suppose also that
a
−
bm
is a smooth integer in
B
1
,say
s
p
f
j
.
a
−
bm
=
j
=
1
If these equations hold then we call (
a
bm
smooth and store
a,b
and the
sequences of
e
i
and
f
j
. We do not call this a “relation” as there is no direct relationship
between the prime ideals
℘
i
and the primes
p
j
. Indeed, the
℘
j
are typically non-principal
ideals and do not necessarily contain an element of small norm. Hence, the two products
are modelled as being “independent”.
It is important to estimate the probability that both the ideal (
a
−
bθ
) and
a
−
−
bθ
) and the integer
a
−
L
N
(1
/
3
,c
+
bm
are smooth. One shows that taking integers
|
a
|
,
|
b
|≤
o
(1)) for a suitable
constant
c
gives (
a
bm
of size
L
N
(2
/
3
,c
+
o
(1)) for certain constants
c
and
c
. To obtain a fast algorithm one uses sieving to determine
within a range of values for
a
and
b
the pairs (
a,b
) such that both
a
bθ
)ofnorm
L
N
(2
/
3
,c
+
−
o
(1)) and
a
−
−
bm
and (
a
−
bθ
)
factor over the appropriate factor base.
Performing linear algebra on both sides gives a set
S
of pairs (
a,b
) such that (ignoring
issues with units and non-principal ideals)
u
2
−
=
(
a
bm
)
(
a,b
)
∈
S
v
2
(
a
−
bθ
)
=
(
a,b
)
∈
S
for some
u
∈ Z
and
v
∈ Z
[
θ
]. Finally, we can “link” the two factor bases: applying the ring
φ
(
v
)
2
(mod
N
) and hence we have a chance to
split
N
. A non-trivial task is computing the actual numbers
u
and
φ
(
v
) modulo
N
so that
one can compute gcd(
u
gives
u
2
homomorphism
φ
:
Z
[
θ
]
→ Z
≡
φ
(
v
)
,N
).
Since one is only considering integers
a
−
bm
in a certain range (and ideals in a certain
range) for smoothness one relies on heuristic assumptions about the smoothness probability.
The conjectural complexity of the number field sieve is
O
(
L
N
(1
/
3
,c
−
+
o
(1))) bit operations
as
N
→∞
where
c
=
(64
/
9)
1
/
3
≈
1
.
923. Note, comparing with Exercise
15.2.12
, that if
N
≈
2
1024
then
L
N
(1
/
3
,
1
.
923)
≈
2
87
.
15.5 Index calculus in finite fields
We now explain how similar ideas to the above have been used to find subexponential
algorithms for the discrete logarithm problem in finite fields. The original idea is due
to Kraitchik [
319
]. While all subexponential algorithms for the DLP share certain basic
