Cryptography Reference
In-Depth Information
Z
these elements are not directly related to the operations in
, so that it is not possible
Z
p
. However,
Z
to use a factor base consisting of primes in
as we did in the case of
F
p
n
is constructed from the polynomial ring
Z
p
[
, as it is again a quotient
ring modulo an irreducible element. On the other hand, we also remarked that the
ring
x
]
in much the same way as
Z
p
is constructed from
Z
and, for example, both are 'unique
factorization domains' in the sense that any nonzero non-unit of the ring factors, in
an essentially unique way, as a product of irreducible elements (the prime numbers in
the case of
Z
p
[
x
]
shares many properties with the ring
Z
).
11
Moreover, the
Z
and the irreducible polynomials in the case of
Z
p
[
x
]
elements of
F
p
n
can be represented by elements of
Z
p
[
x
]
, namely, by the polynomials
Z
p
generalize
of degree
<
n
. Thus the ideas behind the index calculus algorithm for
to this new setting just by looking at the elements of
F
p
n
as polynomials in
Z
p
[
x
]
and by trying to factor them as products of irreducible polynomials.
An important requirement for this idea to work is that there should be a suitable
concept of 'smoothness' also in this more general framework, and indeed there is.
Although the ring
is, there is a concept of 'size' given
by the degree of a polynomial and so we may say that a polynomial is
d
-smooth
when each of its irreducible factors has degree
Z
p
[
x
]
is not ordered like
Z
d
. This concept of smoothness is
not useful when
n
is small, for then the possible choices of
d
are severely restricted,
but it works well when
n
is large, in which case the same procedure as in the prime
case gives a subexponential index calculus algorithm also for
≤
1but
n
is small, the method can also be successfully implemented using another way of
representing the elements of
F
p
n
. When
n
>
F
p
n
based on the theory of algebraic number fields as
in the case of the NFS factorization algorithm (see [60, 6.4.2] for more details).
The basic index calculus method we have described and implemented is inspired
by the quadratic sieve factoring algorithm. But there are other variants of the index
calculus method that are inspired by the NFS factoring algorithm (and also called
NFS) and, as in the factorization case, aremore powerful than the integer-basedmeth-
ods. NFS for discrete logarithms can be used in any finite field and has a heuristic
subexponential running time similar to the NFS factoring algorithm. For an intro-
duction to these and other related methods (such as those based on function fields),
we refer to [106, Chap. 15].
The index calculus methods and, in particular, the NFS variant, are much faster
than the generic DL algorithms we have mentioned. In order to give an idea of how
far this algorithm has gone in practice, we shall briefly mention the current record
for a discrete logarithm in
Z
p
, which was established in 2007 using NFS [112]. In
this case,
p
is a 530-bit, 160-digit safe prime, in contrast with the already mentioned
record for the generic methods which was established in a group whose order is
a 112-bit prime. This clearly shows the power advantage of NFS over the generic
methods but then, of course, NFS was not applicable in the elliptic curve group where
the generic record was established
...
11
In fact, both rings share an even stronger property, namely both are 'Euclidean domains' since
they have a 'Euclidean function' which provides a division algorithm and a Euclidean algorithm.
