Cryptography Reference
In-Depth Information
of the algorithm. In a way similar to the case of QS, it can be shown that an optimal
choice for
B
(
i
n case the Elliptic Curv
e Method is u
sed to obtain the relations) is
B
√
2
, w
h
ere
L
(
√
(
1
/
=
L
(
p
)
(
p
)
=
exp
ln
p
)(
ln ln
p
))
, leading to a subexponential
√
2
+
o
(
1
)
.
complexity
L
(
p
)
6.5.6 The Index Calculus Method in Maple
We next give an implementation of the basic index calculus algorithm. For the factor-
ization of the residues we will use trial division and so we will adapt the previously
defined function
FBTrialDivision
—which was used for the Factor Base and
QS factorization methods—for this purpose. The function
ICTrialDivision
below has four required input parameters which are used, in order, to specify a prime
modulus
p
, a primitive root
g
, an integer in the range 1
2 (which will be pseudo-
randomly chosen by themain
IndexCalculus
function below) and the factor base
fb
. There are two optional parameters, the first of which is
special
, which tells
the function whether an ordinary relation or a special one (i.e., the final relation
involving the element whose discrete logarithm is being computed) is sought. The
default value for this parameter is
false
(it will be set to
true
only when looking
for the special relation at the end). The second optional parameter
a
will take the
value 1 in the 'nonspecial' case and the integer whose discrete logarithm we are
searching for in the 'special' case. The default value is 1. Note that this function is
intended to be called from the other functions in this implementation and not directly
by the user.
The output is a relation in the appropriate format: the exponent vector correspond-
ing to the factor base in the 'special' case, the exponent vector plus the exponent of
g
in the 'nonspecial' case, with a modification of this exponent in order to exploit
the known logarithm of
..
p
−
1 to speed up the process by replacing the integer to be
factored, in case it is greater than
−
(
p
−
1
)/
2, by its opposite in
Z
p
.
> ICTrialDivision := proc(p, g, x, fb, special:=false, a:=1)
local r, z, t, k, e, q, i;
r:=1;
z := modp(a*Power(g, x), p);
t := iquo(p-1, 2);
if not special and t < z then
q:=p-z
else
q:=z
end if;
k := nops(fb);
e := Vector[row](k, datatype = integer[1]);
for i to k while r <> 0 do
r := modp(q, fb[i]);
while r=0do
q := iquo(q, fb[i]);
e[i] := 1+e[i];
r := modp(q, fb[i]);
ifq=1then
if special then
