» O kilku właściwościach trójmianów nierozkładalnych nad małymi ciałami liczbowymi
|
|
Andrzej PASZKIEWICZ 
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[...]
więcej»
w zeszycie
PRZEGLĄD TELEKOMUNIKACYJNY - WIADOMOŚCI TELEKOMUNIKACYJNE 2009/4
|
|
|
|
|
|
» Anomalie w rozkładzie statystycznym dużych liczb pierwszych o zadanym najmniejszym pierwiastku pierwotnym
|
|
Andrzej Paszkiewicz
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[...]
więcej»
w zeszycie
PRZEGLĄD TELEKOMUNIKACYJNY - WIADOMOŚCI TELEKOMUNIKACYJNE 2010/7
|
|
|
» O trójmianach nieprzywiedlnych nad ciałem GF(3)
|
|
Andrzej Paszkiewicz
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[...]
więcej»
w zeszycie
PRZEGLĄD TELEKOMUNIKACYJNY - WIADOMOŚCI TELEKOMUNIKACYJNE 2011/2-3
|
|
|
|
|
|
|
|
|
|
|
|
|
Strona 1
|
Twój Profil
Twój koszyk
