|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
О сложности и глубине булевых схем для умножения и инвертирования в некоторых полях GF(2^n)статья
Статья опубликована в журнале из списка RSCI Web of Science
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 4 февраля 2014 г.
- Авторы: Гашков С.Б., Сергеев И.С.
- Журнал: Вестник Московского университета. Серия 1: Математика. Механика
- Номер: 4
- Год издания: 2009
- Издательство: Изд-во Моск. ун-та
- Местоположение издательства: М.
- Первая страница: 3
- Последняя страница: 7
- DOI: 10.3103/S0027132209040019
- Аннотация: При n =(p-1)p^k, где p такое простое, что 2 - первообразный корень по модулю p, 2^{p-1}-1 не кратно p^2, для стандартного базиса в поле GF(2^n) получены оценки сложности мультиплера O(log log p)nlog n loglog_p n и инвертора O(log p loglog p)nlog n loglog_p n. В частности, при p=3 получена оценка сложности умножения (45/8)nlog_3 n log_2log_3 n + O(nlog n) и оценка сложности инвертирования, которая больше указанной асимптотически в 2,5 раза.
- Добавил в систему: Сергеев Игорь Сергеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Краткий текст | Gashkov-Sergeev2009ComplexityAndDepthOfBoolean.pdf | 1,1 МБ | 31 августа 2019 [gashkov] | |
| 2. | Полный текст | Vestnik2009.pdf | 227,8 КБ | 12 января 2018 [isserg] |