MOF: Mutual Opposite Form

German page Japanese page

MOF is a new canonical representation of signed binary strings, which can be computed not only right-to-left but also left-to-right.

Contents:

Motivation
MOF
wNAF
Window Methods on MOF
Compute MOF-representations for the random numbers d (0 < d < 1024 )

Motivation:

The most common method for computing exponentiation of random elements in Abelian groups are sliding window schemes, which enhance the efficiency of the binary method at the expense of some precomputation. In groups where inversion is easy (e.g. elliptic curves), signed representations of the exponent are meaningful because they decrease the amount of required precomputation. The asymptotic best signed method is wNAF, because it minimizes the precomputation effort whilst the non-zero density is nearly optimal. Unfortunately, wNAF can be computed only from the least significant bit, i.e. right-to-left. However, in connection with memory constraint devices left-to-right recoding schemes are by far more valuable.

In representation an integer d is expressed as d=sum(d_i 2ⁱ) where d_i is in T. For normal binary representations T={0,1} which causes an unique representation. If the set T is larger, i.e. we allow negative digits, one number can be expressed a few times.

decimal binary T=

181 = 1 0 1 1 0 1 0 1 {0,1}

= 1 -1 1 0 -1 1 -1 1 -1 {-1,0,1}

= 1 0 -1 0 -1 0 1 0 1 {-1,0,1}

Goals

Minimize #T.
For ECC applications each digit of T has to be precomputed which takes time and requires memory.
Minimize non-zero digits.
In multiplication or exponentaion algorithms non-zero digits require an extra operation. So the computation of many zero-digits is faster.

MOF:

MOF Definition
The mutual opposite form (MOF) is an signed binary string that satisfies the following properties:

the signs of adjacent non-zero bits (without considering 0 bits) are opposite, and
the most non-zero bit and the least non-zero bit are 1 and -1, respectively.

Example
Some zero bits are inserted between non-zero bits that have a mutual opposite sign. An example of MOF is 0 1 0 0 -1 0 1 0 0 0 -1 0 0 1 -1 0.
Converting Binary String to MOF
We show a simple and flexible conversion from n-bit binary string to (n+1)-bit MOF.

The crucial point is the following observation. The n-bit binary string d can be converted to a signed binary string by computing md = 2d - d, where - stands for a bitwise subtraction. Indeed, we convert d as follows:

2d = d_n-1 d_n-2 ... d_i-1 ... d₁ d₀

-d = d_n-1 ... d_i ... d₂ d₁ d₀

md = d_n-1 d_n-2-d_n-1 ... d_i-1-d_i ... d₁-d₂ d₀-d₁ -d₀

Algorithm: Left-to-Right Gerneration fom Binary to MOF

Input: a non-zero n-bit binary string d=d_n-1|d_n-2|...|d₁|d₀

Output: MOF md_n|...|md₁|md₀ of d

md_n <- d_n-1
for i = n - 1 down to 1 do

md_i <- d_i-1 - d_i

md₀ <- -d₀
return (md_n, md_n-1, ..., md₁, md₀)

Algorithm: Right-to-Left Gerneration fom Binary to MOF

Input: a non-zero n-bit binary string d=d_n-1|d_n-2|...|d₁|d₀

Output: MOF md_n|...|md₁|md₀ of d

md₀ <- -d₀
for i = 1 to n - 1 do

md_i <- d_i-1 - d_i

md_n <- d_n-1
return (md_n, md_n-1, ..., md₁, md₀)

Theorem
Every non-negative integer d has a representation as wMOF, which is unique except for the number of leading zeros.

wNAF

wNAF Definition
A sequence of signed digits is called wNAF iff the following three properties hold:

The most significant non-zero bit is positive.
Among any w consecutive digits, at most one is non-zero.
Each non-zero digit is odd and less than 2^w-1 in absolute value.

Algorithm: Generation of wNAF

Input: width w, an n-bit integer d

Output: wNAF sd_n|sd_n-1|...|sd₀ of d

i <- 0
while d >= 1 do

if d is even then

sd_i <- 0

else

sd_i <- d mods 2^w; d <- d - sd_i

d <- d/2; i <- i + 1

return (sd_n, sd_n-1, ..., sd₀)

The algorithm generates wNAF from the least significant bit, that is right-to-left generation again. The average density of non-zero bits is asymptotically 1/(w+1) for n -> infty, and the digit set equals T={+-1, +-3, ..., +-(2^w-1-1)} which seems to be minimal.

It seems impossible to compute wNAF left-to-right. That's the motivation to look for other solutions.

Window Methods on MOF:

