1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
// Package binary implements generic binary addition chain algorithms.
package binary
import (
"math/big"
"github.com/mmcloughlin/addchain"
"github.com/mmcloughlin/addchain/internal/bigint"
)
// References:
//
// [hehcc:exp] Christophe Doche. Exponentiation. Handbook of Elliptic and Hyperelliptic Curve
// Cryptography, chapter 9. 2006.
// http://koclab.cs.ucsb.edu/teaching/ecc/eccPapers/Doche-ch09.pdf
// RightToLeft builds a chain algorithm for the right-to-left binary method,
// akin to [hehcc:exp] Algorithm 9.2.
type RightToLeft struct{}
func (RightToLeft) String() string { return "binary_right_to_left" }
// FindChain applies the right-to-left binary method to n.
func (RightToLeft) FindChain(n *big.Int) (addchain.Chain, error) {
c := addchain.Chain{}
b := new(big.Int).Set(n)
d := bigint.One()
var x *big.Int
for bigint.IsNonZero(b) {
c.AppendClone(d)
if b.Bit(0) == 1 {
if x == nil {
x = bigint.Clone(d)
} else {
x.Add(x, d)
c.AppendClone(x)
}
}
b.Rsh(b, 1)
d.Lsh(d, 1)
}
return c, nil
}
|
