Cryptography Reference
In-Depth Information
above constructive procedure into the Euclidean algorithm. For this we introduce
variables
u
and
v
, with the help of which the invariants
a
i
=
u
i
· a
+
v
i
· b
are maintained in the individual steps of the procedure presented on page 169, in
which we have
a
i
+1
=
a
i
−
1
mod
a
i
,
and these invariants provide us at the end of the algorithm the desired
representation of the greatest common divisor as a linear combination of
a
and
b
.
Such a procedure is called an
extended Euclidean algorithm
.
The following extension of the Euclidean algorithm is taken from [Cohe],
Section 1.3, Algorithm 1.3.6. The variable
v
in the above invariant condition is
employed only implicitly, and only at the end is it calculated as
v
:= (
d
−
u
·
a
)
/b
.
Extended Euclidean algorithm for calculating
gcd(
a, b
)
and factors
u
and
v
such that
gcd(
a, b
)=
u · a
+
v · b
,
0
≤ a, b
1.
Set
u ←
1
,
d ← a
.If
b
=0
, set
v ←
0
and terminate the algorithm;
otherwise, set
v
1
←
0
and
v
3
← b
.
2.
Calculate
q
and
t
3
with
d
=
q
v
3
+
t
3
and
t
3
<v
3
by a division with
remainder, and set
t
1
← u − q · v
1
,
u ← v
1
,
d ← v
3
,
v
1
← t
1
, and
v
3
← t
3
.
·
3.
If
v
3
=0
, set
v ←
(
d − u · a
)
/b
and terminate the algorithm; otherwise, go
to step 2.
The following function
xgcd_l()
uses the auxiliary functions
sadd()
and
ssub()
for the (exceptional) calculation of a signed addition and subtraction. Each
of these functions contains a prelude that deals with the sign as an argument
to be passed, and then calls the kernel functions
add()
and
sub()
(cf. Chapter
5), which execute addition and subtraction, respectively, without consideration
of overflow or underflow. Based on the division function
div_l()
for natural
numbers there exists the auxiliary function
smod()
, which forms the residue
a
mod
b
with
a, b
,b >
0
. These auxiliary functions will be needed again
later, in connection with the application of the Chinese remainder theorem in the
function
chinrem_l()
(see Section 10.4.3). In a possible extension of the FLINT/C
library for processing integers they could be used as models for handling signs.
A hint for using the following function is in order: If the arguments satisfy
a, b ≥ N
max
/
2
, an overflow in the factors
u
and
v
, which are returned as the
result of
xgcd_l()
, can occur. In such cases enough space must be reserved for
holding
u
and
v
, which are then declared by the calling program as type
CLINTD
or
CLINTQ
as required (see Chapter 2).
∈
Z
