Cryptography Reference
In-Depth Information
(
a
2
a
1
a
0
)
B
·
(
a
2
a
1
a
0
)
B
a
2
a
0
a
1
a
0
a
0
a
0
+
a
2
a
1
a
1
a
1
a
0
a
1
+
a
2
a
2
a
1
a
2
a
0
a
2
p
5
p
0
B
p
4
p
3
p
2
p
1
Figure 4-2. Calculations for squaring
We recognize that the inner products
a
i
a
j
for
i
=
j
appear once (in boldface
in Figure 4-2) and twice for
i
=
j
(in boxes in the figure). Thus we can save three
out of nine multiplications by multiplying the sum
a
i
a
j
B
i
+
j
for
i < j
by
2
. The
sum of the inner products of a square can then be written as
n
−
1
n
−
2
n
−
1
n
−
1
a
i
a
j
B
i
+
j
=2
a
i
a
j
B
i
+
j
+
a
i
B
2
i
.
p
=
i,j
=0
i
=0
j
=
i
+1
j
=0
The number of required elementary multiplications is thus reduced with
respect to the school method from
n
2
to
n
(
n
+1)
/
2
.
A natural algorithmic representation of squaring calculates the above
expression with the two summands in two nested loops.
Algorithm 1 for squaring
1.
Set
p
i
←
0
for
i
=0
,...,n−
1
.
2.
Set
i
0
.
3.
Set
t ← p
2
i
+
a
2
i
,
p
2
i
← t
mod
B
, and
c ←t/B
←
.
4.
Set
j ← i
+1
.If
j
=
n
, go to step 7.
5.
Set
t ← p
i
+
j
+2
a
i
a
j
+
c
,
p
i
+
j
← t
(
mod
B
)
, and
c ←t/B
.
6.
Set
j
←
j
+1
;if
j
≤
n
−
1
, go to step 5.
7.
Set
p
i
+
n
← c
.
8.
Set
j ← i
+1
;if
i
=
n −
1
, go to step 7.
9.
Output
p
=(
p
2
n
−
1
p
2
n
−
2
...p
0
)
B
.
In selecting the necessary data types for the representation of the variables we
must note that
t
can assume the value
(
B −
1) + 2(
B −
1)
2
+(
B −
1)=2
B
2
−
2
B
(in step 5 of the algorithm). But this means that for representing
t
to base
B
more
than two digits to base
B
will be needed, since we also have
B
2
1
<
2
B
2
−
−
2
B <
