D:\sbornik\...\article.DVI


Mathematical Problems of Computer Science 35, 99{103, 2011.

I r r educibility of Some Composite P olynomials Over

Finite Fields ¤

S e r g e y A b r a h a m ya n a n d E d it a H a r u t yu n ya n

Institue for Informatics and Automation Problems of NAS of RA

e-mail serj.abrahamyan@gmail.com, edita@ipia.sci.am

Abstract

Given the ¯eld F with q elements and of characteristics p and an irreducible polyno-
mial P (x) = cnx

n +cn¡1x
n¡1+c1xn¢¢¢c0 over F. We prove that the composite polynomial

(dxp ¡ dx)n p
³

axp¡ax+c
dxp¡dx

´
is irreducible over F under certain conditions. Also a recur-

sive construction of sequences of irreducible polynomials of degree n2k(k = 1; 2; 3; ¢ ¢ ¢)
over F2s is given.

Refer ences

[1 ] S . E . A b r a h a m ya n , \ Co n s t r u c t io n o f Ir r e d u c ib le P o lyn o m ia ls o ve r Fin it e Fie ld s " , P ro-
ceedings of 12th International W orkshop, CASC 2010, in L ecture Notes in Computer
Science, vo l. 6 2 4 4 , Ge r d t , p p . 3 -4 , 2 0 1 0 .

[2 ] S . D . Co h e n , \ On ir r e d u c ib le p o lyn o m ia ls o f c e r t a in t yp e s in ¯ n it e ¯ e ld s " , P roc. Cam-
bridge P hilos. Soc., vo l. 6 6 , p p . 3 3 5 { 3 4 4 , 1 9 6 9 .

[3 ] R . L id l a n d H . N ie d e r r e it e r . Fin it e Fie ld s . Ca m b r id g e U n ive r s it y P r e s s , 1 9 8 7 .

[4 ] M. K . K yu r e g ya n , \ R e c u r r e n t m e t h o d s fo r c o n s t r u c t in g ir r e d u c ib le p o lyn o m ia ls o ve r
Fq o f o d d c h a r a c t e r is t ic s " , F inite F ields Appl., vo l. 9 , p p . 3 9 { 5 8 , 2 0 0 3 .

[5 ] M. K . K yu r e g ya n , \ It e r a t e d c o n s t r u c t io n s o f ir r e d u c ib le p o lyn o m ia ls o ve r ¯ n it e ¯ e ld s
wit h lin e a r ly in d e p e n d e n t r o o t s " , F inite F ields , Appl., vo l. 1 0 , p p . 3 2 3 { 4 3 1 , 2 0 0 4 .

[6 ] M. K . K yu r e g ya n , \ R e c u r r e n t m e t h o d s fo r c o n s t r u c t in g ir r e d u c ib le p o lyn o m ia ls o ve r
Fq o f o d d c h a r a c t e r is t ic s II" , F inite F ields, Appl., vo l. 1 2 , p p . 3 5 7 { 3 7 8 , 2 0 0 6 .

[7 ] M. K . K yu r e g ya n a n d G. M. K yu r e g ya n , \ Ir r e d u c ib le Co m p o s it io n s o f P o lyn o m ia ls
o ve r Fin it e Fie ld s " , D esign, Codes and Cryptography, A va ila b le o n lin e : IS S N :0 9 2 5 -1 0 2 2
2 0 1 0 .

[8 ] A . Me n e z e s , I.F. B la ke , X . Ga o , R . C. Mu llin , S . A . V a n s t o n e , T. Y a g h o o b ia n . Appli-
cations of F inite F ields, K lu we r A c a d e m ic P u b lis h e r s , B o s t o n - D o r d r e c h t - L a n c a s t e r ,
1 9 9 3 .

[9 ] R . R . V a r s h a m o v, \ A g e n e r a l m e t h o d o f s yn t h e s iz in g ir r e d u c ib le p o lyn o m ia ls o ve r
Ga lo is ¯ e ld s " , Soviet M ath. D okl., vo l. 2 9 , 3 3 4 { 3 3 6 , 1 9 8 4 .

¤The work was supported by Armenian Target Programm 04.10.31.

9 9



1 0 0 Irreducibility of Some Composite Polynomials Over Finite Fields

àñáß µ³Õ³¹ñÛ³É µ³½Ù³Ý¹³Ù»ÝñÇ ãµ»ñí»ÉÇáõÃÛáõÝÁ í»ñç³íáñ ¹³ßï»ñÇ íñ³

ê. ²µñ³Ñ³ÙÛ³Ý ¨ ¾. гñáõÃÛáõÝÛ³Ý

²Ù÷á÷áõÙ

²ß˳ï³ÝùÁ ÝíÇñí³Í ¿ í»ñç³íáñ ¹³ßï»ñÇ íñ³ ãµ»ñíáÕ µ³½Ù³Ý¹³ÙÝ»ñÇ µ³Õ³-
¹ñáõÃÛáõÝÝ»ñÇ Ï³éáõóÙ³ÝÁ: îñí³Í ¿ q ѽáñáõÃÛ³Ùµ, p µÝáõó·ñÇãáí Fq ¹³ßïÁ ¨ Fq
¹³ßïÇ íñ³ P ( x ) = cnx

n + cn¡1x
n¡1+c1xn¢¢¢c0 ãµ»ñíáÕ µ³½Ù³Ý¹³ÙÁ: òáõÛó ¿ ïñí³Í, áñ

( dxp ¡ dx ) n p
³

axp¡ax+c
dxp¡dx

´
µ³Õ³¹ñáõÃÛáõÝÁ ãµ»ñíáÕ ¿ Fq ¹³ßïÇ íñ³ áñáß³ÏÇ å³ÛÙ³ÝÝ»ñÇ

¹»åùáõÙ: ²í»ÉÇÝ, ïñí³Í ¿ F2s ¹³ßïÇ íñ³ n2 k( k = 1 ; 2 ; 3 ; ¢ ¢ ¢ ) ³ëïÇ׳ÝÇ ãµ»ñíáÕ
µ³½Ù³Ý¹³ÙÝ»ñÇ Ï³éáõóÙ³Ý Ñ³çáñ¹³Ï³Ý »Õ³Ý³Ï: