Classification of ternary quasicanonical number systems in imaginary quadratic fields and their application
P. S. Bogdanov, V. M. Chernov

Full text of article: Russian language.

Abstract:
In this paper all possible ternary quasicanonical number system in imaginary quadratic fields are considered. For representation of algebraic integers of imaginary quadratic fields in the specified number systems an algorithm based on the division with remainder is used. In addition, the algorithms of the basic arithmetic operations in ternary number systems in the ring of Eisenstain integers are synthesized. Method of fast error-free cyclic convolution computation is considered.

Key words:
canonical numerical system, norm division with remainder, quasicanonical numerical system, imaginary quadratic fields.

References:

  1. Davydov, E.S. Minimal number groups for the formation of natural series / E.S. Davydov – Petersburg: Typo-lithography of V.V. Komarov, 1903. – 39 p. – (In Russian).
  2. Sludsky, F.A. On the properties of degrees of two and three / F. Sludskii // Mathematical Collection. – 1870. – Vol. 4, Issue. 3. – P. 171-175. – (In Russian).
  3. Kushnerov, A. Ternary digital equipment. Retrospective and modern age / A. Kushnerov – Israel Ben-Gurion University, Beersheba, 2005. – 15 p. – (In Russian).
  4. Knuth, D.E. The Art of Computer Programming. Vol. 2 Semi-numerical Algorithms / D.E. Knuth – Moscow: “Mir” Publisher, 1977. – 727 p. – (In Russian).
  5. Katai, I. Kanonische Zahlensysteme in der Theorie der Quadratischen Zahlen / I. Katai, B. Kovacs // Acta Sci. Math. (Szeged). – 1980. – Vol. 42 –P. 99-107.
  6. Katai, I. Canonical number systems in imaginary quadratic fields / I. Katai, B. Kovacs // Acta Math. Hungar. – 1981. – Vol. 37 – P. 159-164.
  7. Kovacs, B. Canonical number systems in algebraic number fields / B. Kovacs // Acta Math. Hungar. – 1981. – Vol. 37 – P. 405-407.
  8. Kovacs, A. Generalized binary number system / A. Kovacs // Annales Univ. Sci. Budapest, Sect. Comp. – 2001. – Vol. 20 – P. 195-206.
  9. Borevich, Z.I. Number theory / Z.I. Borevich, I.R. Shafarevich – Academic Press, 1986. – 434 p.
  10. Chernov, V.M. Arithmetical methods of synthesis  of fast algorithms of Discrete orthogonal Transforms / V.M. Chernov – Moscow.: "Fizmatlit" Publisher, 2007. – 264 p. – (In Russian).
  11. Solomyak, B. Dynamics of self-similar tilings / B. Solomyak // Ergodic Theory Dynam. Systems. – 1997. – Vol. 17, N 3. – P. 695-738.
  12. Schoenhage, A. Schnelle Multiplikation grosser Zahlen / A. Schoenhage, V. Strassen // Computing. – 1971. – Vol. 7. – P. 281-292.
  13. Fuerer, M. Faster integer multiplication / M. Fuerer // STOC Proceedings. – 2007. – P. 57-66.
  14. Chernov, V. Synthesis of parallel algorithms of Fourier-Galois transforms in direct sums of finite rings / V. Chernov // Proceedings of the Samara Scientific Center of Russian Academy of Sciences. – 2000. – Issue 1. – P. 128-134. – (In Russian).
  15. Chernov, V. «Error-free» calculation of the convolution using generalized Mersenne and Fermat transforms over algebraic fields / V. Chernov, M. Pershina // Computer Analysis of Image and Pattern (CAIP’97). Lectures Notes in Computer.

© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; e-mail: ko@smr.ru; Phones: +7 (846 2) 332-56-22, Fax: +7 (846 2) 332-56-20