Cryptography Reference
In-Depth Information
with the
M
-ary process, for every nonzero window (in the following called not
quite aptly a “
1
-window”) of length
t
, in addition to the repeated squaring an
additional multiplication by a precalculated factor is required, in analogy to the
corresponding step of the
2
k
-ary procedure:
3
.Set
p ← p
2
t
mod
m
and then set
p ← pa
e
i
mod
m
.
The number of factors to be precomputed depends on the permitted
maximal length of the
1
-window. One should note that the 1-windows in
the least-significant position always have a
1
and thus are always odd. The
factorization of the exponent digit on page 89 into an even and odd factor will
thus at first not be needed. On the other hand, in the course of exponentiation
the exponent is processed from the most-significant to least-significant place,
which means for the implementation that first the
complete
decomposition of the
exponent must be carried out and stored before the actual exponentiation can
take place.
Yet, if we begin the factorization of the exponent at the most-significant
digit and travel from left to right, then every
0
-or
1
-window can be processed
immediately, as soon as it is complete. This means, of course, that we will also
obtain
1
-windows with an even value, but the exponentiation algorithm is
prepared for that.
Both directions of decomposition of the exponent into
1
-windows with fixed
length
l
follow essentially the same algorithm, which we formulate below for
decomposition from right to left.
Decomposition of an integer
e
into 0-windows and 1-windows having fixed
length
l
1.
If the least-significant binary digit is equal to
0
, then begin a
0
-window and
go to step 2; otherwise, begin a
1
-window and go to step 3.
2.
Add the next-higher binary digits in a
0
-window as long as no
1
appears. If a
1
appears, then close the
0
-window, begin a
1
-window, and go to step 3.
3.
Collect a further
l
1
binary digits into a
1
-window. If the next-higher digit
is a
0
, begin a
0
-window and go to step 2; otherwise, begin a
1
-window
and go to step 3. If in the process all digits of
e
have been processed, then
terminate the algorithm.
−
The decomposition from left to right begins with the most-significant binary
digit and otherwise proceeds analogously. If we suppose that
e
has no leading
binary zeros, then the algorithm cannot reach the end of the representation of
e
within step 2, and the procedure terminates in step 3 under the same condition
given there. The following examples illustrate this process:
