Cryptography Reference
In-Depth Information
For the application of the Chinese remainder theorem we must take into account
the signs of the factors
u_l
and
v_l
, represented by the auxiliary variables
sign_u
and
sign_v
, which assume the values calculated by the function
xgcd_l()
. The
result of this step is the root
x
0
.
mul_l (p_l, q_l, n_l);
xgcd_l (p_l, q_l, x0_l, u_l, &sign_u, v_l, &sign_v);
mul_l (u_l, p_l, u_l);
mul_l (u_l, xq_l, u_l);
mul_l (v_l, q_l, v_l);
mul_l (v_l, xp_l, v_l);
sign_u = sadd (u_l, sign_u, v_l, sign_v, x0_l);
smod (x0_l, sign_u, n_l, x0_l);
Now we calculate the roots
x
1
,
x
2
, and
x
3
.
sub_l (n_l, x0_l, x1_l);
msub_l (u_l, v_l, x2_l, n_l);
sub_l (n_l, x2_l, x3_l);
The smallest root is returned as result.
xptr_l = MIN_L (x0_l, x1_l);
xptr_l = MIN_L (xptr_l, x2_l);
xptr_l = MIN_L (xptr_l, x3_l);
cpy_l (x_l, xptr_l);
return 0;
}
From this we can now easily deduce an implementation of the Chinese
remainder theorem by taking the code sequence from the above function and
extending it by the number of congruences that are to be simultaneously solved.
Such a procedure is described in the following algorithm, due to Garner (see
[MOV], page 612), which has an advantage with respect to the application of
the Chinese remainder theorem in the above form in that reduction must take
place only modulo the
m
i
, and not modulo
m
=
m
1
m
2
ยทยทยท
m
r
. This results in a
significant savings in computing time.
