Targeted Fibonacci Exponentiation

Understand

A targeted exponentiation algorithm computes a group exponentiation operation $a^k$ with a reversible circuit in such a way that the initial state of the circuit consists of only the base $a$ and fixed values, and the final state consists of only the exponential $a^k$ and fixed values.

• Three targeted exponentiation algorithms based on Fibonacci addition chains are considered, offering tradeoffs in terms of the number of working registers and the number of iterations.
• The approaches also motivate related results on the Fibonacci Zeckendorf array, including a new \emph{modular Hofstadter G problem} and an improvement to Anderson's recent algorithm for locating pairs of adjacent integers in the extended Fibonacci Zeckendorf array.
• The algorithms have applications in quantum computing.