Mathematics – Number Theory
Scientific paper
2010-09-02
Mathematics
Number Theory
Scientific paper
We consider digital expansions to the base of $\tau$, where $\tau$ is an algebraic integer. For a $w \geq 2$, the set of admissible digits consists of 0 and one representative of every residue class modulo $\tau^w$ which is not divisible by $\tau$. The resulting redundancy is avoided by imposing the width $w$-NAF condition, i.e., in an expansion every block of $w$ consecutive digits contains at most one non-zero digit. Such constructs can be efficiently used in elliptic curve cryptography in conjunction with Koblitz curves. The present work deals with analysing the number of occurrences of a fixed non-zero digit. In the general setting, we study all $w$-NAFs of given length of the expansion. We give an explicit expression for the expectation and the variance of the occurrence of such a digit in all expansions. Further a central limit theorem is proved. In the case of an imaginary quadratic $\tau$ and the digit set of minimal norm representatives, the analysis is much more refined: We give an asymptotic formula for the number of occurrence of a digit in the $w$-NAFs of all elements of $\Z[\tau]$ in some region (e.g.\ a disc). The main term coincides with the full block length analysis, but a periodic fluctuation in the second order term is also exhibited. The proof follows Delange's method. We also show that in the case of imaginary quadratic $\tau$ and $w \geq 2$, the digit set of minimal norm representatives leads to $w$-NAFs for \emph{all} elements of $\Z[\tau]$. Additionally some properties of fundamental domain are stated.
Heuberger Clemens
Krenn Daniel
No associations
LandOfFree
Analysis of Width-$w$ Non-Adjacent Forms to Imaginary Quadratic Bases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Analysis of Width-$w$ Non-Adjacent Forms to Imaginary Quadratic Bases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of Width-$w$ Non-Adjacent Forms to Imaginary Quadratic Bases will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-376718