cascade exponentiation and simultaneous exponentiation

Wei Dai (weidai@eskimo.com)
Tue, 22 Dec 1998 14:03:27 -0800

• Next message: Mok-Kong Shen: "On living with the 56-bit key length restriction"
• Previous message: Mok-Kong Shen: "WEAK2-EX -- A Poorman's 56-bit Data Encryption Algorithm"

Has anyone noticed an interesting duality between cascade exponentiation
(computing g1^e1*g2^e2*...*gn^en) and simultaneous exponentiation
(computing g^e1, g^e2, ..., g^en. I'm not sure this is an established
terminology.)? It seems every algorithm for cascade exponentiation has a
counterpart for simultaneous exponentiation that takes the same number of
squarings and multiplications on average.

Also, the well-known left-to-right sliding window k-ary exponentation
algorithm (HAC 14.85) begins with a simultaneous exponentiation (computing
the power table g^1, g^3, ..., g^(2^k-1)). There also exists a
right-to-left sliding window k-ary exponentiation algorithm that ends with
a cascade exponentiation, although I'm not sure if this latter algorithm
has been published.

What is the explanation for this duality?

• Next message: Mok-Kong Shen: "On living with the 56-bit key length restriction"
• Previous message: Mok-Kong Shen: "WEAK2-EX -- A Poorman's 56-bit Data Encryption Algorithm"