Cryptography Reference
In-Depth Information
b:=1;
A := table();
for i from 0 to t-1 do
A[b] := i;
b := b*g mod m
end do;
l := sort(ListTools:-Flatten([indices(A)]));
h := gˆ(-t) mod m;
b := a mod m;
for j from 0 to t-1 do
s := ListTools:-BinarySearch(l, b);
if s <> 0 then
return A[l[s]]+t*j
end if;
b := b*h mod m
end do;
printf("%d does not belong to the cyclic subgroup generated by %d", a, g)
end proc:
Example 6.22
Consider the following values of
p
,
g
and
a
:
> p := 439809843839:
g := 139046225820:
a := 310669347635:
Z
p
:
Then
p
is prime and
g
is a primitive root modulo
p
. Let us compute log
g
a
in
> x := BSGS(p, g, a);
x:= 54679028452
We can check that
x
is indeed the discrete logarithm of
a
to the base
g
:
> Power(g, x) mod p;
310669347635
Example 6.23
We now compute a discrete logarithm corresponding to a composite
modulus. Let
> m := 1007916624383:
10
10
1, we see that 10
10
∈ Z
m
. Now consider
m
is composite and, since gcd
(
,
m
)
=
∈ Z
m
and let us try to compute its discrete logarithm to the base
the element 111111
10
10
modulo
m
:
> BSGS(m, 10ˆ10, 111111);
111111 does not belong to the cyclic subgroup generated by 10000000000
Z
m
generated by
10
10
. But the function will compute discrete logarithms in the subgroup
We see that 111111 does not belong to the cyclic subgroup of
10
10
⊆Z
m
and, for example:
> Power(10ˆ10, 10ˆ8) mod m;
879981576058
> BSGS(m, 10ˆ10, %);
100000000
Exercise 6.31
Show that the function
BSGS
can be modified by separating the pre-
computation from the main function, allowing the computation of several discrete
logarithms in the same group without recomputing the table
A
.
