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

• Autorzy: Bartosik P. , Paszkiewicz A.

Warianty tytułu

EN

A study on irreducible polynomials of high degrees over GF(2) tools and results

• Języki publikacji: PL

Abstrakty

PL

Przedstawiono metody i techniki przyspieszenia arytmetyki modularnej w ciałach skończonych o charakterystyce 2. Wprowadzone poprawki sprawiają, że używany pakiet jest szybszy od znanego pakietu NTL. Dzięki temu można zwiększyć zakres badań wielomianów nierozkładalnych, najmłodszych leksykograficznie aż do stopnia n równego 30 000.

EN

In the paper we present some methods and techniques that accelerate mo-dular arithmetic in finite fields with characteristic two. The improvements make our library faster than the well known packet NTL. This made possible to extend the area of computation of all irreducible polynomials which are lexicographically youngest up to the degree n equal to 30000.

Słowa kluczowe

PL

arytmetyka modularna; ciało skończone Galois; wielomiany nierozkładalne; wielomiany pierwotne

EN

modular arithmetic; finite Galois fields; irreducible polynomials; primitive polynomials

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2008
• Tom: R. 81, nr 12
• Strony: 1059--1065
• Opis fizyczny: Bibliogr. 6 poz., rys., tab.

Twórcy

autor

Bartosik P.

autor

Paszkiewicz A.

• Instytut Telekomunikacji, Wydział Elektroniki i Technik Informacyjnych PW,

Bibliografia

• [1] Shoup V., NTL: A library for doing number theory. http: //www. shoup. net/ntl/
• [2] Brent R. R. Larvala S. and Zimmermann P: A fast algorithm for testing irreducibility of trinomials mod 2 (preliminary report), Report PRG TR-13-00, Oxford University Computing Laboratory, December 2000, http: //wwwmaths. anu. edu. au/~brent/pub/pub199. html
• [3] Brent R. R, Gaudry P, Thome E. and Zimmermann P: Faster multiplication in GF (2) /X/, INRIA Tech Report RR-6359, Nov. 2007, 19 pp. To appear in Proc. ANTS-VIII, Banff, May 17-22, 2008.
• [4] Bartosik P, Paszkiewicz A.: Wyznaczanie najmłodszych leksykograficznie wielomianów nieprzywiedlnych. Krajowe Sympozjum Telekomunikacji i Teleinformatyki 10-12 września 2008, Bydgoszcz, KST2008 Przegląd Telekomunikacyjny, Rocznik LXXXI nr 8/9 (2008)
• [5] Rabin M. O.: Probabilistic algorithms in finite fields. SIAM J. Сотр., 9, (1980).
• [6] Ben-Or M.: Probabilistic algorithms in finite fields. Proc. 22nd IEEE Symp. Foundations Computer Science, 1981