On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic 2статья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 26 декабря 2015 г.
Аннотация:For the complexity of multiplication in a standard basis of the field GF(2n), where n = 2·3k, the upper bound 5n log3 n log2 log3 n + O(n log n) for multiplication complexity and an asymptotically 2.5 times greater bound for inversion complexity are obtained. As a consequence, for the complexity of multiplication of binary polynomials the upper bound (10 + o(1))N log3N log2 logN is valid.
The mentioned estimates are generalised to some other finite fields. Let
n = (p - 1)pk,
where p is a prime such that 2 is a primitive root modulo p, 2p-1 - 1 is not divided by p2. For a standard basis of the field GF(2n), we construct a multiplier of complexity (C+o(1))(n log n log log n) and an inverter of complexity O(log p)n log n log log n, where C≤10.