Cryptography Reference
In-Depth Information
≥
is
1000, prompts the user asking whether the computation should be continued
with new seeds (when
b
[
]≡
[
]
(
)
<
1000, all the possible values
are searched until the discrete logarithm is found). If the answer is positive then it
chooses new values for
b
and
c
and restarts the computation. Observe that if
a
does
not belong to the cyclic subgroup of
3
c
3
mod
n
and
n
Z
m
generated by
g
, the algorithm will also
ask the user whether to continue the computation, so one should make sure that this
situation does not happen. The output of the function is log
g
a
.
> RhoDiscreteLog := proc(m::posint, g::posint, a::posint, n:=numtheory:-order(g,m))
local f, b, c, found, sols, i, finished, ans, u;
if igcd(m, g) <> 1 then
error "%1 is not a unit modulo %2", g, m
end if;
if igcd(m, a) <> 1 then
error "%1 is not a unit modulo %2", a, m
end if;
f := proc(x, r, s)
if x < m/3 then
g*x mod m, r+1 mod n, s
elif x < 2*m/3 then
xˆ2 mod m, 2*r mod n, 2*s mod n
else
a*x mod m, r, s+1 mod n
end if;
end proc;
b:=1,0,0;
c:=1,0,0;
finished := false;
while not finished do
found := false;
while not found do
b := f(b);
c := f(f(c));
found := evalb(b[1] = c[1])
end do;
if b[3] <> c[3] or n < 1000 then
sols := Roots((b[3]-c[3])*x-c[2]+b[2]) mod n;
sols := [seq(sols[i][1], i=1..nops(sols))];
for i in sols do
if a = Power(g, i) mod m then
return i
end if;
end do
end if;
ans := readstat("Not found, continue?, y/n");
if ans = y then
print("Computation proceeds with new initial values...");
randomize();
u := RandomTools:-Generate(integer(range = 1 .. n-1));
b := Power(g, u) mod m, u, 0;
c:=b
else
finished := true;
print("Computation interrupted")
end if;
end do;
end proc:
Example 6.24
Let us consider the modulus
m
=
2017, which is prime, and compute
a primitive root modulo
m
:
> numtheory:-primroot(2017);
5
