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

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

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



Вестн. Моск. ун-та. Сер. 1. Матем., мех.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2018, номер 5, страницы 8–14 (Mi vmumm569)  

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

Математика

Быстрый алгоритм извлечения квадратных корней в некоторых конечных полях нечетной характеристики

С. Б. Гашковa, И. Б. Гашковb

a Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
b Университет г. Карлстад, Швеция

Аннотация: Доказано, что извлечь квадратный корень в поле $GF(3^s),$ $s=2^kr,$ можно с битовой сложностью $O(M(2^k)M(r)k+M(r)\log_2 r)+2^k kr^{1+o(1)},$ где $M(n)$ – сложность умножения многочленов степени $n$ над полем характеристики $3.$ Умножение и деление в поле $GF(3^s)$ выполняются со сложностью $O(M(2^k)M(r))$ и $O(M(2^k)M(r))+r^{1+o(1)}$ соответственно. Если базис в поле $GF(3^r)$ определяется неприводимым биномом над $GF(3)$ или является оптимальным нормальным базисом, то слагаемые $2^k kr^{1+o(1)}$ и $r^{1+o(1)}$ можно опустить. В качестве $M(n)$ можно взять $n \log_2 n \psi(n) $, где $\psi(n)$ растет медленнее любой итерации логарифма. Если $k$ растет, а $r$ фиксировано, то все приведенные оценки имеют вид $O_r(M(s)\log_2 s)=s(\log_2 s)^2 \psi(s).$

Ключевые слова: конечные поля, извлечение квадратного корня, битовая (булева) сложность.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-01-00337
17-01-00485
Работа выполнена при финансовой поддержке РФФИ, проекты № 18-01-00337 и 17-01-00485.


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

Англоязычная версия:
Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2018, 73:5, 176–181

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

Тип публикации: Статья
УДК: 519.95
Поступила в редакцию: 22.11.2017

Образец цитирования: С. Б. Гашков, И. Б. Гашков, “Быстрый алгоритм извлечения квадратных корней в некоторых конечных полях нечетной характеристики”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2018, № 5, 8–14; Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 73:5 (2018), 176–181

Цитирование в формате AMSBIB
\RBibitem{GasGas18}
\by С.~Б.~Гашков, И.~Б.~Гашков
\paper Быстрый алгоритм извлечения квадратных корней в некоторых конечных полях нечетной характеристики
\jour Вестн. Моск. ун-та. Сер.~1. Матем., мех.
\yr 2018
\issue 5
\pages 8--14
\mathnet{http://mi.mathnet.ru/vmumm569}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3878529}
\zmath{https://zbmath.org/?q=an:07023559}
\transl
\jour Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin
\yr 2018
\vol 73
\issue 5
\pages 176--181
\crossref{https://doi.org/10.3103/S0027132218050029}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000450666000002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85056086358}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vmumm569
  • http://mi.mathnet.ru/rus/vmumm/y2018/i5/p8

    ОТПРАВИТЬ: 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. С. Б. Гашков, “Быстрые алгоритмы решения уравнений степени не выше четвертой в некоторых конечных полях”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2021, № 3, 22–31  mathnet
  • Просмотров:
    Эта страница:128
    Полный текст:30
    Литература:5
    Первая стр.:10
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021