|
The general theory of addition chains and the results produced by this demonstration program are described in more detail in the white paper obtainable on the Research page. The demonstration program takes as its input a number in decimal or hexadecimal format and produces an addition chain to construct that number. The program uses the following notation:All addition chains are constructed in 2 registers, called R1 and R2 The registers start with 1 in R1 and 0 in R2 Operations consist of additions, denoted Axyz, meaning "Add the contents of register Rx to the contents of register Ry and put the result in Rz", and doublings, denoted Dxy, meaning "Double the contents of Rx and put the result in Ry." The chain finishes with S for stop. Example. The number 15 (in decimal) is produced by the addition chain D12, A122, D21, D11, A121, S The method chosen for the demonstration has been chosen for speed rather than for best possible results, and should give an answer in under two seconds for 2048-bit numbers. The demonstration will only accept numbers of length up to 2048 bits. For a random n-bit number, the demonstration will produce an addition chain of average length around 1.26n, compared to 1.5n for the binary method and an expected best possible average of around 1.20n. | ||
