O pewnej hipotezie dotyczącej wielomianów nieprzywiedlnych nad GF(2)

• Autorzy: Paszkiewicz A.

Warianty tytułu

EN

On a hypothese concerning irreducible trinomials over GF(2)

• Języki publikacji: PL

Abstrakty

PL

W pracy zostały znalezione wszystkie najmłodsze leksykograficznie wielomiany nierozkładalne nad ciałem binarnym GF(2) o stopniach od 10000 do 20000. Każdy ze znalezionych wielomianów posiada szczególną strukturę: może być przedstawiony w postaci X^n + g(X), gdzie g(X) jest wielomianem bardzo niskiego stopnia w stosunku do n, zależnym od n. Hipoteza, o której mowa w tytule dotyczy oszacowania maksymalnej szybkości wzrostu stopnia wielomianu g(X) w zależności od n. Przy okazji odnosimy się do innych przypuszczeń mówiących o zależności stopnia wielomianu g(X) od n. Badania przeprowadzono z wykorzystaniem techniki obliczeń rozproszonych w niewielkiej sieci komputerowej składającej się z komputerów IBM PC.

EN

In this paper all irreducible and lexicographically youngest polynomials over the binary field GF(2) and degrees between 10000 to 20000 have been enumerated. Each of these polynomials has a specific structure: it can be expressed in the form X^n + g(X), where g(X) is a polynomial with very low degree in comparison to n and depending on n. A hypothesis mentioned in the title addresses to the maximal growth rate the degree of g(X) as a function of n. By the way we discuss other conjectures concerning relations between the degree of g(X) and n. All computations were performed by the aid of distributed computing technique in a small computer network consisting of few IBM PC work stations.

Słowa kluczowe

PL

wielomiany nieprzywiedlne; ciało skończone

EN

irreducible polynomials; finite fields

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Matematyka Stosowana : matematyka dla społeczeństwa
• Rocznik: 2009
• Tom: T. 10/51
• Strony: 39--49
• Opis fizyczny: Bibliogr. 11 poz., tab., wykr.

Twórcy

autor

Paszkiewicz A.

• Politechnika Warszawska ul. Nowowiejska 15/19 00-661 WARSZAWA, Poland,

Bibliografia

• [1] W. Aiello and T. Leighton, Coding Theory, Hypercube Embeddings, and Fault Tolerance, in Proc. Of the 3rd Annual Symposium on Parallel Algorithms and Architectures, pp. 125-136, 1991;
• [2] P. Bartosik, A. Paszkiewicz, Wyznaczanie Najmłodszych Leksykograficznie Wielomianów Nieprzywiedlnych, Krajowe Sympozjum Telekomunikacji i Teleinformatyki, Bydgoszcz, 10-12 września 2008, Przegląd Telekomunikacyjny 8-9 (2008), 1282-1292;
• [3] R. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley Publishing Company, Reading, Massachusetts, Reprint with Correction 1984;
• [4] I. F. Blake, S. Gao, R. J. Lambert, Construction and Distribution Problems for Irreducible Trinomials over Finite Fields, in Applications of Finite Fields, D. Gollman (ed.), Oxford, Oxford Univ. Press, 1996;
• [5] R. P. Brent, S. Larvala, P. Zimmerman, A Fast Algorithm for Testing Irreducibility of Trinomials mod 2; Technical Report PRG-TR-13-00, Oxford University Laboratory Wolfson Building, Parks Road, Oxford OX1 3QD;
• [6] D. Coppersmith, Fast Evaluation of Logarithms in Fields of Characteristic Two, IEEE Trans. Inform. Theory, vol. IT-30, pp. 587-594, 1984;
• [7] S. Gao, J. Howell, D. Panario, Irreducible Polynomials of Given Forms, in R. Mullen (ed.) Finite Fields: Theory, Applications and Algorithms, Contemporary Mathematics (1999), vol. 225, pp. 43-54;
• [8] A.J. Menezes et al., Handbook of Applied Cryptography, CRC Press, Boca Raton, New York 1997;
• [9] A. Paszkiewicz, Rzadkie i gęste wielomiany nierozkładalne, Krajowe Sympozjum Telekomunikacji'95, t. B, Problemy Podstawowe, str. 249-254, Wyd. Politechniki Warszawskiej, Warszawa 1995;
• [10] G. Seroussi, Table of Low-Weight Binary Irreducible Polynomials, Hewlett-Packard, HPL, pp. 98-135, August 1998;
• [11] V. Shoup, http://www.shoup.net.papers/ (12.2007).