Cryptography Reference
In-Depth Information
if verbose then
printf("The discrete logarithm is:\n")
end if;
(m-r) mod (p-1)
end proc:
The functions
IndexCalculus
and
IndexCalculusPrecomp
require that
p
is a prime and
g
is a generator of
Z
p
, otherwise they will return an error. The
method can be adapted to work in cyclic subgroups of
Z
p
which are distinct from
Z
p
itself but this requires use of a factor base formed by elements of this cyclic
subgroup and the resulting algorithm is less efficient. There is a variant of the al-
gorithm in which, instead of computing first the discrete logarithms of the primes
and then log
g
a
, they are all computed at once by solving the linear system obtained
by collecting together the ordinary relations and the special relation. This variant
may allow log
g
a
to be found even if not all discrete logs of primes in the factor
base are found, since only those corresponding to primes in the final relation are
needed.
Example 6.30
We present a detailed example to show how
IndexCalculus
com-
putes a discrete logarithm. We define a prime
p
and a primitive root
g
:
> p := 17279730901583:
isprime(p);
ifactor(p-1);
g := numtheory:-primroot(1850226918917, p);
true
(2) (8639865450791)
1850226918918
Note that
p
is actually a safe prime, although this is not necessary for the method
to work. We can separately display the smoothness bound and the factor base for
p
:
> ceil(evalf(sqrt(exp(sqrt(ln(p)*ln(ln(p)))))/sqrt(2)));
[seq(ithprime(i), i=1..numtheory:-pi(%))];
117
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]
117, i.e., the first 30
primes. Suppose that we want to compute the discrete logarithm to the base
g
of
9876543210
We see that the factor base consists of the primes
≤
∈ Z
p
. We will separate the precomputation step from the computation
of this discrete logarithm, so we first compute:
> pr := IndexCalculusPrecomp(p, g, verbose = true):
Solving the linear system modulo 17279730901582 of augmented matrix:
