|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
О сложности и глубине булевых схем для умножения и инвертирования в конечных полях характеристики 2статья
Статья опубликована в журнале из списка RSCI Web of Science
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из перечня ВАК
Дата последнего поиска статьи во внешних источниках: 4 февраля 2014 г.
- Авторы: Гашков С.Б., Сергеев И.С.
- Журнал: Дискретная математика
- Том: 25
- Номер: 1
- Год издания: 2013
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Первая страница: 3
- Последняя страница: 32
- DOI: 10.1515/dma-2013-001
- Аннотация: Для сложности умножения в стандартном базисе поля GF(2^n), где n=2*3^k, получены оценка сложности умножения 5n log_3 n log_2 log_3 n + O(n log n) и оценка сложности инвертирования, которая больше указанной асимптотически в 2,5 раза. Как следствие, для сложности умножения двоичных многочленов cтепени N справедлива верхняя оценка (10+o(1))N log_3 N log_2 log N. Указанные оценки обобщаются на случай других конечных полей.
- Добавил в систему: Сергеев Игорь Сергеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | dm1218.pdf | 283,4 КБ | 10 ноября 2016 [isserg] |