Minimal redundant digit expansions in the Gaussian integers (Q558126)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimal redundant digit expansions in the Gaussian integers |
scientific article |
Statements
Minimal redundant digit expansions in the Gaussian integers (English)
0 references
30 June 2005
0 references
Let \(q\geq 2\) be an integer. There are infinitely many ways to represent a given integer \(n\in {\mathbb N}\) in the form \[ n=\sum_{j=0}^l \varepsilon_j q^j,\quad l \in {\mathbb N},\;\varepsilon_j\in {\mathbb Z}. \] In cryptography, it is sometimes interesting to find a representation with a minimal `cost' (that is, such that \(\sum_{j=0}^l| \varepsilon_j| \) is minimal). \textit{C. Heuberger} and \textit{H. Prodinger} [Computing 66, No. 4, 377--393 (2001; Zbl 1030.11003)] have shown that knowing the digits \(\eta_0,\eta_1\) of the usual \(q\)-ary expansion \(n=\sum_{j=0}^L \eta_jq^j\) (\(0\leq \eta_j<q\)) is enough to decide what digit \(\varepsilon_0\) should be taken to obtain such a minimal representation of \(n\). This provides an easy algorithm to produce a representation of minimal cost for a given integer \(n\). In the paper under review, the corresponding problem is investigated for so-called canonical number systems in the ring of Gaussian integers. The main result shows that the situation becomes very different. Indeed, given an arbitrary positive integer \(L\), the author constructs two Gaussian integers \(\alpha,\alpha'\) with the following properties: The `usual' representations of \(\alpha\) and \(\alpha'\) coincide in the first \(L\) digits, while for all pairs of strings \((\varepsilon_0,\dots \varepsilon_s)\) and \((\varepsilon'_0,\dots \varepsilon'_{s'})\) corresponding to minimal cost representations of \(\alpha\) and \(\alpha'\), respectively, we have \(\varepsilon_0 \not=\varepsilon'_0\). This proves that there is no algorithm, in the vein of the one mentioned above, for finding the minimal representation for canonical number systems in Gaussian integers.
0 references
minimal redundant expansions
0 references
Gaussian integers
0 references
0 references