1// Package math provides some utility functions for big integers.
 2package math
 3
 4import "math/big"
 5
 6// SignedDigit obtains the signed-digit recoding of n and returns a list L of
 7// digits such that n = sum( L[i]*2^(i*(w-1)) ), and each L[i] is an odd number
 8// in the set {±1, ±3, ..., ±2^(w-1)-1}. The third parameter ensures that the
 9// output has ceil(l/(w-1)) digits.
10//
11// Restrictions:
12//   - n is odd and n > 0.
13//   - 1 < w < 32.
14//   - l >= bit length of n.
15//
16// References:
17//   - Alg.6 in "Exponent Recoding and Regular Exponentiation Algorithms"
18//     by Joye-Tunstall. http://doi.org/10.1007/978-3-642-02384-2_21
19//   - Alg.6 in "Selecting Elliptic Curves for Cryptography: An Efficiency and
20//     Security Analysis" by Bos et al. http://doi.org/10.1007/s13389-015-0097-y
21func SignedDigit(n *big.Int, w, l uint) []int32 {
22	if n.Sign() <= 0 || n.Bit(0) == 0 {
23		panic("n must be non-zero, odd, and positive")
24	}
25	if w <= 1 || w >= 32 {
26		panic("Verify that 1 < w < 32")
27	}
28	if uint(n.BitLen()) > l {
29		panic("n is too big to fit in l digits")
30	}
31	lenN := (l + (w - 1) - 1) / (w - 1) // ceil(l/(w-1))
32	L := make([]int32, lenN+1)
33	var k, v big.Int
34	k.Set(n)
35
36	var i uint
37	for i = 0; i < lenN; i++ {
38		words := k.Bits()
39		value := int32(words[0] & ((1 << w) - 1))
40		value -= int32(1) << (w - 1)
41		L[i] = value
42		v.SetInt64(int64(value))
43		k.Sub(&k, &v)
44		k.Rsh(&k, w-1)
45	}
46	L[i] = int32(k.Int64())
47	return L
48}
49
50// OmegaNAF obtains the window-w Non-Adjacent Form of a positive number n and
51// 1 < w < 32. The returned slice L holds n = sum( L[i]*2^i ).
52//
53// Reference:
54//   - Alg.9 "Efficient arithmetic on Koblitz curves" by Solinas.
55//     http://doi.org/10.1023/A:1008306223194
56func OmegaNAF(n *big.Int, w uint) (L []int32) {
57	if n.Sign() < 0 {
58		panic("n must be positive")
59	}
60	if w <= 1 || w >= 32 {
61		panic("Verify that 1 < w < 32")
62	}
63
64	L = make([]int32, n.BitLen()+1)
65	var k, v big.Int
66	k.Set(n)
67
68	i := 0
69	for ; k.Sign() > 0; i++ {
70		value := int32(0)
71		if k.Bit(0) == 1 {
72			words := k.Bits()
73			value = int32(words[0] & ((1 << w) - 1))
74			if value >= (int32(1) << (w - 1)) {
75				value -= int32(1) << w
76			}
77			v.SetInt64(int64(value))
78			k.Sub(&k, &v)
79		}
80		L[i] = value
81		k.Rsh(&k, 1)
82	}
83	return L[:i]
84}