Cryptography Reference
In-Depth Information
calculates solutions
x
1
and
x
2
of the congruences
x
2
≡
a
mod
p,
x
2
≡ a
mod
q.
From
x
1
and
x
2
we assemble according to the method just discussed the solutions
to the congruence
x
2
≡
a
mod
pq,
and the output is the smallest square root of
a
modulo
pq
.
calculate the square root of
a
modulo
p
·
q
Function:
for odd primes
p, q
int root_l (CLINT a_l, CLINT p_l, CLINT q_l, CLINT x_l);
Syntax:
a_l, p_l, q_l
(operands, primes
p_l, q_l
>
2
)
Input:
x_l
(square root of
a_l
modulo
p_l * q_l
)
Output:
Return:
0if
a_l
is a quadratic residue modulo
p_l * q_l
−
1
otherwise
int
root_l (CLINT a_l, CLINT p_l, CLINT q_l, CLINT x_l)
{
CLINT x0_l, x1_l, x2_l, x3_l, xp_l, xq_l, n_l;
CLINTD u_l, v_l;
clint *xptr_l;
int sign_u, sign_v;
Calculate the roots modulo
p_l
and
q_l
with the function
proot_l()
.If
a_l == 0
,
the result is
0
.
if (0 != proot_l (a_l, p_l, xp_l) || 0 != proot_l (a_l, q_l, xq_l))
{
return -1;
}
if (EQZ_L (a_l))
{
SETZERO_L (x_l);
return 0;
}
