Cryptography Reference
In-Depth Information
( a 2 a 1 a 0 ) B
· ( b 2 b 2 b 0 ) B
c 20
p 20
p 10
p 00
+
c 21
p 21
p 11
p 01
+
c 22
p 22
p 12
p 02
p 5
p 0 B
p 4
p 3
p 2
p 1
Figure 4-1. Calculations for multiplication
b j for j =0 , 1 , 2 , are calculated:
The values a i b j are the least-significant digits of the terms ( a i b j + carry )
with the inner products a i b j , and the c 2 j are the more-significant digits of
the p 2 j . The partial products are summed at the end to form the product
p =( p 5 p 4 p 3 p 2 p 1 p 0 ) B .
In the general case the product p = ab has the value
First, the partial products ( a 2 a 1 a 0 ) B
·
n 1
m 1
a i b j B i + j .
p =
j =0
i =0
The result of a multiplication of two operands with m and n digits has at least
m + n − 1 andatmost m + n digits. The number of elementary multiplication
steps (that is, multiplications by factors smaller than the base B )is mn .
A multiplication function that followed exactly the schema outlined above
would first calculate all partial products, store these values, and then sum them
up, each provided with the appropriate scaling factor. This school method is
quite suitable for calculating with pencil and paper, but for the possibilities of
a computer program it is somewhat cumbersome. A more efficient alternative
consists in adding the inner products a i b j at once to the accumulated values in
the result digit p i + j , to which are added the carries c from previous steps. The
resulting value for each pair ( i, j ) is assigned to a variable t :
t ← p i + j + a i b j + c,
where t can be represented as
t = kB + l,
0 ≤ k,
l < B,
and we then have
p i + j + a i b j + c ≤ B − 1+( B − 1)( B − 1) + B − 1
=( B
1= B 2
1 <B 2 .
1) B + B
The current value of the result digit is taken by the assignment p i + j ← l from this
representation of t . As the new carry we set c ← k .
 
Search WWH ::




Custom Search