Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic

Gashkov, S.B.; Gashkov, I.B.

Информация о цитировании статьи получена из Web of Science, Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 17 декабря 2018 г.

Авторы: Gashkov S.B., Gashkov I.B.
Журнал: Moscow University Mathematics Bulletin
Том: 73
Номер: 5
Год издания: 2018
Издательство: Allerton Press Inc.
Местоположение издательства: United States
Первая страница: 176
Последняя страница: 181
DOI: 10.3103/S0027132218050029
Аннотация: It was proved that the complexity of square root computation in the Galois field GF(3^s), s = 2^kr, is equal to O(M(2^k)M(r)k + M(r) log_2r) + 2^kkr^{1+o(1)}, where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3s) is equal to O(M(2^k)M(r)) and O(M(2^k)M(r)) + r^{1+o(1)}, respectively. If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2^kkr^{1+o(1)} and r^{1+o(1)} can be omitted. For M(n) one may take n log_2nψ(n) where ψ(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O_r (M (s)log_2s) = s(log_2s)^2ψ(s).
Добавил в систему: Гашков Сергей Борисович

	ИСТИНА	Войти в систему Регистрация
	ИПМех РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИПМех РАН

Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristicстатья

Прикрепленные файлы