Wyniki 1-10 spośród 14 dla zapytania: authorDesc:"Andrzej Paszkiewicz"

O kilku właściwościach trójmianów nierozkładalnych nad małymi ciałami liczbowymi

Czytaj za darmo! »

Trójmianami nazywamy wielomiany, które są kombinacją liniową o niezerowych współczynnikach dokładnie trzech jednomianów różnych stopni tej samej zmiennej. W niniejszym artykule ograniczymy się do rozważania trójmianów, których współczynniki są z ciał skończonych liczbowych o małej liczbie elementów: 2, 3, 5 i 7. Trójmian o współczynnikach z ciała skończonego GF(p), niedający się przedstawić w postaci iloczynu dwóch wielomianów niższego stopnia, niż on sam, o współczynnikach z tego samego ciała, nazywamy nierozkładalnym albo nieprzywiedlnym nad GF(p). Trójmiany nierozkładalne znajdują szerokie zastosowanie w teorii kodowania [1] i kryptografii [10], [4] do przyspieszania działań w arytmetyce modularnej wielomianów, w tym w zastosowaniach telekomunikacyjnych i teleinformatycznych[...]

Wielomiany nieprzywiedlne nad GF(2) Wyniki projektu badawczego


  Wielomiany o współczynnikach z ciała skończonego GF(p), niedające się przedstawić w postaci iloczynu dwóch wielomianów niższego stopnia niż on sam, o współczynnikach z tego samego ciała, nazywamy nierozkładalnymi albo nieprzywiedlnymi nad GF(p). Znajdują one szerokie zastosowanie w teorii kodowania [4] i kryptografii [10], [11], przede wszystkim do przyspieszania działań w arytmetyce resztowej wielomianów, zwanej inaczej modularną [12]. W zastosowaniach kryptograficznych - z uwagi na udogodnienia wynikające z reprezentacji współczynników wielomianów na pojedynczych bitach - wykorzystuje się wielomiany nierozkładalne nad ciałem dwuelementowym GF(2). Arytmetyka w ciałach GF(2n) jest stosowana najczęściej i studiowana od dawna. Doczekała się ona licznych usprawnień pod względem s[...]

Anomalie w rozkładzie statystycznym dużych liczb pierwszych o zadanym najmniejszym pierwiastku pierwotnym


  W pracach [9], [10], [6] przedstawiono wyniki teoretyczne dotyczące częstości liczb pierwszych o zadanych najmniejszych pierwiastkach pierwotnych. Przeprowadzono także wiele eksperymentów obliczeniowych, dotyczących częstości pierwiastków pierwotnych modulo liczba pierwsza. Uzyskane wyniki teoretyczne wykazują bardzo dobrą zgodność z wynikami obliczeń komputerowych. Obliczenia przeprowadzone przez T. Oliveira e Silva oraz autora niniejszej pracy wykonano w zakresie liczb pierwszych do 1014. Ponieważ uzyskane wyniki teoretyczne mają charakter warunkowy (są prawdziwe pod warunkiem słuszności uogólnionej hipotezy Riemanna), więc sprawdzenie zgodności nawet w dużym przedziale początkowych liczb pierwszych pozostawia pewien niedosyt. Rodzi się pytanie, czy dalej będzie zachowana równie dobra zgodność. W związku z tym kilka lat przed 2000 rokiem autor podjął próby wyrywkowego badania liczb pierwszych w oddalonych od siebie przedziałach wartości dużych liczb pierwszych, mniej więcej do górnej granicy 1) Praca naukowa finansowana ze środków na naukę w latach 2007-2010 jako projekt badawczy nr N517 003 32/0583 rzędu 1050. Początkowo były to przedziały zawierające milion kolejnych liczb naturalnych. Ze względu na poziom techniki obliczeniowej sprzed ponad dziesięciu lat przedziały te były dzielone na mniejsze, a obliczenia przeprowadzano w trybie wsadowym, wykorzystując komputery laboratoryjne w dni wolne od pracy. Taką organizację obliczeń cechowała duża niedogodność. Obliczenia na różnych komputerach na ogół nie kończyły się w jednakowym czasie i często trzeba było przerywać je, z powodu potrzeby wykorzystania laboratoriów do zajęć ze studentami przed ukończeniem cząstkowych obliczeń. Ponadto "ręczne" zarządzanie obliczeniami mogło być (i było) przyczyną powstania wielu błędów. Typowy błąd, który występował podczas takiej organizacji badań, to wznowienie przerwanych obliczeń od innego miejsca. Powodowało to, że moc zbioru liczb pie[...]

