Cryptography Reference
In-Depth Information
Z
2017
Thus we know that 5 is a generator of
and hence we can compute the
..
discrete logarithm of any integer in the range 1
2016 to the base 5. Let us compute
the discrete logarithm of 74:
> RhoDiscreteLog(2017, 5, 74);
"Computation proceeds with new initial values..."
1631
The function does not find the logarithm in the first attempt but if we answer 'y'
the computation proceeds and the logarithm 1631 is found (it could take more than
one restart).
Example 6.25
The following values were used in Example 6.22 with the BSGS
method. We appreciate that this implementation of the rho method does it faster:
> p := 439809843839:
g := 139046225820:
a := 310669347635:
RhoDiscreteLog(p, g, a);
54679028452
An interesting feature of the rho method is the very little storage it requires (there
are versions that, using some more storage, are more efficient at finding collisions).
This allows the previous function to tackle larger numbers than the function
BSGS
although the running time grows similarly. We next present an example that shows
that a discrete logarithm corresponding to a 17-digit modulus is easily doable with
RhoDiscreteLog
:
Example 6.26
Let us consider the modulus
m
12345678910111223 which, as
can easily be checked, is prime. Also, 5 is a primitive root modulo
m
because:
=
> m = 12345678910111223:
numtheory:-primroot(m);
5
Z
m
(this
may take a long time depending on the computer used but we will see in Example
6.28 a much faster method to compute it):
Then we can use
RhoDiscreteLog
to compute log
5
9876543210 in
> RhoDiscreteLog(m, 5, 9876543210);
1001490480543171
Exercise 6.34
Modify the function
RhoDiscreteLog
so that it works with dif-
ferent functions which partition the group into three subsets. In order to do that,
add a new input parameter that takes as value the partition function which can be
previously defined. Check it with the partition functions
x
→
1
+
(
x
+
1
)
mod 3
and
x
→
1
+
(
x
+
2
)
mod 3.