Дискретная математика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискрет. матем., 2000, том 12, выпуск 3, страницы 124–153 (Mi dm340)  

Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

Замечания о быстром умножении многочленов, преобразовании Фурье и Хартли

С. Б. Гашков


Аннотация: Предложен быстрый алгоритм умножения действительных многочленов без использования комплексных чисел и быстрого преобразования Фурье. Эффективность этого алгоритма сравнивается с эффективностью алгоритма умножения, основанного на применении дискретного преобразования Хартли. Показано, что сложность преобразования Хартли совпадает с точностью до линейного слагаемого со сложностью преобразования Фурье, однако применение преобразования Хартли приводит к более эффективному алгоритму умножения. Приведены аналоги упомянутых результатов для конечных полей. Показано, что в некоторых случаях мультипликативные константы в оценках сложности умножения многочленов и преобразований Фурье и Хартли над конечными полями меньше, чем аналогичные константы в случае поля действительных чисел.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 99–01–01175, и ФЦП “Интеграция”, проект 473.

DOI: https://doi.org/10.4213/dm340

Полный текст: PDF файл (2522 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Discrete Mathematics and Applications, 2000, 10:5, 499–528

Реферативные базы данных:

УДК: 519.7
Статья поступила: 22.12.1999

Образец цитирования: С. Б. Гашков, “Замечания о быстром умножении многочленов, преобразовании Фурье и Хартли”, Дискрет. матем., 12:3 (2000), 124–153; Discrete Math. Appl., 10:5 (2000), 499–528

Цитирование в формате AMSBIB
\RBibitem{Gas00}
\by С.~Б.~Гашков
\paper Замечания о~быстром умножении многочленов, преобразовании Фурье и Хартли
\jour Дискрет. матем.
\yr 2000
\vol 12
\issue 3
\pages 124--153
\mathnet{http://mi.mathnet.ru/dm340}
\crossref{https://doi.org/10.4213/dm340}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1810959}
\zmath{https://zbmath.org/?q=an:1001.11060}
\transl
\jour Discrete Math. Appl.
\yr 2000
\vol 10
\issue 5
\pages 499--528


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm340
  • https://doi.org/10.4213/dm340
  • http://mi.mathnet.ru/rus/dm/v12/i3/p124

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Gashkov S.B., Gashkov I.B., “Some Remarks on Testing Irreducibility of Polynomials and Normality of Bases in Finite Fields”, Fundamenta Informaticae, 104:3 (2010), 227–238  mathscinet  zmath  isi  elib
    2. С. Б. Гашков, И. С. Сергеев, “Сложность вычислений в конечных полях”, Фундамент. и прикл. матем., 17:4 (2012), 95–131  mathnet; S. B. Gashkov, I. S. Sergeev, “Complexity of computation in finite fields”, J. Math. Sci., 191:5 (2013), 661–685  crossref
    3. Бурцев А.А., Гашков С.Б., “О схемах для арифметики в конечных полях”, Труды московского физико-технического института, 2012, 15–22  elib
    4. Gashkov S. Frolov A. Sergeev I., “Arithmetic in Finite Fields Supporting Type-2 Or Type-3 Optimal Normal Bases”, Dependability Engineering and Complex Systems, Advances in Intelligent Systems and Computing, 470, ed. Zamojski W. Mazurkiewicz J. Sugier J. Walkowiak T. Kacprzyk J., Springer Int Publishing Ag, 2016, 157–168  crossref  isi  scopus
    5. С. Б. Гашков, И. С. Сергеев, “Умножение”, Чебышевский сб., 21:1 (2020), 101–134  mathnet  crossref
  • Дискретная математика
    Просмотров:
    Эта страница:1240
    Полный текст:462
    Литература:75
    Первая стр.:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021