Properties of reducible polynomials

• Autorzy: Borowska A.

Warianty tytułu

PL

Własności wielomianów redukowalnych

• Języki publikacji: EN

Abstrakty

EN

We consider polynomials p(x) over the 2-element field F₂. If p(x) of degree n is irreducible, then a set of polynomials of degree less than n together with operations (of addition and multiplication) modulo p(x) forms the finite field GF(2ⁿ). If p(x) of degree n is reducible, then the set of all polynomials of degree less than n contains several groups with respect to multiplication modulo p(x). Properties of these groups are described in Section 3. In Section 4 is presented a polynomial factorization algorithm. Irreducible polynomials are widely used (for instance in cryptography) due to the possibility of an efficient representation of all the elements from GF(2ⁿ) on a fixed number of bits.

PL

Analizowano wielomiany z jedną zmienną nad ciałem skończonym F₂. Jeśli wielomian p(x) stopnia n jest nierozkładalny, to zbiór wielomianów stopnia mniejszego od n wraz z operacjami (dodawania i mnożenia) modulo p(x) tworzy ciało skończone GF(2ⁿ). Jeżeli p(x) stopnia n jest rozkładalny, w zbiorze wielomianów stopnia mniejszego od n można wyróżnić kilka podzbiorów, które wraz z działaniem *_p (mnożenie modulo p(x)) tworzą grupy. Własności tych grup (oparte na wykonanych testach) opisano w sekcji 3. W sekcji 4 zaproponowano algorytm faktoryzacji wielomianów. Wydajność zapisywania elementów GF(2ⁿ) na ustalonej liczbie bitów zachęca do wykorzystywania wielomianów nierozkładalnych na przykład w kryptografii.

Słowa kluczowe

EN

irreducible polynomials; factorization; cryptography; elliptic curves

PL

wielomian nieredukowalny; faktoryzacja; kryptografia; krzywe eliptyczne

• Wydawca: Polskie Towarzystwo Symulacji Komputerowej
• Czasopismo: Symulacja w Badaniach i Rozwoju
• Rocznik: 2015
• Tom: Vol. 6, nr 3
• Strony: 175--184
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Borowska A.

• Politechnika Białostocka, Wydział Informatyki ul. Wiejska 45A, 15-351 Białystok

Bibliografia

• 1. Białynicki-Birula A.: Algebra. PWN, Warsaw 1971.
• 2. Blake J., Seroussi G., Smart N.: Elliptic Curves in Cryptography. Cambridge University Press, New York, 2001.
• 3. Browkin J.: Field Theory. PWN, Warsaw 1977
• 4. Bryński M.: Elements of the Galois Theory Alfa Publishing House, Warsaw, 1985.
• 5. Chmielowiec A.: Efficient Methods for Generating Secure Parameters of Public-Key Algorithms Doctoral dissertation, Warsaw 2012.
• 6. Gawinecki J., Szmidt J.: Applications of Finite Fields and Elliptic Curves in Cryptography. WAT, Warsaw 1999
• 7. Jurkiewicz M., Gawinecki J., Bora P., Kijko T.: Applications of Elliptic Curves for Designing Secure Algorithms and Cryptographic Protocols. Cryptology and Cybersecurity, WAT, Warsaw 2014.
• 8. Koblitz N.: Algebraic Aspects of Cryptography, WNT Warsaw 2000.
• 9. Pieprzyk J., Hardjono T., Seberry J.: Fundamentals of Computer Security. Springer-Verlag Berlin Heidelberg, Helion, 2003.
• 10. Stallings W.: Cryptography and Network Security: Principles and Practices. Helion, Gliwice 2011.
• 11. Stinson D. R.: Cryptography. Theory and Practice. WNT, Warsaw 2005.

Uwagi

EN

1. The research presented in this paper was founded by the BST S/WI/1/2014.

PL

2. Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).