Классификация тернарных квазиканонических систем счисления в мнимых квадратичных полях и их приложение
Богданов П.С., Чернов В.М.

Аннотация:

В работе рассматриваются все возможные тернарные квазиканонические системы счисления в мнимых квадратичных полях. Для представления целых алгебраических чисел мнимых квадратичных полей в указанных системах счисления используется алгоритм, основанный на делении с остатком. Кроме того, синтезируются алгоритмы реализации основных арифметических операций над числами в тернарных системах счисления кольца целых чисел Эйзенштейна. Рассматривается метод быстрого безошибочного вычисления дискретной циклической свёртки.

Ключевые слова :
каноническая система счисления, деление с остатком по норме, квазиканоническая система счисления, мнимые квадратичные поля.

Литература:

  1. Давыдов, Е.С. Наименьшие группы чисел для образования натуральных рядов / Е.С. Давыдов. – Питербург: Типо – литография В.В. Комарова, 1903.  – 39 с.
  2. Слудский, Ф.А. О свойствах степеней двух и трёх / Ф.А. Слудский // Математический сборник. – 1870. – Т. 4, Вып. 3.  – С. 171-175.
  3. Кушнеров, А.Троичная цифровая техника. Ретроспектива и современность / А. Кушнеров. – Израиль: Университет им. Бен-Гуриона Беэр-Шева, 2005. – 15 с.
  4. Кнут, Д. Искусство программирования. Том 2. Получисленные алгоритмы / Д. Кнут. – М.: Мир, 1977. – 727 с.
  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. Боревич, З.И. Теория чисел / З.И. Боревич, И.Р. Шафаревич. – М.: Наука, 1985. – 504 с.
  10. Чернов, В.М. Арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований / В.М. Чернов. – М.: Физматлит, 2007. – 264 с.
  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. Чернов, В.М. Синтез параллельных алгоритмов преобразований Фурье–Галуа в прямых суммах конечных колец / В.М. Чернов // Известия Самарского научного центра Российской академии наук. – 2000. – Вып. 1. – С. 128-134.
  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 Science. – 1997. – N 1296 – P. 621–628.

© 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) 332-56-22, Fax: +7 (846) 332-56-20