Microsoft Word - tpel.doc


Mathematical Problems of Computer Science 33, 144--149, 2010. 

144 

 
 
 

Construction of Explicit Irreducible Polynomials 
 over 2F  in Cluster Computational 

 Environment 
 

Ofelya Manukyan and Melsik Kyuregyan 
 

Institute for Informatics and Automation Problems of  NAS of RA 
e-mail: manofa81@yahoo.com, melsik@ipia.sci.am 

 
Abstract 

This paper describes a method for constructing families of explicit irreducible 
polynomials over 2F . The proposed method allows construction of explicit 
polynomials of higher degree over 2F  from a given sequence of primitive 
polynomials. A computational algorithm has been developed and implemented on 
base of this method. The program is realized in the most effective way possible in 
cluster computational environment. Allocation and distribution of memory resources 
have been implemented in a careful manner, since data size increases drastically with 
increasing of the amount of computations required. Program paralleling is performed 
using data paralleling, i.e. data is distributing among all processors, which ran the 
same program and each of which builds the subsequent irreducible polynomial, and 
finally a sequence of all the irreducible polynomials in explicit form is obtained. 
Moreover, the program also searches for the polynomial with the lowest possible 
weight among of all the polynomials of the same degree.            

 
References 
[1] M. Kyuregyan, “Recurrent methods for constructing irreducible polynomials over )2( sGF ”,   

Finite Fields and Their Applications 8, pp. 52-68, 2002.  

[2] R. Lidl and H. Niederreiter,  Finite Fields , Cambridge University Press 1987. 

[3] A. J. Menezes, I. F. Blake, X. Gao, R. C. Mullin, S. A. Vanstone and T. Yaghoobian, 
“Applications of finite fields”, Kluwer Academic Publishers, Boston, Dordrecht, Lancaster, 
1993. 

 
 
 
 
 
 
 



O. Manukyan, M. Kyuregyan  
 

145 

2F  í»ñç³íáñ ¹³ßïÇ íñ³ ³Ýí»ñ³Í»ÉÇ µ³½Ù³Ý¹³ÙÝ»ñÇ µ³ó³Ñ³Ûï 
ï»ëùáí ϳéáõóÙ³Ý »Õ³Ý³Ï Ïɳëï»ñ³ÛÇÝ Ñ³ßíáÕ³Ï³Ý Ñ³Ù³Ï³ñ·áõÙ 

 
ú. سÝáõÏÛ³Ý ¨ Ø. ÎÛáõñ»ÕÛ³Ý 

 
²Ù÷á÷áõÙ 

 
²ß˳ï³ÝùáõÙ Ýϳñ³·ñí³Í ¿ 2F  í»ñç³íáñ ¹³ßïÇ íñ³ ³Ýí»ñ³Í»ÉÇ 

µ³½Ù³Ý¹³ÙÝ»ñÇ µ³ó³Ñ³Ûï ï»ëùáí ϳéáõóÙ³Ý ÙÇ »Õ³Ý³Ï, áñÁ Ñݳñ³íáñÇÝë 
¿ý»ÏïÇíáñ»Ý Ùß³Ïí»É ¨ Çñ³Ï³Ý³óí»É ¿ Ïɳëï»ñ³ÛÇÝ Ñ³ßíáÕ³Ï³Ý Ñ³Ù³Ï³ñ·áõÙ: 
ÐÇßáÕáõÃÛ³Ý é»ëáõñëÝ»ñÇ µ³ßËáõÙÁ` ÑÇßáÕáõÃÛ³Ý Ñ³ïϳóáõÙÝ áõ ³½³ïáõÙÁ ϳï³ñí»É 
»Ý ËݳÛáÕ³µ³ñ, ù³ÝÇ áñ ѳßí³ñÏÝ»ñÇ ÁÝóóùáõÙ ïíÛ³ÉÝ»ñÇ »ñϳñáõÃÛáõÝÝ»ñÁ ß³ï 
³ñ³· ³×áõÙ »Ý: Îɳëï»ñ³ÛÇÝ Ñ³ßíáÕ³Ï³Ý Ñ³Ù³Ï³ñ·áõÙ Íñ³·ñÇ ½áõ·³Ñ»é³óáõÙÁ 
ϳï³ñí»É ¿ Áëï ïíÛ³ÉÝ»ñÇ, ³ÛëÇÝùÝ ïíÛ³ÉÝ»ñÁ µ³ßËíáõÙ »Ý åñáó»ëáñÝ»ñÇ ÙÇç¨, 
µáÉáñ åñáó»ëáñÝ»ñÁ ³ß˳ïáõÙ »Ý ÙǨÝáõÛÝ Íñ³·ñáí ¨ Ûáõñ³ù³ÝãÛáõñÁ ϳéáõóáõÙ ¿ 
Ñ»ñÃ³Ï³Ý ³Ýí»ñ³Í»ÉÇ µ³½Ù³Ý¹³ÙÁ: ²ñ¹ÛáõÝùáõÙ ëï³ÝáõÙ »Ýù ³Ýí»ñ³Í»ÉÇ 
µ³½Ù³Ý¹³ÙÝ»ñÇ Ñ³çáñ¹³Ï³ÝáõÃÛáõÝ ¨ µ³óÇ ³Û¹ ÷ÝïñáõÙ »Ýù ÙǨÝáõÛÝ ³ëïÇ׳ÝÇ 
Ñݳñ³íáñÇÝë ÷áùñ ÏßÇé áõÝ»óáÕ ³Ýí»ñ³Í»ÉÇ µ³½Ù³Ý¹³ÙÁ: