Cryptography Reference
In-Depth Information
2
B
2
1
, and so a
ULONG
will not suffice for representing
t
(the inequality above
is derived from the fact that one additional binary digit is needed). While this
poses no problem for an assembler implementation, in which one has access to
the carry bit of the CPU, it is difficult in C to handle the additional binary digit. To
get around this dilemma, we alter the algorithm in such a way that in step 5 the
required multiplication by
2
is carried out in a separate loop. It is then required
that step 3 be carried out in its own loop, whereby for a slight extra expenditure of
effort in loop management we are spared the additional binary digit. The altered
algorithm is as follows.
−
Algorithm 2 for squaring
1.
Initialization: Set
p
i
←
0
for
i
=0
,...,n
−
1
.
2.
Calculate the product of digits of unequal index: Set
i
←
0
.
3.
Set
j
←
i
+1
and
c
←
0
.
4.
Set
t ← p
i
+
j
+
a
i
a
j
+
c
,
p
i
+
j
← t
mod
B
, and
c ←t/B
.
5.
Set
j ← j
+1
;if
j ≤ n −
1
, go to step 4.
6.
Set
p
i
+
n
← c
.
7.
Set
i ← i
+1
;if
i ≤ n −
2
, go to step 3.
8.
Multiplication of inner products by
2
:Set
i ←
1
and
c ←
0
.
9.
Set
t ←
2
p
i
+
c
,
p
i
← t
mod
B
,and
c ←t/B
.
10.
Set
i ← i
+1
;if
i ≤
2
n −
2
, go to step 9.
11.
Set
p
2
n
−
1
← c
.
12.
Addition of the inner squares: Set
i ←
0
and
c ←
0
.
13.
Set
t ← p
2
i
+
a
i
+
c
,
p
2
i
← t
mod
B
,and
c ←t/B
.
14.
Set
t
←
p
2
i
+1
+
c
,
p
2
i
+1
←
t
mod
B
,and
c
←
t/B
.
15.
Set
i
←
i
+1
;if
i
≤
n
−
1
, go to step 13.
16.
Set
p
2
n
−
1
←
p
2
n
−
1
+
c
; output
p
=(
p
2
n
−
1
p
2
n
−
2
...p
0
)
B
.
In the C function for squaring the initialization in step 1 is likewise, in analogy
to multiplication, replaced by the calculation and storing of the first partial
product
a
0
(
a
n
−
1
a
n
−
2
...a
1
)
B
.
