W artykule omówiono optymalizację procesu poszukiwania nierozkładalnego wielomianu osadowego nad GF(2) zadanego, wysokiego stopnia poprzez wybór odpowiedniego punktu startowego i sposobu kolejkowania badanych wielomianów. Postawione tezy sprawdzono empirycznie oraz zilustrowano odpowiednimi przykładami.
Słowa kluczowe: ciała binarne, wielomiany nieprzywiedlne, wielomiany osadowe.
Abstract
This article addresses the problem of sedimentary irreducible polynomials over GF(2) search process optimization. Different queueing strategies and starting points were tested for optimality. Obtained results were empirically verified by computational experiments.
Keywords: binary fields, irreducible polynomials, sedimentary polynomials.
1. WSTĘP Rozszerzenia skończone ciała binarnego charakteryzują się bardzo szerokim zakresem potencjalnych zastosowań, spośród których w szczególności wymienić należy między innymi kryptografię, algebraiczną teorię kodów, bądź generację liczb pseudolosowych. Z tego względu optymalizacja procesu konstrukcji skończonych ciał binarnych o szczególnych postaciach w dalszym ciągu pozostaje problemem otwartym o istotnym znaczeniu praktycznym [3]. W celu rozwiązania sformułowanego powyżej problemu można zastosować różne podejścia, polegające między innymi na zmniejszaniu złożoności wykorzystywanych algorytmów, coraz wydajniejszym ich implementowaniu, bądź wykorzystaniu właściwości szczególnych postaci wielomianów do ich efektywnego poszukiwania. W niniejszej pracy zaprezentowano wspomniane wykorzystanie własności szczególnych nierozkładalnych wielomianów osadowych celem zmniejszenia złożoności procesu konstrukcji odpowiadających im ciał skończonych. Wzrost wydajności wynikający z zastosowanego podejścia potwierdzono zarówno teoretycznie poprzez wyznaczenie liczby wielomianów kandydujących dla różnych metod, jak i empirycznie wykonując odpowiedni eksperyment obliczeniowy. W obu przypadkach wyraźnie widać odpowiedni spadek średniego czasu znalezienia nierozkładalnego wielomianu osadowego. 2. PRZEPROWADZONE PRACE Definicja 1 Nieprzywiedlnym wielomianem osadowym nad ciałem GF(2) nazywamy wielomian postaci 𝑥𝑛 + 𝑔(𝑥), gdzie 𝑔(𝑥) posiada stopień bliski liczbie 𝑙𝑜𝑔2(𝑛). Definicja 2 Stopniem wewnętrznym wielomianu osadowego postaci 𝑥𝑛 + 𝑔(𝑥) nazywamy stopień 𝑔(𝑥) i oznaczamy jako deg(𝑔(𝑥)). W ramach dotychczas przeprowadzonych badań wielomianów osadowych obalono sławną hipotezę Gao i von zur Gathena [2] dotyczącą szybkości wzrostu stopnia wewnętrznego wielomianu osadowego poprzez wyznacze [...]


Metoda płatności: Płatności elektroniczne (karta kredytowa, przelew elektroniczny) | |
Dostęp do publikacji - jednorazowy (płatność elektroniczna) - tylko 6,00 zł
(płacisz 45% mniej niż przy płatności SMS) |
|
Dostęp do Wirtualnej Czytelni - archiwalne e-zeszyty czasopisma - 1h tylko 24.60 zł | |
Dostęp do Wirtualnej Czytelni - archiwalne e-zeszyty czasopisma - 4h tylko 43.05 zł | |
Dostęp do Wirtualnej Czytelni - archiwalne e-zeszyty czasopisma - 12h tylko 73.80 zł | |
Metoda płatności: SMS Premium | |
Dostęp do publikacji - jednorazowy (płatność SMS'em) - 11,07 zł brutto (9,00 zł + VAT) | |
Prenumerata
Bibliografia
[1] Augustynowicz Paweł, Paszkiewicz Andrzej. 2017. "Empiryczna
weryfikacja hipotezy o stopniu wewnętrznym osadowych
wielomianów nieprzywiedlnych nad GF(2)", Przegląd
Telekomunikacyjny Wiadomości Telekomunikacyjne.
8-9: 799-802.
[2] Gao Shuhong, Howell Jason, Panario Daniel. 1999. "Irreducible
polynomials of given forms. Finite fields: theory,
applications, and algorithms", Contemporary Mathematics:
43-54
[3] Gao Shuhong, Panario Daniel. 1997. "Tests and Constructions
of Irreducible Polynomials over Finite Fields", Foundations
of Computational Mathematics: 346-361
[4] Paszkiewicz Andrzej. 2009. "O pewnej hipotezie dotyczącej
wielomianów nieprzywiedlnych nad GF(2)", Matematyka
Stosowana, 10:39- 49
[5] Swan Richard. 1962. "Factorization of polynomials over finite
fields", Pacific J. Math. 12:1099-1066.