O trójmianach nieprzywiedlnych nad ciałem GF(3)


  Przez trójmian rozumie się wielomian, który jest kombinacją liniową o niezerowych współczynnikach dokładnie trzech jednomianów różnych stopni. W artykule ograniczono się wyłącznie do wielomianów o współczynnikach z ciała Galois GF(3). Wielomiany o współczynnikach z ciała skończonego, które dają się przedstawić w postaci iloczynu wielomianów niższego stopnia niż one same, nazywa się rozkładalnymi albo inaczej przywiedlnymi. W przeciwnym przypadku mówi się, że są one wielomianami nierozkładalnymi albo nieprzywiedlnymi nad tym ciałem. Na przykład wielomian X7+2X2+1 jest nierozkładalny nad GF(3), natomiast X7+X2+1 jest wielomianem rozkładalnym nad tym samym ciałem, bowiem X7+X2+1= (X+2)2(X2+X+2)(X3+X2+2). Wielomiany nieprzywiedlne nad ciałami skończonymi i metody ich znajdowania mają wielkie znaczenie w kryptografii [4] i teorii kodowania [2]. W kryptografii - ze względu na istotne korzyści wynikające z reprezentacji wielomianów na bitach słowa maszynowego - wykorzystuje się trójmiany nierozkładalne nad ciałem dwuelementowym GF(2). Nie zawsze jednak udaje się znaleźć trójmian nieprzywiedlny zadanego stopnia n [6]. Dla około połowy wszystkich stopni, jak pokazują badania w zakresie liczb n nie większych niż 30 000, trójmian nierozkładalny nie istnieje. W tych przypadkach wykorzystuje się inne wielomiany rzadkie (o małej liczbie niezerowych współczynników), np. pięciomiany [6], [7], które zawsze udaje się znaleźć. Dobrą alternatywą może też być wykorzystanie wielomianów rzadkich o współczynnikach z innych małych ciał liczbowych [8]. Badania pokazują, że w miarę wzrostu liczności elementów skończonego ciała liczbowego maleje liczba wartości n, dla których nie istnieje trójmian nieprzywiedlny stopnia n nad tym ciałem [1]. Jest to zgodne z intuicją, bowiem zwiększa się zbiór, z którego są wybierane współczynniki wielomianów, a zatem ma się prawo oczekiwać, że przy pewnej konfiguracji współczynników badany wielomian może okazać się ni[...]

