Dual Exponentiation Schemes
Colin D. Walter
Information Security GroupRoyal Holloway University of London
Colin.Walter@rhul.ac.uk
29 Feb 2012

The Problem
Motivation: New algorithms are always useful as
there are always so many different optimisations andconflicting pressures on resource-constrained platforms.
Aim:

Better exponentiation on space-limited chip.
(Fast memory is expensive.)

Setting: Mixed base representation for the exponent.
Solution: Define a dual for the associated addition chain.
Benefits: Derive new algorithms from existing ones;
Better understanding of exponentiation.

2 / 30

Dual Exponentiation Colin D. Walter

Outline
1 Background
2 The Transposition Method
3 Space Duality
4 Extra Requirements
5 New Algorithms
6 Conclusion

3 / 30

Dual Exponentiation Colin D. Walter

Background
1 Background
2 The Transposition Method
3 Space Duality
4 Extra Requirements
5 New Algorithms
6 Conclusion

4 / 30

Dual Exponentiation Colin D. Walterr -ary Exponentiation — L2R (Brauer, 1939)g ∈ G,
D = ((dn−1 r +dn−2 )r + . . . +d1 )r +d0 ∈ N where 0≤di <r .
Output: g D ∈G——————————————————————————
Inputs:

Initialise table: T [d] ← g d for all d, 0<d<r .
P ← 1G
for i ← n−1 downto 0 do {if i 6= n−1 then P ← P r
if di 6= 0 then P ← P×T [di ] }return P

5 / 30

Dual Exponentiation Colin D. Walterr -ary Exponentiation — R2L (Yao, 1976)g ∈ G,
D = dn−1 r n−1 +dn−2 r n−2 + . . . +d1 r 1 +d0 where 0≤di <r .
Output: g D ∈G——————————————————————————

Inputs:

Initialise table: T [d] ← 1G for all d, 0<d<r .
P←gfor i ← 0 to n−1 do {if di 6= 0 then T [di ] ← T [di ]×P
if i Q
6= n−1 then P ← P r }return d:0<d<r T [d]d6 / 30

Dual Exponentiation Colin D. Walter

Sliding Window — L2R
g ∈ G,
D = ((dn−1 rn−2 +dn−2 )rn−3 + . . . +d1 )r0 +d0 ∈ N, wheredi ∈{0, ±1, ±3, . . . , ± 12 (r −1)}, ri ∈{2, 2w } and di =0 if ri =2.
Output: g D ∈G——————————————————————————
Inputs:

Initialise table: T [d] ← g d for all d 6= 0.
P ← 1G
for i ← n−1 downto 0 do {if i 6= n−1 then P ← P ri
if di 6= 0 then P ← P×T [di ] }return P

7 / 30

Dual Exponentiation Colin D. Walter

Sliding Window — R2L
g ∈ G,
D = ((dn−1 rn−2 +dn−2 )rn−3 + . . . +d1 )r0 +d0 ∈ N, wheredi ∈{0, ±1, ±3, . . . , ± 12 (r −1)}, ri ∈{2, 2w } and di =0 if ri =2.
Output: g D ∈G——————————————————————————
Inputs:

Initialise table: T [d] ← 1G for all d 6= 0.
P←g
for i ← 0 to n−1 do {if di 6= 0 then T [di ] ← T [di ]×P
if i Q
6= n−1 then P ← P ri }return d6=0 T [d]d8 / 30

Dual Exponentiation Colin D. WalterMixed Base Exponentiation — L2R
g ∈ G,
D = ((dn−1 rn−2 +dn−2 )rn−3 + . . . +d1 )r0 +d0 ∈ N,
where (ri , di ) ∈ R×D.
Output: g D ∈G————————————————————————–
Inputs:

Initialise table: T [d] ← g d for all d ∈ D \ {0}.
P ← 1G
for i ← n−1 downto 0 do {if i 6= n−1 then P ← P ri
if di 6= 0 then P ← P×T [di ] }return P

