On the representation of finite fields
Sonlu cisimlerin gösterimi üzerine
- Tez No: 284707
- Danışmanlar: PROF. DR. FERRUH ÖZBUDAK
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Matematik, Computer Engineering and Computer Science and Control, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2010
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Uygulamalı Matematik Enstitüsü
- Ana Bilim Dalı: Kriptografi Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 81
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Free storage basis conversion over extension field
Cisim genişlemesi üzerinde serbest depolama baz dönüşümü
NDANGANG HAROLD YAMPA
Yüksek Lisans
İngilizce
2014
MatematikOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
PROF. DR. ERSAN AKYILDIZ
- Results on the multiplication in finite fields of characteristic three using modified polynomial representation and normal elements in binary fields
Değiştirilmiş polinom gösterimi kullanılarak karakteristiği üç olan sonlu cisimlerde çarpma üzerine ve ikilik cisimlerde normal elemanlar üzerine sonuçlar
CANAN ÖZEL
Doktora
İngilizce
2013
MatematikOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
PROF. DR. FERRUH ÖZBUDAK
YRD. DOÇ. DR. SEDAT AKLEYLEK
- Some results on APN functions and weakly regular bent functions over finite fields
Sonlu cisimler üzerinde APN ve zayıf düzenli bükük fonksiyonlara ilişkin bazı sonuçlar
İLKSEN ACUNALP ERLEBLEBİCİ
Doktora
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
DOÇ. DR. OĞUZ YAYLA
- On lower degree bounds for vector invariants over finite fields
Sonlu cisimler üzerindeki vektör değişmezlerinin derecelerinin alt sınırları üzerine
UĞUR MADRAN
Yüksek Lisans
İngilizce
2000
Matematikİhsan Doğramacı Bilkent ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. SERGUES A. STEPANOV