On the representation of finite fields

Abstract

Cisim elemanlarının gösterimi sonlu cisim aritmetik uygulamalarının performansı üzerinde büyük öneme sahiptir. Bu tezde, herhangi bir karakteristiğe sahip sonlu cisimlerde düşük çarpımsal karmaşıklığa sahip devre ihtiyacı için tasarlanan, gerekenden fazla eleman kullanan gösterimin değiştirilmiş versiyonu veriliyor. Bu gösterimi kullanarak bir çok değerin karmaşıklığını azaltıyoruz. Sonra, karakteristiği 2 olan sonlu cisimlerin gösterimlerine alternatif bir yol olması için Charlier ve Hermite polinomların kullanılmasını öneriyoruz. Bu gösterimlerde çarpma işleminin logaritmik alan karmaşıklığı ile yapılabildiğini gösteriyoruz. Charlier ve Hermite gösterimleri, hızlı modüler aritmetik yapmamıza ve başka gösterimler kullanılarak istenilen düzeyde az terimli indirgenemez polinom elde edilemediği durumlarda, iki, üç ve dört terimli indirgenemez polinomları bulabilmemize olanak sağlamaktadır. Bu gösterimler, NIST ve SEC standartlarında karakteristiği 2 olan cisimlerde kullanılması önerilen $GF(2^{283})$ ve $GF(2^{571})$ cisim genişlemeleri için optimal normal gösterim bulunmadığından oldukça ilginç sonuçlar vermektedir. Bunlara ek olarak, bazı cisim genişlemeleri için optimal normal gösterim olsa bile önerilen bu yeni gösterimlerin daha iyi alan karmaşıklığına sahip olduğunu gösteriyoruz.

The representation of field elements has a great impact on the performance of the finite field arithmetic. In this thesis, we give a modified version of redundant representation which works for any finite fields of arbitrary characteristics to design arithmetic circuits with small complexity. Using our modified redundant representation, we improve many of the complexity values. We then propose new representations as an alternative way to represent finite fields of characteristic two by using Charlier and Hermite polynomials. We show that multiplication in these representations can be achieved with subquadratic space complexity. Charlier and Hermite representations enable us to find binomial, trinomial or quadranomial irreducible polynomials which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. These representations are very interesting for the NIST and SEC recommended binary fields $GF(2^{283})$ and $GF(2^{571})$ since there is no optimal normal basis (ONB) for the corresponding extensions. It is also shown that in some cases the proposed representations have better space complexity even if there exists an ONB for the corresponding extension.