Cryptography Reference
In-Depth Information
while (GTZ_L (v3_l))
{
div_l (d_l, v3_l, q_l, t3_l);
mul_l (v1_l, q_l, q_l);
sign_t1 = ssub (tmpu_l, *sign_u, q_l, sign_v1, t1_l);
cpy_l (tmpu_l, v1_l);
*sign_u = sign_v1;
cpy_l (d_l, v3_l);
cpy_l (v1_l, t1_l);
sign_v1 = sign_t1;
cpy_l (v3_l, t3_l);
}
Step 3: Calculation of
v
and the end of the procedure.
mult (a_l, tmpu_l, tmp_l);
*sign_v = ssub (d_l, 1, tmp_l, *sign_u, tmp_l);
div_l (tmp_l, b_l, tmpv_l, tmp_l);
cpy_l (u_l, tmpu_l);
cpy_l (v_l, tmpv_l);
return;
}
Since dealing with negative numbers within the FLINT/C package requires
additional cost, we arrive at the observation that for calculating the inverse of a
residue class
a ∈
Z
n
only the one factor
u
of the representation
1=
u · a
+
v · n
of the greatest common divisor is necessary. A positive representative for
u
can
always be found, and we can thereby spare ourselves the need to deal with
negative numbers. The following algorithm is a variant of the previous one that
makes use of this observation and eliminates entirely the calculation of
v
.
Extended Euclidean algorithm for calculating
gcd(
a, n
)
and the multiplicative
inverse of
a
mod
n
,
0
≤
a
,
0
<n
1.
Set
u
←
1
,
g
←
a
,
v
1
←
0
,and
v
3
←
n
.
2.
Calculate
q
,
t
3
with
g
=
q · v
3
+
t
3
and
t
3
<v
3
by division with remainder
and set
t
1
← u − q · v
1
mod
n
,
u ← v
1
,
g ← v
3
,
v
1
← t
1
,
v
3
← t
3
.
3.
If
v
3
=0
, output
g
as
gcd(
a, n
)
and
u
as the inverse of
a
mod
n
and
terminate the algorithm; otherwise, return to step 2.
v
1
mod
n
ensures that
t
1
,
v
1
,and
u
do not
become negative. At the end we have
u ∈{
1
,...,n−
1
}
The modular step
t
1
←
u
−
q
·
. The coding of the
algorithm leads us to the following function.