In this section we show how to decrease the non-zero density of MOF by applying window methods on it. First we consider the right-to-left width w sliding window method which surprisingly yields the familiar wNAF. In contrast to previously known generation methods, the new one is carry-free, i.e. in each step the knowledge of at most w+1 consecutive input bits is sufficient.

Then we define the dual new class wMOF as the result of the analogue left-to-right width w sliding window method on MOF. This conversion leads to the first left-to-right signed recoding scheme for general width w.

The coherency is shown on the following picture:

Right-to-Left Case: wNAF
In order to describe the proposed scheme, we need the conversion table for width w. First, we define the conversions for MOF windows of length l, such that the first and the last bit is non-zero:

In addition, we have analogue conversions with all signs changed. To generate the complete table for width w, we have to consider all conversions of length l=2, 3, ..., w. If l < w holds, the window is filled with leading zeros.

Example: In the case of w=3, we use the following table for the right-to-left sliding window method:

Algorithm: Right-to-Left Generation from Binary to wNAF

Input: width w, an n-bit binary string d=d_n-1|d_n-2|...|d₁|d₀

Output: wNAF sd_n|sd_n-1|...|sd₀ of d

d_n+w-2 <- 0; d_n+w-3 <- 0; ...; d_n <- 0; d_-1 <- 0
i <- 0
while i <= n do

if d_i-1 = d_i then

sd_i <- 0; i <- i + 1

else {The MOF windows begins with a non-zero digit righthand}

(sd_i+w-1, ..., sd_i) <- Table_wSW(d_i+w-2 - d_i+w-1, d_i+w-3 - d_i+w-2, ..., d_i-1 - d_i)
i <- i + w

return (sd_n, sd_n-1, ..., sd₀)

Left-to-Right Case: wMOF
In order to describe the proposed scheme, we need the conversion table for width w. The conversions for MOF windows of length l, such that the first and the last bit is non-zero, are defined in exactly the same way as in the right-to-left case (see the table above and reflect the assignments). To generate the complete table for width w, we have to consider all conversions of length l=2, 3, ..., w as before. The only difference is that if l < w holds, the window is filled with closing zeros instead of leading ones. As an example, we construct the conversion table Table_4SW for width 4:
The table is complete due to the properties of MOF. Note that because of the equalities (* 1 -1) = (* 0 1), (* -1 1) = (* 0 -1) usually two different MOF-strings are converted to the same pattern. In an analogue way, Table_wSW is defined for general width w. In this case the digit set equals T = { +-1, +-3, ..., +-2^w-1-1 }, which is the same as for wNAF. Therefore, the scheme requires only 2^w-2 precomputed elements. The algorithm makes use of this table to generate wMOF left-to-right.
Algorithm: Left-to-Right Generation from Binary to wMOF

Input: width w, a non-zero n-bit binary string d=d_n-1|d_n-2|...|d₁|d₀

Output: wMOF sd_n|sd_n-1|...|sd₀ of d

d_-1 <- 0; d_n <- 0
i <- 0
while i >= w - 1 do

if d_i = d_i-1 then

sd_i <- 0; i <- i - 1

else {The MOF windows begins with a non-zero digit lefthand}

(sd_i, sd_i-1, ..., sd_i-w+1) <- Table_wSW(d_i-1 - d_i, d_i-2 - d_i-1, ..., d_i-w - d_i-w+1)
i <- i - w

if i >= 0 then

(sd_i, sd_i-1, ..., sd₀) <- Table_i+1SW(d_i-1 - d_i, d_i-2 - d_i-1, ..., d₀ - d₁, -d₀)

return (sd_n, sd_n-1, ..., sd₀)

Theorem
The average non-zero density of wMOF is asymptotically 1/(w+1) for n -> infty.

Compute MOF-representations for the random numbers d (0 < d < 1024 ):

This is a wMOF converter which compute MOF-representations for the random numbers d (0 < d < 1024 ) and output the answer. After that a left-to-right or right-to-left sliding window method can be applied.

(0 < d < 1024)

decimal		binary									T=
181	=		1	0	1	1	0	1	0	1	{0,1}
	=	1	-1	1	0	-1	1	-1	1	-1	{-1,0,1}
	=	1	0	-1	0	-1	0	1	0	1	{-1,0,1}

2d =	d_n-1	d_n-2	...	d_i-1	...	d₁	d₀
-d =		d_n-1	...	d_i	...	d₂	d₁	d₀

md =	d_n-1	d_n-2-d_n-1	...	d_i-1-d_i	...	d₁-d₂	d₀-d₁	-d₀