D:\sbornik\...\Said_9\tpel.DVI


Mathematical Problems of Computer Science 35, 63{69, 2011.

I r r educible Compositions of P olynomials Over Finite

Fields of E ven Char acter istic¤

S a e id M. Me h r a b i a n d Me ls ik K . K yu r e g ya n

Institue for Informatics and Automation Problems of NAS of RA

e-mail smbatt@ipia.sci.am

Abstract

This note presents some results with the constructive theory of synthesis of irre-
ducible polynomials over a Galois ¯eld with even characteristic. We prove a theorem
that plays an important role for constructing irreducible polynomials. By this theo-
rem a recurrent method for constructing families of irreducible polynomials of degree
n2k (k = 1; 2; :::) over F2s is proposed.

Refer ences

[1 ] E .R . B e r le ka m p , A lg e b r a ic Co d in g Th e o r y, Mc Gr a w-H ill, N e w Y o r k, 1 9 6 8 .

[2 ] I.F. B la ke , G.S e r o u s s i a n d N .P .S m a r t , E llip t ic c u r ve s in Cr yp t o g r a p h y, Ca m b r id g e
U n ive r s it y P r e s s , Ca m b r id g e , R e p r in t e d 2 0 0 0 .

[3 ] B . Ch o r , R . r ive s t , \ A kn a p s a c k-t yp e p u b lic ke y c r yp t o s ys t e m b a s e d o n a r it h m e t ic in
¯ n it e ¯ e ld s " , IE E E Trans.Inform.Theory, vo l. 3 4 , p p . 9 0 1 -9 0 9 , 1 9 8 8 .

[4 ] J. Ca lm e t , \ A lg e b r a ic a lg o r it h m s in GF ( q) " ,D iscrete M ath, vo l. 5 6 p p . 1 0 1 -1 0 9 , 1 9 8 5 .

[5 ] R . Ch a p m a n , \ Co m p le t e ly n o r m a l e le m e n t s in it e r a t e d qu a d r a t ic e xt e n s io n s Of ¯ n it e
¯ e ld s " ,F inite F ields Appl, vo l. 3 , p p . 3 -1 0 , 1 9 9 7 .

[6 ] 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. S o c , vo l. 6 6 , p p . 3 3 5 -3 4 4 , 1 9 6 9 .

[7 ] S . D . Co h e n ,\ Th e e xp lic it c o 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 ¯ n it e ¯ e ld s " ,
D e. Codes Cryptogr, vo l. 2 , p p . 1 6 9 -1 7 3 , 1 9 9 2 .

[8 ] W . E b e r ly,\ V e r y fa s t p a r a lle l m a t r ix a n d p o lyn o m ia l a r it h m e t ic " , 25th Annual sym-
posium on F oundations of Computer Science, p p . 2 1 -3 0 , 1 9 8 4 .

[9 ] S . Ga o , N o r m a l b a s e s o ve r ¯ n it e ¯ e ld s , P h .D Th e s is , W a t e r lo o , 1 9 9 3 .

[1 0 ] M.K . K yu r e g ya n ,\ R e c u r r e n t Me t h o d s fo r Co 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 "
, F inite F ields Apple, vo l. 8 , p p . 5 2 -6 8 , 2 0 0 2 .

[1 1 ] 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 Apple, vo l. 1 0 , p p . 3 2 3 -4 3 1 , 2 0 0 4 .

[1 2 ] 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 .

¤2000 Mathematics subject classi¯cations: 47A68, 47A70

6 3



6 4 Irreducible Compositions of Polynomials Over Finite Fields of Even Characteristic

[1 3 ] 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 .

[1 4 ] M.K . K yu r e g ya n , \ Qu a d r a t ic t r a n s fo r m a t io n s a n d s yn t h e s is o f ir r e d u c ib le p o lyn o m i-
a ls o ve r ¯ n it e ¯ e ld s " , D okl, Akad, Nauk Arm, SSR , vo l. 8 4 ( 2 ) , p p . 6 7 -7 1 , 1 9 8 7 . ( in
R u s s ia n ) .

[1 5 ] N .K o b lit z , A lg e b r a ic A s p e c t s o f Cr yp t o g r a p h y, S p r in g e r , B e r lin , 1 9 9 8 .

[1 6 ] 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 .

[1 7 ] 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 . A p p li-
c a t io n s o f Fin it e Fie ld s , 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 .

[1 8 ] F.J.Ma c W illia m s , N .J.A , S lo a n e . Th e t h e o r y o f e r r o r -c o r r e c t in g c o d e s , P a r t , B e ll L a b o -
r a t o r ie s Mu r r a y H ill, N J, U S A , N o r t h -H o lla n d P u b lis h in g Co m p a n y, A m s t e r d a m , N e w
Y o r k, Oxfo r d .

[1 9 ] G. Mc N a y, To p ic s in ¯ n it e ¯ e ld s , P h .D . Th e s is , U n ive r s it y o f Gla s g o w, 1 9 9 5 .

[2 0 ] H . Me yn ,\ E xp lic it N -p o lyn o m ia ls o f 2 -p o we r d e g r e e o ve r ¯ n it e ¯ e ld s " , D esigns Codes
Cryptogr, vo l. 6 , p p . 1 0 7 -1 1 6 , 1 9 9 5 .

[2 1 ] S . P e r lis , \ N o r m a l b a s e s o f c yc lic ¯ e ld s o f p r im e -p o we r d e g r e e " ,D uke M ath. J ., vo l. 9 ,
p p . 5 0 7 -5 1 7 , 1 9 4 2 .

[2 2 ] J.V o n z u r Ga t h e n , E . K a lt o fe n ,\ Fa c t o r iz a t io n o f m u lt iva r ia t e p o lyn o m ia ls o ve r ¯ n it e
¯ e ld s " , M ath.Comput, vo l.4 5 , p p . 2 5 1 -2 6 1 , 1 9 8 5 .

[2 3 ] 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 , p p . 3 3 4 - 3 3 6 , 1 9 8 4 .

¼áõÛ· µÝáõó·ñÇãáí ãµ»ñíáÕ µ³½Ù³Ý¹³ÙÝ»ñÇ µ³Õ³¹ñáõÃÛáõÝÝ»ñ
í»ñç³íáñ ¹³ßï»ñÇ íñ³

ê. Ø»Ññ³µÇ ¨ Ø. ÎÛáõñ»ÕÛ³Ý

²Ù÷á÷áõÙ

²Ûë ³ß˳ï³ÝùÁ Ý»ñϳ۳óÝáõÙ ¿ í»ñç³íáñ ¹³ßï»ñÇ íñ³ ½áõÛ· µÝáõó·ñÇãáí
ãµ»ñíáÕ µ³½Ù³Ý¹³ÙÝ»ñÇ ëÇÝï»½Ù³Ý ÏáÝëïñáõÏïÇí ï»ëáõÃÛ³Ý áñáß ³ñ¹ÛáõÝùÝ»ñ:
Ø»Ýù ³å³óáõó»É »Ýù ûáñ»Ù, áñÁ Ù»Í ¹»ñ ¿ ˳ÕáõÙ ãµ»ñíáÕ µ³½Ù³Ý¹³ÙÝ»ñ
ϳéáõó»Éáõó: ²Ûë ûáñ»ÙÇ û·ÝáõÃÛ³Ùµ ³é³ç³ñÏíáõÙ ¿ n2 k ( k = 1 ; 2 :::) ³ëïÇ׳ÝÇ
ãµ»ñíáÕ µ³½Ù³Ý¹³Ù ϳéáõó»Éáõ é»Ïáõé»Ýï Ù»Ãá¹: