  Modular exponentiation and scalar multiplication are important operations of
most public key cryptosystems, and their fast calculation is essential to
improve the system efficiency. The shortest addition chain is one of the most
important mathematical concepts to realize the optimization. However, finding a
shortest addition chain of length k is an NP-hard problem, whose time
complexity is comparable to O($k!$). This paper proposes some novel methods to
generate short addition chains. We firstly present a Simplified Power-tree
method by deeply deleting the power-tree, whose time complexity is reduced to
O($k^2$) sacrificing some increasing of the addition chain length. Moreover, a
Cross Window method and its variant are introduced by improving the Window
method. More precisely, the Cross Window method uses the cross correlation to
deal with the windows and its pre-computation is optimized by the Addition
Sequence algorithm. The theoretical analysis is conducted to show the
correctness and effectiveness. Meanwhile, the experiment shows that the new
methods can obtain shorter addition chains compared to the existing methods.
The Cross Window method with the Addition Sequence algorithm can attain 9.5%
reduction of the addition chain length, in the best case, compared to the
Window method.