9 / 30

Dual Exponentiation Colin D. WalterMixed Base Exponentiation — R2L
g ∈ G,
D = ((dn−1 rn−2 +dn−2 )rn−3 + . . . +d1 )r0 +d0 ∈ N,
where (ri , di ) ∈ R×D.
Output: g D ∈G————————————————————————–
Inputs:

Initialise table: T [d] ← 1G for all d ∈ D \ {0}.
P←g
for i ← 0 to n−1 do {if di 6= 0 then T [di ] ← T [di ]×P
if i Q
6= n−1 then P ← P ri }return d∈D\{0} T [d]d10 / 30

Dual Exponentiation Colin D. WalterA Compact Right-to-Left Algorithm (Arith13, 1997)g ∈ G,
D = ((dn−1 rn−2 +dn−2 )rn−3 + . . . +d1 )r0 +d0 ∈ N,
where (ri , di ) ∈ R×D.
Output: g D ∈G————————————————————————
Inputs:T ← 1GP←g
for i ← 0 to n−1 do {if di 6= 0 then T ← T ×P di
if i 6= n−1 then P ← P ri }return T
The loop body involves computing P di en route to P ri .

11 / 30

Dual Exponentiation Colin D. Walter

The Transposition Method
1 Background
2 The Transposition Method
3 Space Duality
4 Extra Requirements
5 New Algorithms
6 Conclusion

12 / 30

Dual Exponentiation Colin D. Walter

The Computational Di-Graph
An addition chain for D yields a computational, acyclic di-graph:n3n5Here is that for
1+1=2; 1+2=3; 2+3=5.
n1n2dFor convenience, nodes are numbered so nd represents g .
Addition i+j = k gives directed edges ni nk and nj nk .
It is acyclic, with a single root n1 and a single leaf n5 .
All nodes except root n1 have input degree 2 as all ops are binary.
#Ops = #Nodes−1 = 12 #Edges.
By induction, D = #paths from n1 to nD .

13 / 30

Dual Exponentiation Colin D. Walter

Di-Graph for the Transpose Method
n3

n1

n5

n2

Reverse the edges for the “transposition” method.
Node inputs are again multiplied together.
Path count is D, as before. So it again computes g D .
Nodes may need merging or expanding to restore in-degree 2.
The #binary operations is not changed: 12 #edges.
This reverses the addition chain in some sense.
It doesn’t preserve space requirements andwithout care, sqg & multn counts may change.

14 / 30

Dual Exponentiation Colin D. WalterSpace Duality
1 Background
2 The Transposition Method
3 Space Duality
4 Extra Requirements
5 New Algorithms
6 Conclusion

15 / 30

Dual Exponentiation Colin D. WalterSpace-Aware Addition Chains
Definition. For a given set of registers, take five classes of “atomic” ops :Copying one register to another;
Copying one register to another & initialising source register to 1G ;In-place squaring of the contents of one register;Multiplying two different registers into one of the input registers;
Multiplying two different registers into one of the input registers,& initialising the other input to 1G .
A space-aware addition chain is a sequence of such operations in which
the registers are named.
Every addition chain can be written as a space-aware addition chain.

16 / 30

Dual Exponentiation Colin D. Walter

Matrix Representation — SpaceFor a device with two locations, matrix examples of each class are:

 
 
 



1 0
0 0
2 0
1 1
1 1
,
,
,
, and
.
1 0
1 0
0 1
0 1
0 0
They act on a column vector containing the values in each register.
By omitting more general opns , this set is closed under transposition.
Copy (without initialise) becomes multiplication with initialise,
and vice versa. (The red matrices.)
Other operations stay in their class under transposition.
Definition. The dual of a space-aware chain is its transpose.
(The transposed operations are applied in reverse order.)The dual uses the same space but may not have the same multn count.
17 / 30

Dual Exponentiation Colin D. Walter

Matrix Representation — SpaceFor a device with two locations, matrix examples of each class are:

 
 
 



