Cryptography Reference
In-Depth Information
/* step 2: loop to approximate the root until y_l
≥
x_l */
while (1)
{
umul_l (x_l, (USHORT)(b-1), y_l);
umexp_l (x_l, (USHORT)(b-1), z_l, max_l);
div_l (n_l, z_l, z_l, junk_l);
add_l (y_l, z_l, y_l);
udiv_l (y_l, b, y_l, junk_l);
if (LT_L (y_l, x_l))
{
assign_l (x_l, y_l);
}
else
{
break;
}
}
cpy_l (floor_l, x_l);
return E_CLINT_OK;
}
To determine whether a number
n
is a
b
th root of another number, it suffices
to raise the output value by
introot_l()
to the
b
th power and compare the result
with
n
. If the values are unequal, then
n
is clearly not a root. For square roots one
must, however, admit that this is not the most efficient method. There are criteria
that in many cases can recognize such numbers that are not squares without the
explicit calculation of root and square. Such an algorithm is given in [Cohe]. It
uses four tables,
q
11
,
q
63
,
q
64
,and
q
65
, in which the quadratic residues modulo
11, 63, 64, and 65 are labeled with a “1” and the quadratic nonresidues with a “0”:
q
11[
k
]
←
0
for
k
=0
,...,
10
,
11[
k
2
mod 11]
←
1
for
k
=0
,...,
5
,
q
63[
k
]
←
0
for
k
=0
,...,
62
,
63[
k
2
mod 63]
←
1
for
k
=0
,...,
31
,
q
64[
k
]
0
for
k
=0
,...,
63
,
64[
k
2
mod 64]
1
for
k
=0
,...,
31
,
q
65[
k
]
←
0
for
k
=0
,...,
64
,
65[
k
2
mod 65]
←
1
for
k
=0
,...,
32
.
←
←
From the representation of the residue class ring as the absolute smallest residue
system (cf. page 70) one sees that we obtain all squares in this way.
Algorithm for identifying an integer
n>
0
as a square. In this case the square
root of
n
is output (from [Cohe], Algorithm 1.7.3)
1.
Set
t ← n
mod 64
.If
q
64[
t
]=0
,then
n
is not a square and we are done.
Otherwise, set
r
←
n
mod (11
·
63
·
65)
.
