(25) 25 * << * >> * Русский * English * Содержание * Все выпуски

АЛГОРИТМ БЕЗОШИБОЧНОГО ВЫЧИСЛЕНИЯ СВЕРТКИ В РАСШИРЕНИЯХ КОНЕЧНЫХ ПОЛЕЙ
А.Н. Калугин
Самарский государственный аэрокосмический университет

 PDF, 447 kB

Страницы: 134-140.

Язык статьи: Русский.

Аннотация:
В работе рассматривается алгоритм безошибочного вычисления дискретной круговой свертки с помощью теоретико–числовых преобразований в системе остаточных классов при альтернативной факторизации составного модуля в расширении кольца классов вычетов. Дополнительный вычислительный выигрыш обеспечивается за счет представления входных данных и параметров преобразования в канонических системах счисления.

Keywords:
error-free calculation, finite field, discrete circular convolution, numbertheoretic transformations, factorization, canonical number system

Citation:
Kalugin AN. An algorithm for error-free calculation of convolution in extensions of finite fields. Computer Optics 2003; 25: 134-140.

Литература:

  1. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си // М.: Издательство ТРИУМФ, 2002. 816 с.
  2. Handbook of Applied Cryptography // by A. Menezes, P. Van Oorschot, and S. Vanstone. CRC Press, 1996.
  3. Chernov V.M., Pershina M.V. «Error-free» calculation of the convolution using generalized Mersenne and Fermat transforms over algebraic fields // In: G. Sommer, K. Daniilidis, J. Pauli (Eds) “Computer Analysis of Image and Pattern”. (CAIP'97). Springer, LNCS 1296. Р. 621-628
  4. Чернов В.М. Синтез параллельных алгоритмов преобразований Фурье-Галуа в прямых суммах конечных колец // Известия Самарского научного центра Российской Академии Наук, 2000. Вып.1. №2. С. 128-134.
  5. Kátai I., Kovács B. Canonical number systems in imaginary quadratic fields // Acta Mathematica Academiae Scientarium Hungaricae. T. 37 (1-3), 1981. Р. 159-164.
  6. Kátai I., Szabo J. Canonical number systems for complex integers // Acta Sci.Math.(Szeged), 37. 1975. Р. 255-260.
  7. Thuswardner J. Elementary properties of canonical number systems in quadratic fields // G.E. Bergum et al. (eds.), Applications of Fibonacci Numbers, Volume 7. Р. 405-415.
  8. Кнут Д. Искусство программирования // Получисленные алгоритмы, 3-е изд. М.: Изд. Дом «Вильямс», 2001. Т.2. 832 с.
  9. Kovács A. Generalized binary number systems // Annales Univ. Sci. Budapest, Sect. Comp. 20. 2001. Р. 195-206.
  10. Чернов В.М. Неоднозначность разложения на множители, канонические системы счисления в квадратичных кольцах и параллельные алгоритмы вычисления свертки // Доклады 11-й конференции Математические методы распознавания образов (ММРО-11), М..: 2003. С. 212-215.

© 2009, IPSI RAS
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: journal@computeroptics.ru; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20