Fast Algorithms for Solving Equations of Degree <=4 in Some Finite Fieldsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 29 сентября 2021 г.
Аннотация:It is possible to solve equations of degree ⩽4⩽4 in some bases of the field GF(ps)GF(ps), where p>3p>3, s=2krs=2kr, k→∞k→∞, r=±1(mod 6)r=±1(mod 6), and p,r=O(1)p,r=O(1) with the bit complexityOr(M(2k)kM(r)M(⌈log2p)⌉)=Or,p(M(s)log2s),Or(M(2k)kM(r)M(⌈log2p)⌉)=Or,p(M(s)log2s),where M(n)M(n) is the complexity of polynomial multiplication. In a normal basis of the fields GF(3s)GF(3s), s=±1(mod 6)s=±1(mod 6), all roots may be found with the bit complexity O(M(GF(3s))log2s)O(M(GF(3s))log2s), where M(GF(q))M(GF(q)) is the complexity of multiplication in the field GF(q)GF(q). For normal bases in the fields GF(2s)GF(2s), where s=2rs=2r, r≠0(mod 3)r≠0(mod 3), the bit complexity is O(M(GF(2s))log2s)O(M(GF(2s))log2s).