Cryptography Reference
In-Depth Information
return Vector[row](e)
elif t < z then
return Vector[row]([e, (x-t) mod (p-1)])
else
return Vector[row]([e, x])
end if;
end if;
end do;
end do;
end proc:
The next function,
IndexCalculusPrecomp
, embodies the precomputation
stage of the index calculus algorithm, which depends only on
p
and
g
and not on
the element whose logarithm is being computed. The smoothness bound and the
factor base are obtained first and then the ordinary relations are computed by gen-
erating pseudo-random integers
x
and calling
ICTrialDivision
to try to factor
g
x
mod
p
for each of these
x
. This way, the matrix
M
whose solution gives the
logarithms of the factor base is also computed. Then the linear system defined by
this matrix is solved by calling
LinearAlgebra:-Modular:-LinearSolve
,
which works also for composite moduli such as
p
1. The output is a list whose first
term is the factor base and whose second term is the vector of the discrete logarithms
of the factor base primes.
The required inputs are the prime
p
and the primitive root
g
. Moreover, there
are two optional keyword parameters. One of them,
verbose
, tells the func-
tion whether or not to print additional information on screen and has
false
as default. The other,
addrels
, specifies how many relations are to be com-
puted, their number being equal to the size
k
of the factor base plus the value
of
addrels
. The default value for this parameter is 10, as it seems that
k
−
10
ordinary relations are enough in most cases. If the relations found are not suffi-
cient to determine the discrete logarithms of the factor base primes as their only
solution, then either Maple's function
LinearSolve
will return an error or an
error message will be printed by the main function below indicating that the num-
ber of relations is insufficient (and hence that a higher value should be passed to
addrels
).
This function can either be called from the
IndexCalculus
function below or
it can be used in an autonomous way. The latter has the advantage that it separates the
precomputation from the final stage of the algorithm and hence allows the compu-
tation of several discrete logarithms in the same group without having to recompute
the factor base primes.
+
> IndexCalculusPrecomp := proc(p::posint, g::posint, {verbose:=false, addrels:=10})
local B, k, fb, i, rels, x, s, M, fblogs;
if 'not'(isprime(p)) then
error "%1 is not prime", p
elif numtheory:-order(g, p) <> p-1 then
error "%1 is not a primitive root modulo %2", g, p
end if;
RandomTools:-MersenneTwister:-SetState();
B := ceil(evalf(sqrt(exp(sqrt(ln(p)*ln(ln(p)))))/sqrt(2)));
k := numtheory:-pi(B);
fb := [seq(ithprime(i), i=1..k)];
rels := [];
