Results on complexity of multiplication over finite fields

Abstract

Üzerinde çalışılan cismin eleman sayısı olan $q$, 2 veya 3 olmak üzere, $n$ ve $/ell$ pozitif tamsayı, $f(x)$ indirgenemezpolinom ve $/ell deg(f(x))<2n -1 $ olsun. Bu tezde $/F_q$ üzerine $n$-terimli poinomların mod $f(x)^/ell$ indirgemesine göre çarpım karmaşıklığı üzerine üst sınırlar elde edildi. Bu üst sınır Çinli Kalan Teoreminde daha iyi modülüs polinomları seçilmesine olanak tanıdı. Boylece $/F_q$ üzerine küçük dereceli polinom çarpımları için literarürde olan en iyi sonuçlardan daha iyi sonuçlar geliştirildi. Ek olarak belirli $n$ ve $q$ için $/mu_q(n)$ olan sonlu cisim çarpma karmaşıklığı üzerinde gelişmeler elde edildi. Burada, sınıf cisimlerinde değerlendirme yerine lokal genişlemeler kullanarak sınırlar üzerinde optimizasyonlar elde edildi. Belirli $q$ ve $n$ değerleri olan $q=2,3,4$ ve $2/leq n/leq 18$ için $/F_{q^n}$'de geliştirilmiş çarpmalar elde edildi.

Let n and ? be positive integers and f(x) be an irreducible polynomial over /Fq such that ?l deg(f(x))<2n-1, where q is 2 or 3. We obtain an effective upper bound for the multiplication complexity of n-term polynomials modulo f(x)? This upper bound allows a better selection of the moduli when Chinese Remainder Theorem is used for polynomial multiplication over Fq We give improved formulae to multiply polynomials of small degree over Fq. In particular we improve the best known multiplication complexities over $/F_q$ in the literature in some cases. Moreover, we present a method for multiplication in finite fieldsimproving finite field multiplication complexity $/mu_q(n)$ for certain values of $q$ and $n$. We use local expansions, the lengths of which are further parameters that can be used to optimize the bounds on the bilinear complexity, instead of evaluation into residue class field. We show that we obtain improved bounds for multiplication in $/F_{q^n}$ for certain values of $q$ and $n$ where $2/leq n /leq 18$ and $q=2,3,4$.