1 0
0 0
2 0
1 1
1 1
,
,
,
, and
.
1 0
1 0
0 1
0 1
0 0
They act on a column vector containing the values in each register.
By omitting more general opns , this set is closed under transposition.
Copy (without initialise) becomes multiplication with initialise,
and vice versa. (The red matrices.)
Other operations stay in their class under transposition.
Definition. The dual of a space-aware chain is its transpose.
(The transposed operations are applied in reverse order.)The dual uses the same space but may not have the same multn count.
17 / 30

Dual Exponentiation Colin D. Walter

Matrix Representation — SpaceFor a device with two locations, matrix examples of each class are:

 
 
 



1 0
0 0
2 0
1 1
1 1
,
,
,
, and
.
1 0
1 0
0 1
0 1
0 0
They act on a column vector containing the values in each register.
By omitting more general opns , this set is closed under transposition.
Copy (without initialise) becomes multiplication with initialise,
and vice versa. (The red matrices.)
Other operations stay in their class under transposition.
Definition. The dual of a space-aware chain is its transpose.
(The transposed operations are applied in reverse order.)The dual uses the same space but may not have the same multn count.
17 / 30

Dual Exponentiation Colin D. Walter

The Dual Chain — An Example
R3 ← R2; R3 ← R2+R3; R1 ←I R2; R2 ←I R3; R2 ←I R1+R2
In matrices acting on a colmn vector:









0 0 0
1 0 0
0 1 0
1 0 0
1 0 0
0 0 0
 1 1 0  0 0 1  0 0 0  0 1 0  0 1 0  =  0 3 0 
0 0 1
0 0 0
0 0 1
0 1 1
0 1 0
0 0 0

The dual (the transpose) is:









1 0 0
1 0 0
0 0 0
1 0 0
0 1 0
0 0 0
 0 1 1  0 1 1  1 0 0  0 0 0  0 1 0  =  0 3 0 
0 0 0
0 0 1
0 0 1
0 1 0
0 0 1
0 0 0

i.e. R1 ← R2; R3 ←I R2; R2 ←I R1; R2 ← R2+R3; R2 ←I R2+R3
Both have two multiplications and no squarings.
Both compute g 3 from g ∈ G with R2 for I/O.
18 / 30

Dual Exponentiation Colin D. Walter

Extra Requirements
1 Background
2 The Transposition Method
3 Space Duality
4 Extra Requirements
5 New Algorithms
6 Conclusion

19 / 30

Dual Exponentiation Colin D. Walter

The Main Problems
1#Mults may not be preserved in the dual
as copying becomes multn with initialisation.

2

The dual chain may not compute the same value
unless the matrix product is symmetric.

To overcome the first of these, extra conditions are required:Select the initialising opn when possible.
Eliminate 1G as an operand.
Remove operations whose output is not used.
Fix a subset of registers for I/O.
(An I/O register must read input and write non-trivial output.)
Definition. A space-aware chain is normalised if the above hold.

20 / 30

Dual Exponentiation Colin D. Walter

The Main Problems
1#Mults may not be preserved in the dual
as copying becomes multn with initialisation.

2

The dual chain may not compute the same value
unless the matrix product is symmetric.

To overcome the first of these, extra conditions are required:Select the initialising opn when possible.
Eliminate 1G as an operand.
Remove operations whose output is not used.
Fix a subset of registers for I/O.
(An I/O register must read input and write non-trivial output.)
Definition. A space-aware chain is normalised if the above hold.

20 / 30

Dual Exponentiation Colin D. Walter

The Main Problems
1#Mults may not be preserved in the dual
as copying becomes multn with initialisation.

2

The dual chain may not compute the same value
unless the matrix product is symmetric.

To overcome the first of these, extra conditions are required:Select the initialising opn when possible.
Eliminate 1G as an operand.
Remove operations whose output is not used.
Fix a subset of registers for I/O.
(An I/O register must read input and write non-trivial output.)
Definition. A space-aware chain is normalised if the above hold.