NIEROZWIĄZANE PROBLEMY DOTYCZĄCE WIELOMIANÓW NIEPRZYWIEDLNYCH NAD CIAŁEM SKOŃCZONYM GF(2) DOI:10.15199/59.2017.8-9.35


  Wielomiany o współczynnikach z ciała skończonego GF(p), nie dające przedstawić się w postaci iloczynu dwóch wielomianów niższego stopnia niż on sam o współczynnikach z tego samego ciała nazywamy nierozkładalnymi albo nieprzywiedlnym nad GF(p). Znajdują one szerokie zastosowanie w teorii kodowania i kryptografii, przede wszystkim do przyspieszania działań w arytmetyce resztowej wielomianów. W zastosowaniach kryptograficznych z uwagi na udogodnienia wynikające z reprezentacji współczynników wielomianów na pojedynczych bitach wykorzystuje się wielomiany nierozkładalne nad ciałem dwuelementowym GF(2). W przypadku ciał GF(2n), istotny wpływ na efektywność działań arytmetycznych ma dobór właściwego typu wielomianu. Najczęściej wybierane są trójmiany nieprzywiedlne o ile istnieją lub pięciomiany, tzn. wielomiany, które posiadają odpowiednio dokładnie trzy lub dokładnie pięć niezerowych współczynników. Innym typem wielomianów nierozkładalnych są wielomiany najmłodsze leksykograficznie. Arytmetyka modularna generowana przez ten typ wielomianów jest równie efektywna pod względem implementacyjnym jak arytmetyka na bazie trójmianów nierozkładalnych. Wszystkim trzem rodzajom wielomianów autor poświęcił wiele uwagi w poprzednich pracach [1], [2], [4], [5] doprowadzając ich badania w roku 2010 do stopnia 50000. W latach 2010- 2012 korzystając z dwóch laboratoriów Zakładu Podstaw Telekomunikacji Politechniki Warszawskiej w czasie wolnym od zajęć ze studentami badania te zostały doprowadzone dla trójmianów i pięciomianów nad GF(2) do stopnia 100000 i dla wybranych stopni do 300000, natomiast dla wielomianów najmłodszych leksykograficznie do stopnia 132000. Dla wielomianów nieprzywiedlnych, które są najmłodsze leksykograficznie oddzielnie przebadano przedział stopni między 256000 i 257000. Szczególny przypadek trójmianów najmłodszych leksykograficznie postaci oraz +1 zbadano dla wszyst[...]

O dwóch nowych właściwościach wielomianów nierozkładalnych i pierwotnych nad GF(p) DOI:10.15199/59.2017.11.2


  Niech p będzie liczbą pierwszą. Wielomiany o współczynnikach z ciała skończonego GF(p), niedające się przedstawić w postaci iloczynu dwóch wielomianów niższego stopnia niż on sam i o współczynnikach z tego samego ciała, nazywają się nierozkładalnymi albo nieprzywiedlnymi nad GF(p). Znajdują one liczne zastosowania w teorii kodowania [1] i kryptografii [2], [3]. Dla ustalonej liczby naturalnej n oraz liczby pierwszej p niech In(p) oznacza liczbę wielomianów nieprzywiedlnych stopnia n nad GF(p). Funkcja In(p) jest zdefiniowana w następujący sposób: (1) gdzie m oznacza funkcję Möbiusa [4]. Z postaci wyrażenia (1) wynika, że dla każdej liczby naturalnej n i każdej liczby pierwszej p istnieje co najmniej jeden wielomian nierozkładalny. Dla p = 2 wartość In(2) oznacza się jako I2. Wielomian nierozkładalny stopnia n nad GF(p) jednej zmiennej X nazywa się wielomianem pierwotnym, jeżeli jednomian X generuje grupę multiplikatywną GF*(pn). Dla każdej liczby naturalnej n i każdej liczby pierwszej p istnieje wielomian pierwotny stopnia n nad GF(p). Ściślej mówiąc, liczbę wielomianów pierwotnych dla ustalonych wartości n i p można wyznaczyć ze wzoru: (2) gdzie f oznacza funkcję Eulera, zwracającą dla argumentu naturalnego n liczbę liczb względnie pierwszych z n. Korzystając ze specyfiki wzoru (1), można wykazać, że występują następujące dwie nierówności [4]: (3) [...]

