Cryptography Reference
In-Depth Information
Step 3: End of the procedure; otherwise, find the smallest
m
such that
z
2
m
≡
1mod
p
.
mod _l (b_l, p_l, q_l);
while (!equ_l (q_l, one_l))
{
m=0;
do
{
++m;
msqr_l (q_l, q_l, p_l);
}
while (!equ_l (q_l, one_l));
if (m == r)
{
return -1;
}
Step 4: Recursion step for
x
,
y
,
z
, and
r
.
mexp2_l (y_l, (ULONG)(r-m-1),t_l, p_l);
msqr_l (t_l, y_l, p_l);
mmul_l (x_l, t_l, x_l, p_l);
mmul_l (b_l, y_l, b_l, p_l);
cpy_l (q_l, b_l);
r=m;
}
return 0;
}
The calculation of roots modulo prime powers
p
k
can now be accomplished
on the basis of our results modulo
p
. To this end we first consider the congruence
x
2
≡ a
mod
p
2
(10.18)
based on the following approach: Given a solution
x
1
of the above congruence
x
2
≡
a
mod
p
we set
x
:=
x
1
+
p
·
x
2
, from which follows
− a ≡ x
1
− a
+2
px
1
x
2
+
p
2
x
2
≡ p
x
1
−
a
p
+2
x
1
x
2
mod
p
2
.
x
2
