Wyniki 1-4 spośród 4 dla zapytania: authorDesc:"Paweł Augustynowicz"

DOBÓR FUNKCJI SKRÓTU SPEŁNIAJĄCYCH WYMAGANIA SPRZĘTOWEJ IMPLEMENTACJI FILTRU BLOOMA DOI:


  1. WPROWADZENIE Filtr Blooma jest probabilistyczną strukturą danych zaprezentowaną po raz pierwsze w roku 1970 przez B.H. Blooma, która pozwala na szybkie sprawdzenie, czy dany element występuje w zadanym zbiorze [2]. Sprawdzenie to jest jednak obarczone pewnym prawdopodobieństwem wystąpienia błędnej odpowiedzi pozytywnej (ang. false positive), które należy należy utrzymywać na możliwie niskim poziomie. Ze względu na pomysłową konstrukcję oraz małą złożoność pamięciową filtry Blooma są szeroko stosowane w różnych dziedzinach, między innymi w systemach ratingowych adresów IP, antywirusach, analizie tekstowej, sprawdzaniu pisowni i systemach baz danych [2,4,5,6]. Formalnie, filtr Blooma można reprezentować, jako tablicę 𝑚 bitów, które początkowo ustawiony są na wartość "0". Dla każdego elementu ze zbioru danych wejściowych [...]

EMPIRYCZNA WERYFIKACJA HIPOTEZY O STOPNIU WEWNĘTRZNYM OSADOWYCH WIELOMIANÓW NIEPRZYWIEDLNYCH NAD GF(2) DOI:10.15199/59.2017.8-9.33


  Zakres stosowania teorii dotyczącej wielomianów nieprzywiedlnych nad ciałami skończonymi jest bardzo szeroki. Znajdują zastosowanie między innymi w kryptografii, teorii kodów oraz technikach przetwarzania równoległego. W związku z powyższym efektywne techniki poszukiwania tychże wielomianów nierozkładalnych pozostają w kręgu zainteresowania matematyków i inżynierów z całego świata o czym świadczą liczne eksperymenty obliczeniowe [3][4]. Ze względu na szczególnie dobre właściwości implementacyjne zarówno w zastosowaniach sprzętowych, jak i programowych poszukuje się tylko pewnych postaci wielomianów nieprzywiedlnych, takich jak: trójmiany, wielomiany osadowe, bądź wielomiany, dla których istnieją bazy normalne. W rozpatrywanym przypadku ciał skończonych o charakterystyce 2 nie dla każdego stopnia istnieje trójmian nierozkładalny, bądź wielomian, dla którego jesteśmy w stanie przejść do bazy normalnej. Stąd też weryfikacja hipotez dotyczących sposobów efektywnego poszukiwania nieprzywiedlnych wielomianów osadowych, które istnieją dla każdego stopnia, wydaje się mieć znaczenie podstawowe. 2. PODSTAWY MATEMATYCZNE Definicja 1 Wielomianem osadowym nad ciałem binarnych GF(2) nazywamy wielomian postaci 𝑥𝑛 + 𝑔(𝑥), gdzie 𝑔(𝑥) posiada stopień bliski liczbie 𝑙𝑜𝑔2(𝑛). [2] Definicja 2 Stopniem wewnętrznym wielomianu osadowego postaci 𝑥𝑛 + 𝑔(𝑥) nazywamy stopień 𝑔(𝑥) i oznaczamy jako 𝑑𝑒𝑔(𝑔(𝑥)). Ze względu na ścisłe powiązanie stopnia wewnętrznego wielomianu osadowego zarówno z metodami jego efektywnego wyznaczania jak i złożonością tworzonych na podstawie tego wielomianu arytmetyk właściwość ta okazała się mieć znaczenie podstawowe. W szczególności już w 1996 zostały przebadane wszystkie wielomiany osadowe do stopnia 2000 i na tej podstawie została sformułowana następu[...]

O TRÓJMIANACH NIEROZKŁADALNYCH NAD GF(2) TOWARZYSZĄCYCH WIELOMIANOM POSTACI x2.3l+x3l+1 DOI:10.15199/59.2018.8-9.48


  1. WSTĘP Wielomiany nierozkładalne w naturalny sposób pojawiają się przy omawianiu struktury algebraicznej ciał skończonych [5]. W teorii kodowania [3], [4], [10] stanowią one podstawowy element konstrukcji metod wykrywania błędów i ich korekcji w kanałach telekomunikacyjnych. Występują też często w kryptografii [7]. Wiele popularnych dziś i powszechnie dostępnych przez Internet usług teleinformatycznych [12], nie mogłoby być realizowanych bez wykorzystania arytmetyki modularnej opartej na wielomianach nierozkładalnych. Skala wykorzystania kryptografii i ilość świadczonych na jej bazie usług sieciowych jest tak ogromna, że oprócz oczywistego wymagania na bezpieczeństwo algorytmów kryptograficznych przywiązuje się wielką wagę do ich szybkości. Z tego powodu m.in. w rozwiązaniach kryptograficznych do realizacji arytmetyki wykorzystuje się wielomiany binarne o małej liczbie niezerowych współczynników zwane krótkimi. Najczęściej są to trójmiany a jeżeli takich nie ma wówczas stosuje się pięciomiany (odpowiednio trzy lub pięć niezerowych współczynników) albo wielomiany osadowe, w których liczba niezerowych współczynników zależy logarytmicznie od stopnia wielomianu [1]. W [8] analizowana była klasa wielomianów nierozkładalnych nad ciałem GF(2) postaci 𝑋2𝑛 + 𝑋𝑛 + 1. Jedynymi wartościami 𝑛, dla których wielomiany te są nierozkładalne nad GF(2) są liczby postaci 𝑛 = 2 ∙ 3𝑙 . Interesującym jest pytanie jakie jeszcze inne wielomiany stopnia 𝑛 = 2 ∙ 3𝑙 są nierozkładalne nad GF(2). W cytowanej pracy [8] przedstawiono pełną listę takich wielomianów dla liczb naturalnych 𝑙 ≤ 9. W niniejszym artykule uzupełniamy tę listę o wartości 10 ≤ 𝑙 ≤ 13. Poczynione obserwacje pozwalają wskazać 9 nieskończonych klas wielomianów nierozkładalnych nad GF(2), które mają stopień 𝑛 = 2 ∙ 3𝑙 . 2. PRZEPROWADZONE BADAN[...]

OPTYMALIZACJA PROCESU POSZUKIWANIA NIEROZKŁADALNYCH WIELOMIANÓW OSADOWYCH DOI:10.15199/59.2018.8-9.51


  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[...]

 Strona 1