It is known that every positive integer n can be represented as a finite sum of the form n = ∑ a_i2~i, where a_i ∈ {0,1, -1} for all i, and no two consecutive a_i's are non-zero. Such sums are called nonadja-cent representations. Nonadjacent representations are useful in efficiently implementing elliptic curve arithmetic for cryptographic applications. In this paper, we investigate if other digit sets of the form {0,1, x}, where x is an integer, provide each positive integer with a nonadjacent representation. If a digit set has this property we call it a nonadjacent digit set (NADS). We present an algorithm to determine if {0, l,x} is a NADS; and if it is, we present an algorithm to efficiently determine the nonadjacent representation of any positive integer. We also present some necessary and sufficient conditions for {0,1, x} to be a NADS. These conditions are used to exhibit infinite families of integers x such that {0,1, x} is a NADS, as well as infinite families of x such that {0,1, x} is not a NADS.
展开▼
