Cryptography Reference
In-Depth Information
2.
If
q
63[
r
mod 63] = 0
,then
n
is not a square, and we are done.
3.
If
q
65[
r
mod 65] = 0
,then
n
is not a square, and we are done.
4.
If
q
11[
r
mod 11] = 0
,then
n
is not a square, and we are done.
←
√
n
using the function
iroot_l()
.If
q
2
5.
Compute
q
=
n
,then
n
is not
a square and we are done. Otherwise,
n
is a square, and the square root
q
is
output.
This algorithm appears rather strange due to the particular constants that
appear. But this can be explained: A square
n
has the property for any integer
k
that if it is a square in the integers, then it is a square modulo
k
. We have used the
contrapositive: If
n
is not a square modulo
k
, then it is not a square in the integers.
By applying steps 1 through 4 above we are checking whether
n
is a square
modulo 64, 63, 65, or 11. There are 12 squares modulo 64, 16 squares modulo 63,
21 squares modulo 65, and 6 squares modulo 11, so that the probability that we
are in the case that a number that is not a square has not been identified by these
four steps is
1
1
1
1
=
12
52
64
47
63
44
65
5
11
16
63
·
21
65
·
11
=
6
6
715
.
It is only for these relatively rare cases that the test in step 5 is carried out.
If this test is positive, then
n
is revealed to be a square, and the square root of
n
is determined. The order of the tests in steps 1 through 4 is determined by the
individual probabilities. We have anticipated the following function in Section 6.5
to exclude squares as candidates for primitive roots modulo
p
.
−
−
−
−
64
·
Function:
determining whether a
CLINT
number
n_l
is a square
unsigned int issqr_l(CLINT n_l, CLINT r_l);
Syntax:
n_l
(operand)
Input:
r_l
(square root of
n_l
,or
0
if
n_l
is not a square)
Output:
1if
n_l
is a square
0 otherwise
Return:
static const UCHAR q11[11]=
{1,1, 0, 1, 1, 1, 0, 0, 0, 1, 0};
static const UCHAR q63[63]=
{1,1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1,
0,0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0,
1,0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0};