20 / 30

Dual Exponentiation Colin D. Walter

Counting Ones
Instances of 1G or ⊥ arise from:a) Initial value of a non-input register.
b) Initialised by copy or multn opn .
Instances of 1G or ⊥ finish their lives as:c) Final value in a non-output register.
d) Overwritten by a copy opn .
Since #a = #c, we conclude #b = #d.
Subtracting the #{copies with initn } from #b and #d, we have#Multns with initn = #Copies without initn
These opn types are swapped in the dual & others stay as they are. So:
Theorem. For a normalised space-aware chain,#Multns & #Sqres are the same for the dual.
21 / 30

Dual Exponentiation Colin D. Walter

Counting Ones
Instances of 1G or ⊥ arise from:a) Initial value of a non-input register.
b) Initialised by copy or multn opn .
Instances of 1G or ⊥ finish their lives as:c) Final value in a non-output register.
d) Overwritten by a copy opn .
Since #a = #c, we conclude #b = #d.
Subtracting the #{copies with initn } from #b and #d, we have#Multns with initn = #Copies without initn
These opn types are swapped in the dual & others stay as they are. So:
Theorem. For a normalised space-aware chain,#Multns & #Sqres are the same for the dual.
21 / 30

Dual Exponentiation Colin D. Walter

Counting Ones
Instances of 1G or ⊥ arise from:a) Initial value of a non-input register.
b) Initialised by copy or multn opn .
Instances of 1G or ⊥ finish their lives as:c) Final value in a non-output register.
d) Overwritten by a copy opn .
Since #a = #c, we conclude #b = #d.
Subtracting the #{copies with initn } from #b and #d, we have#Multns with initn = #Copies without initn
These opn types are swapped in the dual & others stay as they are. So:
Theorem. For a normalised space-aware chain,#Multns & #Sqres are the same for the dual.
21 / 30

Dual Exponentiation Colin D. Walter

Counting Ones
Instances of 1G or ⊥ arise from:a) Initial value of a non-input register.
b) Initialised by copy or multn opn .
Instances of 1G or ⊥ finish their lives as:c) Final value in a non-output register.
d) Overwritten by a copy opn .
Since #a = #c, we conclude #b = #d.
Subtracting the #{copies with initn } from #b and #d, we have#Multns with initn = #Copies without initn
These opn types are swapped in the dual & others stay as they are. So:
Theorem. For a normalised space-aware chain,#Multns & #Sqres are the same for the dual.
21 / 30

Dual Exponentiation Colin D. WalterSymmetric Cases
If the action of a (multi-) exponentiation function f on registers is
described by matrix M then a dual f ∗ is described by the transpose M T .
Theorem a) f ∗ computes the same values as f iff its matrix is symmetric.
b) In particular, it uses the same registers for output as input.
In the normalised case, unused registers give columns of zeros.
Used, non-output registers are over-written with 1G : more zeros.
Used, non-input registers are initialised to 1G : more zeros.
So only the sub-matrix MIO on I/O registers need be symmetric.
Theorem A normalised space-aware chain for a single
exponentiation and its dual compute the same values.
(Duals become unique only when written in atomic operations.)

22 / 30

Dual Exponentiation Colin D. WalterSymmetric Cases
If the action of a (multi-) exponentiation function f on registers is
described by matrix M then a dual f ∗ is described by the transpose M T .
Theorem a) f ∗ computes the same values as f iff its matrix is symmetric.
b) In particular, it uses the same registers for output as input.
In the normalised case, unused registers give columns of zeros.
Used, non-output registers are over-written with 1G : more zeros.
Used, non-input registers are initialised to 1G : more zeros.
So only the sub-matrix MIO on I/O registers need be symmetric.
Theorem A normalised space-aware chain for a single
exponentiation and its dual compute the same values.
(Duals become unique only when written in atomic operations.)

22 / 30

