1 // Package math provides some utility functions for big integers.
2 package math
3 4 import "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
21 func 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
56 func 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 }
85