Cryptography Reference
In-Depth Information
Function:
extended Euclidean algorithm for calculating the
representation
gcd(
a, b
)=
u · a
+
v · b
for natural
numbers
a, b
void xgcd_l (CLINT a_l, CLINT b_l, CLINT g_l,
CLINT u_l, int *sign_u,
CLINT v_l, int *sign_v);
Syntax:
a_l, b_l
(operands)
Input:
Output:
g_l
(gcd of
a_l
and
b_l
)
u_l, v_l
(factors of
a_l
and
b_l
in the representation
of
g_l)
*sign_u
(sign of
u_l
)
*sign_v
(sign of
v_l)
.
void
xgcd_l (CLINT a_l, CLINT b_l, CLINT d_l, CLINT u_l, int *sign_u, CLINT v_l,
int *sign_v)
{
CLINT v1_l, v3_l, t1_l, t3_l, q_l;
CLINTD tmp_l, tmpu_l, tmpv_l;
int sign_v1, sign_t1;
Step 1: Initialization.
cpy_l (d_l, a_l);
cpy_l (v3_l, b_l);
if (EQZ_L (v3_l))
{
SETONE_L (u_l);
SETZERO_L (v_l);
*sign_u = 1;
*sign_v = 1;
return;
}
SETONE_L (tmpu_l);
*sign_u = 1;
SETZERO_L (v1_l);
sign_v1 = 1;
Step 2: Main loop; calculation of the greatest common divisor and of
u
.
