Cryptography Reference
In-Depth Information
In consideration of the ranges of numbers for which the FLINT/C package
was developed, it appears that with
k
=5
we have found the universal base
M
=2
k
, with which, however, there is a rather high memory requirement of 15
kilobytes for the powers
a
2
,a
3
,...,a
31
to base
a
that are to be precomputed.
The
M
-ary algorithm can be improved, however, according to [Cohe], Section 1.2,
to the extent that we can employ not
M −
2
, but only
M/
2
, premultiplications
and thus require only half the memory. The task now additionally consists in
the calculation of the power
a
e
mod
m
,where
e
=(
e
n
−
1
e
n
−
2
...e
0
)
M
is the
representation of the exponent to the base
M
=2
k
.
M
-ary Algorithm for exponentiation with reduced number of
premultiplications
1.
Compute and store
a
3
mod
m
,
a
5
mod
m
,
a
7
mod
m
,
...
,
a
2
k
−
1
mod
m
.
2.
If
e
n
−
1
=0
, set
p ←
1
.
If
e
n
−
1
=0
, factor
e
n
−
1
=2
t
u
with odd
u
.Set
p
a
u
mod
m
and then
←
p ← p
2
t
mod
m
.
In each case set
i ← n −
2
.
p
2
k
mod
m
by calculating
2
p
2
2
2
3.
If
e
i
=0
, set
p
←
···
···
mod
m
(
k
-fold squaring modulo
m
).
If
e
i
=0
, factor
e
i
=2
t
u
with odd
u
; set
p ← p
2
k
−
t
mod
m
and then
p
2
t
mod
m
.
pa
u
mod
m
; now set
p
p
←
←
4.
Set
i
←
i
−
1
;if
i
≥
0
, go to step 3.
5.
Output
p
.
The trick of this algorithm consists in dividing up the squarings required in step 3
in a clever way, such that the exponentiation of
a
is taken care of together with the
even part
2
t
of
e
i
. Within the squaring process the exponentiation of
a
by the odd
part
u
of
e
i
remains. The balance between multiplication and squaring is shifted
to the more favorable squaring, and only the powers of
a
with odd exponent need
to be precomputed and stored.
For this splitting one requires the uniquely determined representation
e
i
=2
t
u
,
u
odd, of the exponent digit
e
i
. For rapid access to
t
and
u
a table is
used, which, for example, for
k
=5
is displayed in Table 6-3.
To calculate these values we can use the auxiliary function
twofact_l()
,
which will be introduced in Section 10.4.1. Before we can program the improved
M
-ary algorithm there remains one problem to be solved: How, beginning with
the binary representation of the exponent or the representation to base
B
=2
16
,
do we efficiently obtain its representation to base
M
=2
k
for a variable
k>
0
?
It will be of use here to do a bit of juggling with the various indices, and we can
