MEMO ROUTING SLIP I NEYER USB FOR APPROVALS. DISAPPROVALS, 

CONCURRBNCBS, OR SIMILAR ACTIONS • 

1 NAME OR TITLE . <i /~~ - -~ INITIALS CIRCIJIATE 

ORGANIZATION AND LOCATidft ~ / '~. • ~ DATE COOR DINA-

'A • _.,. - - - , TION 

- 2 RLE 

INFORMATION 

3 NECESSARY 

ACTION 

NOTE AND 

RETURN 

4 SEE ME 

SIGNATURE 

REMARKS 

FROM rWIE ca mu ~-~A. . - ~/¥ ogf . 

n - ORGANIZATIOJI AID LOCATIOll /1- //7 . Md ;:ry/ 

@'pp roved for Release bv NSA on 10-30-2013 pursuant to E .0. 1352\3 
REF ID:A67570 

A METHOD FOR GENERA TING IRREDt1CIBJ.:E, POLYNOMIALS 

A. Gleason 

R. W. Marsh 

NSA-.314 

26 May 1955 

p. i 

It was observed ttat, if the polynomial r{x) • E o(' 1 x 

i"'O 

{coerticients in GF(2)) is irreducible and its root has•maximum period 

p p ~~ 

2 - 1, then the polynomial F{x) • E '-'i x is irreducible and its i~O . root has maximum period. This was verified in all cases up to P • 5. 

We shall give a proof that F is always irreducible but leave unsettled 

the question or whether its roots are primitive. 

Let K be a finite field or cardinal q (which must be a prime power 

and, in the case of particular interest, is 2). 'Let K* be a minimal 

algebraically closed field containing K. For each positive integer 

. U n 

n there is in K* a unique field Kn of degree n oyer K; K* • K • We 

my regard K* as an infinite dimensional vector space ov.er K; then each 

n of the fields K is a vector subspace. 

Let· o( be the mapping x-:) xq ot K* into itselt. 

n n 

Lemma 1. Se; K ~ o( a = e 

Proof: The tie1d If has qn elements, and the q

0 - l non-zero elements 

from a group unier multiplication. By the theorem of Lagrange every 

qn-1 element or this group satisfies the relation e . 1, whence every 

element or i1 satieties Bqn =e . This proves one halt or the lemma. 

n 

The polynomial xq - x can have at most qn roots in K*• Hence all 

ot the roots are in K°. This proves the second halt of the lenna. 
.#• REF ID:A67570 

The mapping o( is an automorphism of K.* since it evidently s~tisfies 

0( ( e c/' ) • o<C e )o< (ct' ) and bC ( g + tp ) *' o( ( 9 ) ~p(( cf ) because Cl 

is a power or the characteristic• We have seen that oe 9 • 0 if 

0 e K • K1 • Hence 0< is a linear transformation of K* regarded as a 

vector space over K. 

Lemma 2. If 8 £ K*• the degree of 9 is the least positive integer 

n for which 0( n e =e 

Proof: Obvious .from lemma. 1. 

pTheorem: Let t -= E bi xi be an irreducible polynomial of degree p 

i=O ,--p P q1-1 is an 

over K whose roots are prj.mitive in K • Then F • r bi x 

irreducible polynomial of degree qP - 1. i=-0 

Proof: Consider any root fi of F. Evidently 9 f. O. We have then 

o .. e FC e> • t b1 e qi • I~ b1 °' "s • re°'> e . i•O \1-0 ) 

The set or all polynomials P such that P( °') e • 0 is an ideal cf. 

in the polynomial ring over K. Since this ring is a principal ideal 

ring and & contains the irreducible polynomial t, ell. is either the 

uni4deal or the p~incipal ideal (£). The .former possibilit:r implies 

e .. 0 which is false, 80 c.€ ... (£). By lenma 2, the degree of e 

is the least integer n for which (O<n-1)~· o, that is, the leasi integer 

n for which -rl' - 1 E (f). Since the roots of t are primitive this 

integer is 2P - 1. 

The minimal polynomial tor e, 1s t.Aerefore an ineduri.bM po!Jrlomial 

ot degne / - l 'ldllch ~ '• Cblnparing degrees we see that the 
REF ID:A67570 

quotient-is in K, hence Fis irreducible. q.e.d. 

It mar be remarked t.~t. in case t does not' have primitive roots we' 

can see that F splits into irreducible factors or degree equal to the 

order or the root~ or t. 

Concerning· the second question as io whether F has primitive· roots 

in the case K • GF(2), it may b~ remarked that .it true we could then 

obtain an algebraic recursion ~iving only irreducible polynomial$ · 

_by iterat.ing the procedure.. Since this is closely related to a prime 

generating function, it is rather unlikely to be provable by' element~17 

methods, it true._. Starting with q • ), · K • GF(3), and the irreducible . 

. .' 2 

polynondal x - x - 1 which las primitive roots we obtain the irreducibl~ 

cS - 2 · ~-·;:. 

polynomial x ..... x - 1, whose roots have order 160, a tar cry from being. 

_primitive. This also indicates that any proof .would have to rely on 

number theoretic properties or the number 2. 

3