NAF calculation algo

[Raneet10]

Hey guys! I was wondering what algo or calculator you used to determine the NAF representation of u ? More context: I was breezing through go-ethereum's implementation and the NAF form caught my eye (see ethereum/go-ethereum#27957). Now from what I know, the NAF form cannot have non zero bits adjacent to each other but not sure whether there can be some exceptions to this.

[armfazh]

The w-NAF method is a classic number system. You can find a complete description on the book "Guide to ECC" (Page 99 and 100) https://www.google.com/books/edition/Guide_to_Elliptic_Curve_Cryptography/V5oACAAAQBAJ?hl=en&gbpv=1&pg=PA99&printsec=frontcover

Page 99 lists the properties of a w-NAF expansion, so it will become clear the runs of zeros in the expansion.

Fortunately, CIRCL already has an implementation of w-NAF. For the value you pointed in bn256 code, the conversion sets the parameter w=2, so you have 2-NAF, or more shortly NAF.

Program

package main

import (
    "fmt"
    "math/big"

    "github.com/cloudflare/circl/math"
)

// sixuPlus2NAF is 6u+2 in non-adjacent form.
var sixuPlus2NAF = []int8{0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, -1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 1, 0, -1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, -1, 0, -1, 0, 0, 0, 0, 1, 0, 0, 0, 1}

func main() {
    u := new(big.Int).SetUint64(6518589491078791937)
    fmt.Printf("u: %v\n", u)

    sixuPlus2 := new(big.Int)
    sixuPlus2.Mul(u, new(big.Int).SetUint64(6))
    sixuPlus2.Add(sixuPlus2, new(big.Int).SetUint64(2))
    fmt.Printf("6u+2: %v\n", sixuPlus2)

    L := math.OmegaNAF(sixuPlus2, 2)
    fmt.Printf("2-NAF: %v\n", L)

    got := fmt.Sprintf("%v", L)
    want := fmt.Sprintf("%v", sixuPlus2NAF)
    fmt.Printf("same expansion: %v\n", got == want)
}