# Crypto Sometimes Likes Zero: Meet Non-adjacent Form

Here is a bit of trivia for you … why do we use 65,537 as the encryption exponent value for RSA?

Well, 65,537 is a prime number as the encryption exponent cannot share a factor with (p-1)(q-1). Also, in its binary representation of “**10000000000000001**”, we can see that it has many zeros and only two 1’s. Why is this good? Well, when we perform an operation of:

M^e (mod p)

it is more efficient to process with a zero in the exponent (e) value, than with a 1.

## CSD

With the Canonic Signed Digit (CSD) Representation of Integers, we can represent we can represent an integer (*n*) in the form:

and where we get:

and where *L_n *can be positive and negative integers. In normal binary, a value of 11 would be:

This could be represented in a CSD form as:

and which is [1 0 -1 0 -1].

Let’s say we have a value of 48,153, and want four values. These could be {(3,-3}), (-7,7),(-1, 1)}, and could represent as:

and repsented as:

`[3 0 0 0 -1 0 0 0 0 1 0 0 0 0 -7]`

NAF has the advantage that the Hamming weight between values is minimal, and where in a normal binary format, we will have around half of the bits set to 1 and half the bits set to 0. With NAF, this the number of 1s can drop to around one-third. Having so many zeros, allows efficent adding and subtraction. In cryptography, it reduces the number of multiplications requires for exponentation, as zero values are quicker than one values.

## Coding

Some sample code is [here]:

`package main`

import (

"fmt"

"math/big"

"github.com/cloudflare/circl/math"

"crypto/rand"

"strconv"

"os"

)

func reverseInts(input []int32) []int32 {

if len(input) == 0 {

return input

}

return append(reverseInts(input[1:]), input[0])

}

func main() {

w:=2

bits:=128

argCount := len(os.Args[1:])

if argCount > 0 {

w,_ = strconv.Atoi(os.Args[1])

}

if argCount > 1 {

bits,_ = strconv.Atoi(os.Args[2])

}

var max big.Int

max.SetInt64(1)

max.Lsh(&max, uint(bits))

x, _ := rand.Int(rand.Reader, &max)

L := math.OmegaNAF(x, uint(w))

var y big.Int

for i := len(L) - 1; i >= 0; i-- {

y.Add(&y, &y).Add(&y, big.NewInt(int64(L[i])))

}

L=reverseInts(L)

got := &y

fmt.Printf("\nNumber of bits=%d\nw=%d\nx=%s\n%v\nChecking: %v\n",bits,w,x, L,got)

}

For *w*=2, we have {0, (1, -1)} for values. For a value of 11458119973769479092371685680579383142, we get [here]:

`Number of bits=128`

w=2

x=11458119973769479092371685680579383142

[1 0 0 0 1 0 1 0 0 0 0 -1 0 -1 0 0 0 0 0 1 0 0 0 -1 0 0 -1 0 0 1 0 1 0 0 0 0 1 0 0 -1 0 0 0 1 0 -1 0 0 -1 0 0 0 0 0 1 0 -1 0 0 0 -1 0 1 0 -1 0 0 0 1 0 0 0 -1 0 1 0 1 0 1 0 -1 0 0 -1 0 -1 0 0 -1 0 1 0 0 0 1 0 0 0 -1 0 -1 0 -1 0 -1 0 0 0 1 0 0 1 0 0 0 0 -1 0 -1 0 1 0 -1 0]

Checking: 11458119973769479092371685680579383142

For *w*=3, we get three values. In this case we have {0, (1, -1), (3, 3)} and for a value of 3640439295394695171, we get [here]:

`Number of bits=64`

w=3

x=3640439295394695171

[1 0 0 0 -3 0 0 -3 0 0 0 0 1 0 0 3 0 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 3 0 0 -3 0 0 0 0 3 0 0 0 0 0 0 -1 0 0 1 0 0 0 0 0 0 0 0 0 0 3]

Checking: 3640439295394695171

For *w*=5, we get three values. In this case we have {0, (1, -1), (-9, 9), (-13, 13), (-15, 15)} and for a value of 169187459747143294798673799909229736090, we get [here]:

`Number of bits=128`

w=5

x=169187459747143294798673799909229736090

[1 0 0 0 0 0 0 -1 0 0 0 0 9 0 0 0 0 1 0 0 0 0 9 0 0 0 0 0 -7 0 0 0 0 9 0 0 0 0 15 0 0 0 0 15 0 0 0 0 -7 0 0 0 0 13 0 0 0 0 0 0 0 3 0 0 0 0 9 0 0 0 0 -11 0 0 0 0 5 0 0 0 0 15 0 0 0 0 -13 0 0 0 0 1 0 0 0 0 -15 0 0 0 0 11 0 0 0 0 0 0 0 -13 0 0 0 0 0 3 0 0 0 0 1 0 0 0 0 0 13 0]

Checking: 169187459747143294798673799909229736090