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


Mathematical Problems of Computer Science 36, 57{62, 2012.

Computation of the Complexity of some Recur sive

Constr ucted N or mal P olynomials

Ma h m o o d A liz a d e h

Islamic Azad University- Ahvaz Branch

E-mail: Alizadeh@iauahvaz.ac.ir

Abstract

In this paper we give some algorithms for computing the complexity of some nor-
mal polynomials constructed by some recurrent methods. Finally some results of our
algorithms are given in a table.

Keywords: Complexity, Irreducible Polynomial, Normal Polynomial.

Refer ences

[1 ] S . A b r a h a m ya n , \ S o m e c o n s t r u c t io n o f N-p o lyn o m ia ls o ve r ¯ n it e ¯ e ld s " , National
Academy of Sciences of Armenia R eports, vo l. 1 1 1 , n o . 3 , 2 3 2 -2 3 9 , 2 0 1 1 .

[2 ] M. A liz a d e h , \ S o m e a lg o r it h m s fo r n o r m a lit y t e s t in g ir r e d u c ib le p o lyn o m ia ls a n d c o m -
p u t in g c o m p le xit y o f t h e n o r m a l p o lyn o m ia ls o ve r ¯ n it e ¯ e ld s , Applied M athematical
Sciences, vo l. 6 , n o . 4 0 , 1 9 9 7 - 2 0 0 3 , 2 0 1 2 .

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

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

[5 ] M. K . K yu r e g ya n ," R e c u r s ive c o n s t r u c t io n s o f N -p o lyn o m ia ls o ve r GF ( 2 s ) " , D iscrete Ap-
plied M athematics, vo l. 1 5 6 , p p . 1 5 5 4 -1 5 5 9 , 2 0 0 8 .

[6 ] R . L id l a n d H . N ie d e r r e it e r . F inite F ields. Ca m b r id g e U n ive r s it y P r e s s , 1 9 8 7 .

[7 ] A . J. 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 a n d T. Y a g h o o b ia n ,
Applications of ¯nite ¯elds, 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 .

[8 ] H . Me yn , " E xp lic it N -p o lyn o m ia l 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
and Cryptography, vo l. 6 , p p . 1 4 7 -1 5 8 , 1 9 9 5 .

[9 ] R . Mu llin , I. On ys z c h u k, S . V a n s t o n e a n d R . W ils o n ,\ Op t im a l n o r m a l b a s e s in
GF ( pn )

n
" ,D iscreate Applied math.,vo l. 2 2 , ,1 4 9 -1 6 1 , 1 9 8 8 / 1 9 8 9 .

[1 0 ] J. Om u r a a n d J. Ma s s e y, \ Co m p u t a t io n a l m e t h o d a n d a p p a r a t u s fo r ¯ n it e ¯ e ld a r it h -
m a t ic " ,U .S . p a t e n t 4 ,5 8 6 ,6 2 7 , 1 9 8 6 .

[1 1 ] I. On ys z c h u k, R . Mu llin , a n d S . V a n s t o n e , \ Co m p u t a t io n a l m e t h o d a n d a p p a r a t u s fo r
m u lt ip lic a t io n " ,U .S p a t e n t 4 ,7 4 5 ,5 6 8 , 1 9 8 8 .

5 7



5 8 Computation of the Complexity of some Recursive Constructed Normal Polynomials

è»ÏáõñëÇí ϳéáõóí³Í áñáß ÝáñÙ³É µ³½Ù³Ý¹³ÙÝ»ñÇ
µ³ñ¹áõÃÛ³Ý Ñ³ßíáõÙÁ

Ø. ²ÑÉǽ³¹»Ñ

²Ù÷á÷áõÙ

²Ûë ³ß˳ï³ÝùáõÙ Ù»Ýù ³é³ç³ñÏáõÙ »Ýù áñáß³ÏÇ ³É·áñÇÃ٠ѳßí»Éáõ ѳٳñ áñáß
ÝáñÙ³É µ³½Ù³Ý¹³ÙÝ»ñÇ µ³ñ¹áõÃÛáõÝÁ, áñáÝù ϳéáõóí»É »Ý é»Ïáõñ»Ýï »Õ³Ý³ÏÝ»ñáí:
´»ñí³Í ¿ ³ÕÛáõë³Ï, áñáõÙ Ýßí³Í ¿ áñáß ³ñ¹ÛáõÝùÝ»ñ:

Âû÷èñëåíèå ñëîæíîñòè íåêîòîðûõ ðåêóðñèâíî
ïîñòðîåííûõ ïîëèíîìîâ

Ì. Àëèçàäå

Àííîòàöèÿ

 ýòîé ñòàòüå ìû ïðåäëàãàåì àëãîðèòìû âû÷èñëåíèÿ ñëîæíîñòè íîðìàëüíûõ
ïîëèíîìîâ, ïîñòðîåííûõ îïðåäåëåííûìè ðåêóððåíòíûìè ìåòîäàìè.

 çàêëþ÷åíèè ïðèâåäåíà òàáëèöà, êîòîðàÿ ñîäåðæèò íåêîòîðûå ðåçóëüòàòû.