Dual Exponentiation Colin D. WalterSymmetric Cases
If the action of a (multi-) exponentiation function f on registers is
described by matrix M then a dual f ∗ is described by the transpose M T .
Theorem a) f ∗ computes the same values as f iff its matrix is symmetric.
b) In particular, it uses the same registers for output as input.
In the normalised case, unused registers give columns of zeros.
Used, non-output registers are over-written with 1G : more zeros.
Used, non-input registers are initialised to 1G : more zeros.
So only the sub-matrix MIO on I/O registers need be symmetric.
Theorem A normalised space-aware chain for a single
exponentiation and its dual compute the same values.
(Duals become unique only when written in atomic operations.)

22 / 30

Dual Exponentiation Colin D. Walter

New Algorithms
1 Background
2 The Transposition Method
3 Space Duality
4 Extra Requirements
5 New Algorithms
6 Conclusion

23 / 30

Dual Exponentiation Colin D. Walter

High Level Algorithms
Question: When is an algorithm dualisable if its steps are more complex
than the atomic operations?
We want to be able to decompose steps independently into atomic opns
yet obtain the normalised property when all steps are concatenated.
Solution: For each step the values initially in its non-input registers mustnot be used and its used non-output registers must be reset to 1G .
The output registers for one step must be the input registers for the next.
(Include unused registers in the I/O set for convenience here.)
These are only requirements on how steps are realised as space-aware
chains. So not a restriction on algorithm formulation.
Definition The dual of a high level exponentiation algorithm is thatgiven by transposing its steps and reversing their order.

24 / 30

Dual Exponentiation Colin D. Walter

High Level Algorithms
Question: When is an algorithm dualisable if its steps are more complex
than the atomic operations?
We want to be able to decompose steps independently into atomic opns
yet obtain the normalised property when all steps are concatenated.
Solution: For each step the values initially in its non-input registers mustnot be used and its used non-output registers must be reset to 1G .
The output registers for one step must be the input registers for the next.
(Include unused registers in the I/O set for convenience here.)
These are only requirements on how steps are realised as space-aware
chains. So not a restriction on algorithm formulation.
Definition The dual of a high level exponentiation algorithm is thatgiven by transposing its steps and reversing their order.

24 / 30

Dual Exponentiation Colin D. Walter

High Level Algorithms
Question: When is an algorithm dualisable if its steps are more complex
than the atomic operations?
We want to be able to decompose steps independently into atomic opns
yet obtain the normalised property when all steps are concatenated.
Solution: For each step the values initially in its non-input registers mustnot be used and its used non-output registers must be reset to 1G .
The output registers for one step must be the input registers for the next.
(Include unused registers in the I/O set for convenience here.)
These are only requirements on how steps are realised as space-aware
chains. So not a restriction on algorithm formulation.
Definition The dual of a high level exponentiation algorithm is thatgiven by transposing its steps and reversing their order.

24 / 30

Dual Exponentiation Colin D. WalterAn “Old” Algorithm (Arith13, 1997)
Inputs: g ∈ G , D = ((dn−1 rn−2 +dn−2 )rn−3 + . . . +d1 )r0 +d0 ∈ N
Output: g D ∈G——————————————————————————T ← 1GP←g
for i ← 0 to n−1 do {if di 6= 0 then T ← T ×P di
if i 6= n−1 then P ← P ri }return T
The loop body involves computing P di en route to P ri .

25 / 30

Dual Exponentiation Colin D. Walter

One Iteration
Base/digit pairs (r , d) are chosen for compact, fast performance.
Specifically at most one register in addition to P and T .
e.g. r = 2i ±1, d = 2j will involve i squarings & 2 mults .
It avoids a table entry for each d.
There is now a dual algorithm using the same space – only three registers.



T
r 0
r d
The step T ←TP d , P←P r is achieved by
=
.
d 1
0 1
So the transpose performs the dual opn P ← P r T d .
The sequence of ops is easily determined via the dual.

26 / 30

