Cryptography Reference
In-Depth Information
This relation, in turn, gives the following equation that the discrete logarithms of
the involved primes must satisfy:
3log
g
2
+
12 log
g
3
+
log
g
5
+
4log
g
7
+
log
g
113
≡
2074798658290
(
mod
p
−
1
),
and each row of the matrix defines one such equation, where the first 30 columns
of the matrix correspond to the discrete logarithms of the primes in the factor base
(in their natural order) and the last column gives the 'independent terms'. Thus
this matrix defines a linear system of 40 equations in 30 unknowns over
Z
p
−
1
30
p
−
whose solution is the vector of
1
whose components are the discrete loga-
rithms of the primes in the factor base. The system is solved by Maple's function
LinearAlgebra:-Modular:-LinearSolve
and the result obtained in this
case is the vector printed above, just after the matrix (the solution of the system is
given by Maple in the form of a column vector but we display it as a row vector for
convenience). For example, since the last component of the vector is 1891579519393
and the last prime in the factor base is 113, we know that log
g
113
Z
=
1891579519393
and we may use Maple to check that this is indeed the case:
> Power(g, 1891579519393) mod p;
113
We are now ready to compute log
g
9876543210, which was our original goal. The
output of the function
IndexCalculusPrecomp
was stored in a global variable
called
pr
and we feed it to
IndexCalculus
through the keyword parameter
pre
.
The result is the following:
> IndexCalculus(p, g, 9876543210, verbose = true, pre = pr);
(1850226918918ˆ10951180283336)*9876543210 mod 17279730901583 has exponent vector
over the factor base:
[4,1,1,1,1,0,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0]
The discrete logarithm is:
11628971657383
The special relation that produced the discrete logarithm is displayed in the first
two printed lines after the command. These lines inform us that
g
10951180283336
2
4
·
=
·
·
·
·
·
·
·
·
·
9876543210 mod
p
3
5
7
11
29
37
43
61
79
and, although not necessary, we can again check that this is indeed the case:
> ifactor(modp(9876543210*Power(g, 10951180283336), p));
(2)ˆ4 (3) (5) (7) (11) (29) (37) (43) (61) (79)
Once this final relation is obtained, the discrete logarithm 11628971657383 fol-
lows easily and it was given as the output of the
IndexCalculus
function. The
result can also be obtained from this relation by direct manipulation and we explic-
itly show how it is obtained. Taking logarithms, the final relation translates into the
following equation in
Z
p
−
1
:
