addchain

addchain

Compute addition chains using three methods: Bergeron-Berstel-Brlek-Duboc, Bos-Coster, and Yacobi.

(I have not implemented the Bos-Coster Lucas method.)

See also:

Bergeron, Berstel, Brlek, Duboc. "Addition chains using continued fractions." Journal of Algorithms, vol 10 no 3, 1989, pp. 403--412.

Bergeron, Berstel, Brlek. "Efficient computation of addition chains." Journal de Théorie des Nombres de Bordeaux, vol 6 no 1, 1994, pp. 21--38.

Bos, Coster. "Addition chain heuristics." In Proceedings of CRYPTO, Aug. 1989.

Doche. "Chapter 9: Exponentiation." In Cohen, Frey, Doche, eds. Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, 2005.

Yacobi, Y. "Exponentiating faster with addition chains." In Proceedings of EUROCRYPT, May 1990.

Yacobi, Y. "Fast exponentiation using data compression." Siam J. Computing, vol 28 no 2, 1998, pp. 700-703.

license

Copyright 2018 Riad S. Wahby <rsw@cs.stanford.edu>

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.