O złożoności problemu wyznaczania podstawy logarytmu dyskretnego w schemacie Diffi'ego-Hellmana DOI:10.15199/59.2018.1.3


  W schemacie podziału sekretu Diffi'ego-Hellmana w grupie multiplikatywnej reszt modulo liczba pierwsza zasadniczym i najbardziej pracochłonnym problemem jest wybór generatora tej grupy. W pracy [4] szczegółowo rozpatrzono ten problem, wykonując serię rozległych eksperymentów z wykorzystaniem lokalnych sieci komputerowych oraz otwartego środowiska Internet. W krytycznej fazie eksperymentu uczestniczyło ponad 400 stacji roboczych, głównie komputerów IBM PC, będących w użytkowaniu studentów. Z przeprowadzonych badań, które zakończyły się w kwietniu 2007 roku, wynika, że generatory grup multiplikatywnych modulo liczba pierwsza (zwane też pierwiastkami pierwotnymi modulo liczba pierwsza) wyrażają się małymi liczbami naturalnymi. Na przykład liczby 2, 3 lub 5 są najmniejszymi pierwiastkami pierwotnymi w ok. 74% przypadków. Jeżeli dołączy się do tego zbioru liczbę 6, wówczas obejmie on prawie 80% wszystkich liczb pierwszych. Nie jest to jednak reguła, ponieważ zdarzają się przypadki, w których nawet dla małych liczb pierwszych (liczb, które dają się zapisać na 64 bitach) ich najmniejszy pierwiastek wydaje się znacznie odbiegać od ich statystycznego zachowania. Ponadto z badań wynika, że gęstości liczb pierwszych, dla których najmniejszy generator (najmniejszy pierwiastek pierwotny) jest równy danej liczbie naturalnej, dążą do pewnych ustalonych wartości, które można efektywnie policzyć przy założeniu prawdziwości hipotezy Riemanna o funkcji dzeta nad pewnymi ciałami Kummera. Zgodność wyników uzyskanych doświadczalnie z wynikami uzyskanymi na drodze teoretycznej jest zdumiewająca. Z badań wynika, że wielkość najmniejszego pierwiastka pierwotnego modulo liczba pierwsza jest funkcją wielomianowo zależną od logarytmu tej liczby. Warunkowe wyniki teoretyczne szacują tę złożoność jako funkcję zależną od kwadratu logarytmu naturalnego liczby pierwszej [4]. Badania numeryczne pokazują, że może to być funkcja wolniej rosnąca, niż kwad[...]

Wykorzystanie generatora Legendre'a do konstrukcji wektorowych funkcji boolowskich typu S-box

Czytaj za darmo! »

Niech a, n będą dwiema liczbami całkowitymi. Jeśli gcd(a, n)=1, gdzie gcd oznacza największy wspólny dzielnik liczb całkowitych a, n i kongruencja: (1) ma rozwiązanie x, wówczas a jest nazywana resztą kwadratową n. Jeżeli (1) nie ma rozwiązania, a jest zwana nieresztą kwadratową n. Dla przypadku, gdy n jest równe liczbie pierwszej p większej od 2, Legendre wprowadził specjalny symbol (a/p)[...]

Badania wielomianów nierozkładalnych wysokich stopni nad GF(2) - narzędzia i wyniki

Czytaj za darmo! »

Arytmetyce wielomianów nad GF(2) poświęcono w literaturze wiele miejsca, z racji licznych zastosowań w teorii kodowania oraz w kryptografii. Część z nich wraz z odniesieniami bibliograficznymi opisano w naszej wcześniejszej pracy [4]. Przedstawiliśmy tam wyniki badań nad najmłodszymi leksykograficznie wielomianami nierozkładalnymi o współczynnikach z ciała binarnego GF(2) i stopniach n nie w[...]

Modyfikacja algorytmu A5/1

Czytaj za darmo! »

GSM jest systemem komórkowym, z którego korzysta na całym świecie ponad 1,75 mld abonentów. Koncepcja i projekt systemu powstały w latach 80. poprzedniego wieku. W architekturze systemu można wyróżnić trzy podstawowe segmenty: stacje ruchome, zespół stacji bazowych oraz część komutacyjno-sieciową. Segment stacji ruchomych obejmuje terminale użytkowników wraz z kartami SIM. Rozróżnialne są za[...]

 Strona 1  Następna strona »