Cryptography Reference
In-Depth Information
> iquo(p2, numtheory:-order(g2, p2));
2
Z
p
2
. Since it is a subgroup of
the group of quadratic residues and has the same order, the two groups are the same
and the order is
and this means that the subgroup
g
2
has index 2 in
(
p
2
−
1
)/
2, a 160-bit number. Let us now pick an element of
g
2
,
i.e., a quadratic residue, and find its discrete logarithm to the base
g
2. Let
> a2 := 141592653589793238462643383279502884197169399375:
(incidentally, the digits of
a
2 are just the first 48 digits of
after the decimal point,
as in the example of [39]). We can check that
a
2 is a quadratic residue modulo
p
2
and hence it belongs to
π
g
2
and its discrete logarithm to the base
g
2 is defined:
> numtheory:-legendre(a2, p2);
1
So, let us use
PohligHellman
(with the rho method) to compute log
g
2
a
2:
> PohligHellman(p2, g2, a2);
277491729918135060759724184851982006579871508881
The result is quickly found and another possibility is to use the combination
PohligHellman/BSGS
:
> PohligHellman(p2, g2, a2, method = BSGS);
277491729918135060759724184851982006579871508881
In this case BSGS is slower than rho but it is a matter of seconds anyway. We
check that the result is correct:
> evalb(Power(g2, 277491729918135060759724184851982006579871508881) mod p2 = a2);
true
6.5.5 The Index Calculus Method for Discrete Logarithms
The generic algorithms for the DL problem discussed so far work in any finite
cyclic group whose elements can be represented in such a way that we have efficient
algorithms to perform the group multiplication. As we have seen, the number of steps
or group operations required by these algorithms is of the order of the square root
of the group order, and hence they run in exponential time. However, we have also
seen an example of a class of groups for which there is an efficient specific method
to compute discrete logarithms, namely, the (additive) groups
Z
n
, for which there is
2
an algorithm with running time
O
. The specific feature that underlies this
algorithm is that these groups have an additional multiplicative structurewhichmakes
them (commutative) rings. This suggests the possibility that additional features of the
group might also be exploited in other cases, such as the groups
(
len
(
n
)
)
Z
p
with
p
prime or,
more generally, the multiplicative groups of nonzero elements of finite fields. In the
case of
Z
p
, its operation is closely related to themultiplication of
and hence the idea
arose of using smooth numbers and factor bases in a similar way to the subexponential
Z
