bug: NAF decomposition doesn't enforce checks on adjacent values

[ivokub]

Description

The method focumentation is:

ToNAF returns the NAF decomposition of given input. The non-adjacent form (NAF) of a number is a unique signed-digit representation, in which non-zero values cannot be adjacent. For example, NAF(13) = [1, 0, -1, 0, 1].
But this check is not enforced, see

diff --git a/std/math/bits/hints.go b/std/math/bits/hints.go
index bb3da6d13..58a8ae42b 100644
--- a/std/math/bits/hints.go
+++ b/std/math/bits/hints.go
@@ -95,13 +95,14 @@ func nafDecomposition(a *big.Int, results []*big.Int) error {
 		if buf.Cmp(&zero) == 0 {
 			results[n].SetUint64(0)
 		} else { // aCopy odd
-			buf.And(&aCopy, &three)
-			if buf.IsUint64() && buf.Uint64() == 3 {
-				results[n].SetInt64(-1)
-				aCopy.Add(&aCopy, &one)
-			} else {
-				results[n].SetUint64(1)
-			}
+			results[n].SetUint64(1)
+			// buf.And(&aCopy, &three)
+			// if buf.IsUint64() && buf.Uint64() == 3 {
+			// 	results[n].SetInt64(-1)
+			// 	aCopy.Add(&aCopy, &one)
+			// } else {
+			// 	results[n].SetUint64(1)
+			// }
 		}
 		aCopy.Rsh(&aCopy, 1)
 		n++
diff --git a/std/math/bits/naf_test.go b/std/math/bits/naf_test.go
index 2ead74a68..a2ca467de 100644
--- a/std/math/bits/naf_test.go
+++ b/std/math/bits/naf_test.go
@@ -28,5 +28,5 @@ func (c *toNAFCircuit) Define(api frontend.API) error {
 
 func TestToNAF(t *testing.T) {
 	assert := test.NewAssert(t)
-	assert.ProverSucceeded(&toNAFCircuit{}, &toNAFCircuit{A: 13, B0: 1, B1: 0, B2: -1, B3: 0, B4: 1})
+	assert.ProverSucceeded(&toNAFCircuit{}, &toNAFCircuit{A: 13, B0: 1, B1: 0, B2: 1, B3: 1, B4: 0})
 }

We should either fix it or remove the method as it is not used anymore.

cc. @gbotrel, @yelhousni

[yelhousni]

I suggest to remove the method. Usually 2-NAF representation is used to reduce the number of operations because of the lower Hamming weight compared to the bit representation. But anyway in-circuit the number of operations is related to the number of bits and not the representation because of the lack of branching. Originally we implemented this method to experiment with but ended up never using it so I suggest to remove it.

[gbotrel]

ok to remove, will open a PR.