Dual Exponentiation Colin D. Walter

One Iteration
Base/digit pairs (r , d) are chosen for compact, fast performance.
Specifically at most one register in addition to P and T .
e.g. r = 2i ±1, d = 2j will involve i squarings & 2 mults .
It avoids a table entry for each d.
There is now a dual algorithm using the same space – only three registers.



T
r 0
r d
The step T ←TP d , P←P r is achieved by
=
.
d 1
0 1
So the transpose performs the dual opn P ← P r T d .
The sequence of ops is easily determined via the dual.

26 / 30

Dual Exponentiation Colin D. Walter

A New Compact Left-to-Right Algorithm
Inputs: g ∈ G , D = ((dn−1 rn−2 +dn−2 )rn−3 + . . . +d1 )r0 +d0 ∈ N
Output: g D ∈G——————————————————————————T ←g
P ← 1G
for i ← n−1 downto 0 do
P ← P ri ×T di
return P
Loop iterations are computed as described on last slide.
It is the dual of the previous R2L algorithm, as just derived.

27 / 30

Dual Exponentiation Colin D. Walter

The Value of the Algorithm“Table-less” exponentiation – useful in constrained environments.
If space for only three registers and division has the same cost as
multn , the compact algorithms are faster.
A left-to-right version allows better use of composite ops ,e.g. double-and-add, triple-and-add, quintuple-and-add.
Recoding is done on-the-fly for R2L expn ; in advance for L2R expn .
The recoding typically needs up to 3 times the storage space of D.

28 / 30

Dual Exponentiation Colin D. Walter

Conclusion
1 Background
2 The Transposition Method
3 Space Duality
4 Extra Requirements
5 New Algorithms
6 Conclusion

29 / 30

Dual Exponentiation Colin D. Walter

Summary & Final Remarks
A general setting enabling most expn algorithms to be
described naturally, namely a mixed base recoding.
A new space- and time-preserving duality
between left-to-right and right-to-left expn algorithms.
A new tableless expn algorithm.
It enables new speed records to be set in certain environments.
New understanding of expn is possible,
e.g. a comparison of R2L initialisation with L2R finalisation steps.
...

30 / 30

Dual Exponentiation Colin D. Walter

Summary & Final Remarks
A general setting enabling most expn algorithms to be
described naturally, namely a mixed base recoding.
A new space- and time-preserving duality
between left-to-right and right-to-left expn algorithms.
A new tableless expn algorithm.
It enables new speed records to be set in certain environments.
New understanding of expn is possible,
e.g. a comparison of R2L initialisation with L2R finalisation steps.
...

30 / 30

Dual Exponentiation Colin D. Walter

Summary & Final Remarks
A general setting enabling most expn algorithms to be
described naturally, namely a mixed base recoding.
A new space- and time-preserving duality
between left-to-right and right-to-left expn algorithms.
A new tableless expn algorithm.
It enables new speed records to be set in certain environments.
New understanding of expn is possible,
e.g. a comparison of R2L initialisation with L2R finalisation steps.
...

30 / 30

Dual Exponentiation Colin D. Walter

Summary & Final Remarks
A general setting enabling most expn algorithms to be
described naturally, namely a mixed base recoding.
A new space- and time-preserving duality
between left-to-right and right-to-left expn algorithms.
A new tableless expn algorithm.
It enables new speed records to be set in certain environments.
New understanding of expn is possible,
e.g. a comparison of R2L initialisation with L2R finalisation steps.
...

30 / 30

Dual Exponentiation Colin D. Walter

Summary & Final Remarks
A general setting enabling most expn algorithms to be
described naturally, namely a mixed base recoding.
A new space- and time-preserving duality
between left-to-right and right-to-left expn algorithms.
A new tableless expn algorithm.
It enables new speed records to be set in certain environments.
New understanding of expn is possible,
e.g. a comparison of R2L initialisation with L2R finalisation steps.
...

30 / 30

Dual Exponentiation Colin D. Walter