,*apt} #bb ,f9ite ,fields ,f9ite fields appe> 9 _m applica;ns ( algebra1 9clud+ cod+ !ory & cryptography4 ,we alr "k "o f9ite field1 _% `;,z;p _:1 ": .2;p is prime4 ,9 ? *apt} we w %{ t a unique f9ite field ( ord} _% p~n _: exi/s = e prime .2;p1 ": .2;n is a positive 9teg}4 ,f9ite fields >e al call$ ,galois fields 9 honor ( ,~/ev>i/e ,galois1 :o 0 "o ( ! f/ ma!maticians to 9ve/igate !m4 ,sec;n #bb4a ,/ructure ( a ,f9ite ,field ,recall t a field .2;,f has ~1"*i/ic .2;p if .2;p is ! smalle/ positive 9teg} s* t = e nonz}o ele;t _% .a _: 9 .2;,f1 we h _% p.a .k #0 _:4 ,if no s* 9teg} exi/s1 !n .2;,f has "*i/ic #j4 ,f ,!orem #af4ai we "k t .2;p m/ 2 prime4 ,suppose t .2;,f is a f9ite field ) .2;n ele;ts4 ,!n _% n.a .k #0 _: = all _% .a _: 9 .2;,f4 ,3sequ5tly1 ! "*i/ic ( .2;,f m/ 2 .2;p1 ": .2;p is a #ajbg prime divid+ .2;n4 ,? 4cus.n is summ>iz$ 9 ! foll{+ proposi;n4 7777777777777777777777777777777777777777 ,proposi;n #bb4a 4 ,if .2;,f is a f9ite field1 !n ! "*i/ic ( .2;,f is .2;p1 ": .2;p is prime4 gggggggggggggggggggggggggggggggggggggggg ,"?|t ? *apt} we w assume t .2;p is a prime numb} un.s o!rwise /at$4 7777777777777777777777777777777777777777 ,proposi;n #bb4b 4 ,if .2;,f is a f9ite field ( "*i/ic .2;p1 !n ! ord} ( .2;,f is _% p~n _: = "s _% n `e `;,n _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,let _% .f_3 `;,z $o ,f _: 2 ! r+ homomorphism def9$ by _% f(n) .k n*1 _:4 ,s9ce ! "*i/ic ( .2;,f is .2;p1 ! k}nel ( _% .f _: m/ 2 _% p`;,z _: & ! image ( _% .f _: m/ 2 a subfield ( .2;,f #ajbh isomorphic to _% `;,z;p _:4 ,we w d5ote ? subfield by .2;,k4 ,s9ce .2;,f is a f9ite field1 x m/ 2 a f9ite ext5.n ( .2;,k &1 "!=e1 an algebraic ext5.n ( .2;,k4 ,suppose t _% `(,f "1 ,k`) .k n _: is ! dim5.n ( .2;,f1 ": .2;,f is a .2;,k vector space4 ,"! m/ exi/ ele;ts _% .a1, ''', .a;n" `e ,f _: s* t any ele;t _% .a _: 9 .2;,f c 2 writt5 uniquely 9 ! =m _% .a .k a1.a1+''' +a;n".a;n _: 1 ": ! _% a;i _:'s >e 9 .2;,k4 ,s9ce "! >e .2;p ele;ts 9 .2;,k1 "! >e _% p~n _: possible l9e> comb9a;ns ( ! _% .a;i _:'s4 ,"!=e1 ! ord} ( .2;,f m/ 2 _% p~n _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,lemma #bb4c 4 ,fre%man's ,dr1m4 ,let .2;p 2 prime & .2;,d 2 an 9tegral doma9 ( "*i/ic .2;p4 ,!n _% a~p~~n~"+b~p~~n .k (a+b)~p~~n _: = all positive 9teg}s .2;n4 #ajbi gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,we w prove ? lemma us+ ma!matical 9duc;n on .2;n4 ,we c use ! b9omial =mula " to v}ify ! case = _% n .k #1 _:2 t is1 _% (a+b)~p .k ".,s%k .k #0able if x has .2;n 4t9ct roots 9 ! splitt+ field ( _% f(x) _:2 t is1 _% f(x) _: is sep>able :5 x factors 9to 4t9ct l9e> factors ov} ! splitt+ field ( .2;f4 ,an ext5.n .2;,e ( .2;,f is a ~1sep>able ~1ext5.n ( .2;,f if e ele;t 9 .2;,e is ! root ( a sep>able polynomial 9 _% ,f`(x`) _:4 7777777777777777777777777777777777777777 ,example #bb4d 4 ,! polynomial _% x~2"-2 _: is sep>able ov} _% `;,q _: s9ce x factors z _% (x->2})(x+>2}) _:4 ,9 fact1 _% `;,q(>2}) _: is a sep>able ext5.n ( _% `;,q _:4 ,let #ajca _% .a .k a+b>2} _: 2 any ele;t 9 _% `;,q(>2}) _:4 ,if _% b .k #0 _:1 !n _% .a _: is a root ( _% x-a _:4 ,if _% b /.k #0 _:1 !n _% .a _: is ! root ( ! sep>able polynomial _% x~2"-2ax+a~2"-2b~2 .k (x-(a+b>2}))(x-(a-b>2})) _: 4 gggggggggggggggggggggggggggggggggggggggg ,=tunately1 we h an easy te/ to det}m9e ! sep>abil;y ( any polynomial4 ,let _% f(x) .k a0+a1x+''' +a;n"x~n _: 2 any polynomial 9 _% ,f`(x`) _:4 ,def9e ! ~1d}ivative ( _% f(x) _: to 2 _% f~'"(x) .k a1+2a2x+''' +na;n"x~n-1 _: 4 7777777777777777777777777777777777777777 ,lemma #bb4e 4 ,let .2;,f 2 a field & _% f(x) `e ,f`(x`) _:4 ,!n _% f(x) _: is sep>able if & only if _% f(x) _: & _% f~'"(x) _: >e relatively prime4 #ajcb gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,let _% f(x) _: 2 sep>able4 ,!n _% f(x) _: factors ov} "s ext5.n field ( .2;,f z _% f(x) .k (x-.a1)(x-.a2) ''' (x-.a;n") _:1 ": _% .a;i /.k .a;j _: = _% i /.k j _:4 ,tak+ ! d}ivative ( _% f(x) _:1 we see t _% f~'"(x) .k (x-.a2) ''' (x-.a;n") +(x-.a1)(x-.a3) ''' (x-.a;n") + '''+(x-.a1) ''' (x-.a;n-1") _: 4 ,h;e1 _% f(x) _: & _% f~'"(x) _: c h no common factors4 ,to prove ! 3v}se1 we w %{ t ! 3trapositive ( ! /ate;t is true4 ,suppose t _% f(x) .k (x-.a)~k"g(x) _:1 ": _% k .1 #1 _:4 ,di6}5tiat+1 we h #ajcc _% f~'"(x) .k k(x-.a)~k-1"g(x)+(x-.a)~k"g~'"(x) _: 4 ,"!=e1 _% f(x) _: & _% f~'"(x) _: h a common factor4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,!orem #bb4f 4 ,= e prime .2;p & e positive 9teg} .2;n1 "! exi/s a f9ite field .2;,f ) _% p~n _: ele;ts4 ,fur!rmore1 any field ( ord} _% p~n _: is isomorphic to ! splitt+ field ( _% x~p~~n~"-x _: ov} _% `;,z;p _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,let _% f(x) .k x~p~~n~"-x _: & let .2;,f 2 ! splitt+ field ( _% f(x) _:4 ,!n by ,lemma #bb4e1 _% f(x) _: has _% p~n _: 4t9ct z}os 9 .2;,f1 s9ce _% f~'"(x) .k p~n"x~p~~n~-1"-1 .k -#1 _: is relatively prime to _% f(x) _:4 ,we claim t ! roots ( _% f(x) _: #ajcd =m a subfield ( .2;,f4 ,c}ta9ly #j & #a >e z}os ( _% f(x) _:4 ,if _% .a _: & _% .b _: >e z}os ( _% f(x) _:1 !n _% .a+.b _: & _% .a.b _: >e al z}os ( _% f(x) _:1 s9ce _% .a~p~~n~"+.b~p~~n .k (.a+.b)~p~~n _: & _% .a~p~~n~".b~p~~n .k (.a.b)~p~~n _:4 ,we al ne$ to %{ t ! additive 9v}se & ! multiplicative 9v}se ( ea* root ( _% f(x) _: >e roots ( _% f(x) _:4 ,= any z}o _% .a _: ( _% f(x) _:1 we "k t _% -.a _: is al a z}o ( _% f(x) _:1 s9ce _% f(-.a) .k (-.a)~p~~n~"-(-.a) .k -.a~p~~n~"+.a .k -(.a~p~~n~"-.a) .k #0 _: 1 provid$ .2;p is odd4 ,if _% p .k #2 _:1 !n _% f(-.a) .k (-.a)~2~~n~"-(-.a) .k .a+.a .k #0 _: 4 ,if _% .a /.k #0 _:1 !n _% (.a~-1")~p~~n .k (.a~p~~n~")~-1 .k .a~-1 _: 4 ,s9ce ! z}os ( _% f(x) _: =m a subfield ( .2;,f & _% f(x) _: splits 9 ? subfield1 ! subfield m/ 2 all ( #ajce .2;,f4 ,let .2;,e 2 any o!r field ( ord} _% p~n _:4 ,to %{ t .2;,e is isomorphic to .2;,f1 we m/ %{ t e ele;t 9 .2;,e is a root ( _% f(x) _:4 ,c}ta9ly #j is a root ( _% f(x) _:4 ,let _% .a _: 2 a nonz}o ele;t ( .2;,e4 ,! ord} ( ! multiplicative gr|p ( nonz}o ele;ts ( .2;,e is _% p~n"-1 _:2 h;e1 _% .a~p~~n~-1 .k #1 _: or _% .a~p~~n~"-.a .k #0 _:4 ,s9ce .2;,e 3ta9s _% p~n _: ele;ts1 .2;,e m/ 2 a splitt+ field ( _% f(x) _:2 h{"e1 by ,coroll>y #ba4cf1 ! splitt+ field ( any polynomial is unique up to isomorphism4 gggggggggggggggggggggggggggggggggggggggg ,! unique f9ite field ) _% p~n _: ele;ts is call$ ! ~1,galois ~1field ( ord} _% p~n _:4 ,we w d5ote ? field by _% ,,gf(p~n") _:4 7777777777777777777777777777777777777777 ,!orem #bb4g 4 ,e subfield ( ! ,galois field _% ,,gf(p~n") _: has _% p~m _: #ajcf ele;ts1 ": .2;m divides .2;n4 ,3v}sely1 if _% m|n _: = _% m .1 #0 _:1 !n "! exi/s a unique subfield ( _% ,,gf(p~n") _: isomorphic to _% ,,gf(p~m") _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,let .2;,f 2 a subfield ( _% ,e .k ,,gf(p~n") _:4 ,!n .2;,f m/ 2 a field ext5.n ( .2;,k t 3ta9s _% p~m _: ele;ts1 ": .2;,k is isomorphic to _% `;,z;p _:4 ,!n _% m|n _:1 s9ce _% `(,e "1 ,k`) .k `(,e "1 ,f`)`(,f "1 ,k`) _: 4 ,to prove ! 3v}se1 suppose t _% m|n _: = "s _% m .1 #0 _:4 ,!n _% p~m"-1 _: divides _% p~n"-1 _:4 ,3sequ5tly1 _% x~p~~m~-1"-1 _: divides _% x~p~~n~-1"-1 _:4 ,"!=e1 _% x~p~~m~"-x _: m/ divide _% x~p~~n~"-x _:1 & e z}o ( _% x~p~~m~"-x _: is al a z}o ( #ajcg _% x~p~~n~"-x _:4 ,?us1 _% ,,gf(p~n") _: 3ta9s1 z a subfield1 a splitt+ field ( _% x~p~~m~"-x _:1 : m/ 2 isomorphic to _% ,,gf(p~m") _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,example #bb4h 4 ,! lattice ( subfields ( _% ,,gf(p~24") _: is giv5 9 ,figure #bb4i4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,image ,,id3 f9ite-subfield-lattice ,descrip;n3 ,a lattice ( field 9clu.ns ) ! top level a ,galois field ( p`5#bd ele;ts4 ,! second level has ,galois fields ( p`5#h & p`5#ab ele;ts : >e 9clud$ 9 ! top level4 ,! ?ird level has ,galois fields ( p`5#d "<9clud$ 9 ! fields ( p`5#h & p`5#ab ele;ts"> & p`5#f ele;ts "<9clud$ 9 ! field ( p`5#ab ele;ts">4 ,! f|r? level has ,galois fields ( p`5#b "<9clud$ 9 ! #ajch fields ( p`5#d & p`5#af ele;ts"> & p`5#c ele;ts "<9clud$ 9 ! field ( p`5#f ele;ts">4 ,! bottom level a ,galois field ( ;p ele;ts "<9clud$ 9 ! fields ( p`5#b & p`5#c ele;ts">4 ,figure #bb4i 4 ,subfields ( _% ,,gf(p~24") _: gggggggggggggggggggggggggggggggggggggggg #ajci ,transcrib} note3 ! image ) ,,id f9ite-subfield-lattice 2l;gs "h4 ,replace ? page ) ! 9dep5d5tly g5}at$ tactile image4 #ajdj ,) ea* field .2;,f we h a multiplicative gr|p ( nonz}o ele;ts ( .2;,f : we w d5ote by _% ,f~`# _:4 ,! multiplicative gr|p ( any f9ite field is cyclic4 ,? result foll{s f ! m g5}al result t we w prove 9 ! next !orem4 7777777777777777777777777777777777777777 ,!orem #bb4aj 4 ,if .2;,g is a f9ite subgr|p ( _% ,f~`# _:1 ! multiplicative gr|p ( nonz}o ele;ts ( a field .2;,f1 !n .2;,g is cyclic4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,let .2;,g 2 a f9ite subgr|p ( _% ,f~`# _: ( ord} .2;n4 ,by ! ,funda;tal ,!orem ( ,f9ite ,abelian ,gr|ps "<,!orem #ac4d">1 _% ,g `:.k `;,z;p1;~e1`*''' `*`;,z;p;;k;~e;~;k _: 1 ": _% n .k p1~e1 ''' p;k~e~;k _: & ! _% p1, ''', p;k _: >e "ily 4t9ct"> primes4 ,let .2;m 2 ! l1/ #ajda common multiple ( _% p1~e1, ''', p;k~e~;k _:4 ,!n .2;,g 3ta9s an ele;t ( ord} .2;m4 ,s9ce e _% .a _: 9 .2;,g satisfies _% x~r"-1 _: = "s .2;r divid+ .2;m1 _% .a _: m/ al 2 a root ( _% x~m"-1 _:4 ,s9ce _% x~m"-1 _: has at mo/ .2;m roots 9 .2;,f1 _% n "k: m _:4 ,on ! o!r h&1 we "k t _% m "k: |,g| _:2 "!=e1 _% m .k n _:4 ,?us1 .2;,g 3ta9s an ele;t ( ord} .2;n & m/ 2 cyclic4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,coroll>y #bb4aa 4 ,! multiplicative gr|p ( all nonz}o ele;ts ( a f9ite field is cyclic4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,coroll>y #bb4ab 4 ,e f9ite ext5.n .2;,e ( a f9ite field .2;,f is a simple ext5.n ( .2;,f4 gggggggggggggggggggggggggggggggggggggggg #ajdb 7777777777777777777777777777777777777777 ,pro( 4 ,let _% .a _: 2 a g5}ator = ! cyclic gr|p _% ,e~`# _: ( nonz}o ele;ts ( .2;,e4 ,!n _% ,e .k ,f(.a) _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,example #bb4ac 4 ,! f9ite field _% ,,gf(2~4") _: is isomorphic to ! field _% `;,z2`(x`)_/..(1+x+x~4"..) _:4 ,"!=e1 ! ele;ts ( _% ,,gf(2~4") _: c 2 tak5 to 2 _% .(a0+a1.a+a2.a~2"+a3.a~3_3a;i" `e `;,z2 and #1+.a+.a~4" .k #0.) _: 4 ,rememb}+ t _% #1+.a+.a~4 .k #0 _:1 we add & multiply ele;ts ( _% ,,gf(2~4") _: exactly z we add & multiply polynomials4 ,! multiplicative gr|p ( _% ,,gf(2~4") _: is isomorphic to _% `;,z15 _: ) g5}ator _% .a _:3 #ajdc _% .a~1 .k .a .a~6 .k .a~2"+.a~3" .a~11 .k .a+.a~2"+.a~3" .a~2 .k .a~2" .a~7 .k #1+.a+.a~3" .a~12 .k #1+.a+.a~2"+.a~3" .a~3 .k .a~3" .a~8 .k #1+.a~2" .a~13 .k #1+.a~2"+.a~3" .a~4 .k #1+.a .a~9 .k .a+.a~3" .a~14 .k #1+.a~3" .a~5 .k .a+.a~2" .a~10 .k #1+.a+.a~2" .a~15 .k #1. _: gggggggggggggggggggggggggggggggggggggggg ,sec;n #bb4b ,polynomial ,codes ,) k ( polynomial r+s & f9ite fields1 x is n{ possible to d}ive m sophi/icat$ codes ?an ~? ( ,*apt} #h4 ,f/ let u recall t an _% (n, k) _:-block code 3si/s ( a "o-to-"o 5cod+ func;n _% ,e_3 `;,z2~k $o `;,z2~n _: & a decod+ func;n _% ,d_3 `;,z2~n $o `;,z2~k _:4 ,! code is }ror-correct+ if .2;,d is onto4 ,a code is a l9e> code if x is ! null space ( a matrix #ajdd _% ,h `e `;,m;k`*n"(`;,z2) _:4 ,we >e 9t}e/$ 9 a class ( codes "kn z cyclic codes4 ,let _% .f_3 `;,z2~k $o `;,z2~n _: 2 a b9>y _% (n, k) _:-block code4 ,!n _% .f _: is a ~1cyclic ~1code if = e code~w _% (a1, a2, ''', a;n") _:1 ! cyclically %ift$ .2;n-tuple _% (a;n, a1, a2, ''', a;n-1") _: is al a code~w4 ,cyclic codes >e "picul>ly easy to imple;t on a comput} us+ %ift regi/}s .<#b1 #c.>4 7777777777777777777777777777777777777777 ,example #bb4ad 4 ,3sid} ! _% (6, 3) _:-l9e> codes g5}at$ by ! two matrices #ajde _% ,g1 .k ,(#1 #0 #0,)and,g2 .k ,(#1 #0 #0,) ,(#0 #1 #0,) ,(#1 #1 #0,) ,(#0 #0 #1,) ,(#1 #1 #1,) ,(#1 #0 #0,) ,(#1 #1 #1,) ,(#0 #1 #0,) ,(#0 #1 #1,) ,(#0 #0 #1,) ,(#0 #0 #1,) _: 4 ,messages 9 ! f/ code >e 5cod$ z foll{s3 #ajdf _% (000) $|33o (000000) (100) $|33o (100100) (001) $|33o (001001) (101) $|33o (101101) (010) $|33o (010010) (110) $|33o (110110) (011) $|33o (011011) (111) $|33o (111111). _: ,x is easy to see t ! code~ws =m a cyclic code4 ,9 ! second code1 #c-tuples >e 5cod$ 9 ! foll{+ mann}3 _% (000) $|33o (000000) (100) $|33o (111100) (001) $|33o (001111) (101) $|33o (110011) (010) $|33o (011110) (110) $|33o (100010) (011) $|33o (010001) (111) $|33o (101101). _: ,? code _c 2 cyclic1 s9ce _% (101101) _: is a code~w b _% (011011) _: is n #ajdg a code~w4 gggggggggggggggggggggggggggggggggggggggg ,subsec;n ,polynomial ,codes ,we wd l to f9d an easy me?od ( obta9+ cyclic l9e> codes4 ,to a3ompli% ?1 we c use |r k ( f9ite fields & polynomial r+s ov} _% `;,z2 _:4 ,any b9>y .2;n-tuple c 2 9t}pret$ z a polynomial 9 _% `;,z2`(x`) _:4 ,/at$ ano!r way1 ! .2;n-tuple _% (a0, a1, ''', a;n-1") _: corresponds to ! polynomial _% f(x) .k a0+a1x+''' +a;n-1"x~n-1 _: 1 ": ! degree ( _% f(x) _: is at mo/ _% n-1 _:4 ,= example1 ! polynomial correspond+ to ! #e-tuple _% (10011) _: is _% #1+0x+0x~2"+1x~3"+1x~4 .k #1+x~3"+x~4 _: 4 ,3v}sely1 ) any polynomial _% f(x) `e `;,z2`(x`) _: ) _% deg f(x) "k n _: we c associate a b9>y .2;n-tuple4 ,! polynomial _% x+x~2"+x~4 _: corresponds to ! #e-tuple _% (01101) _:4 #ajdh ,let u fix a noncon/ant polynomial _% g(x) _: 9 _% `;,z2`(x`) _: ( degree _% n-k _:4 ,we c def9e an _% (n, k) _:-code .2;,c 9 ! foll{+ mann}4 ,if _% (a0, ''', a;k-1") _: is a .2;k-tuple to 2 5cod$1 !n _% f(x) .k a0+a1x+''' +a;k-1"x~k-1 _: is ! correspond+ polynomial 9 _% `;,z2`(x`) _:4 ,to 5code _% f(x) _:1 we multiply by _% g(x) _:4 ,! code~ws 9 .2;,c >e all ~? polynomials 9 _% `;,z2`(x`) _: ( degree less ?an .2;n t >e divisible by _% g(x) _:4 ,codes obta9$ 9 ? mann} >e call$ ~1polynomial ~1codes~'4 7777777777777777777777777777777777777777 ,example #bb4ae 4 ,if we let _% g(x) .k #1+x~3 _:1 we c def9e a _% (6, 3) _:-code .2;,c z foll{s4 ,to 5code a #c-tuple _% (a0, a1, a2) _:1 we multiply ! correspond+ polynomial _% f(x) .k a0+a1x+a2x~2 _: by _% #1+x~3 _:4 ,we >e def9+ a map _% .f_3 `;,z2~3 $o `;,z2~6 _: by #ajdi _% .f_3 f(x) $|33o g(x)f(x) _:4 ,x is easy to *eck t ? map is a gr|p homomorphism4 ,9 fact1 if we reg>d _% `;,z2~n _: z a vector space ov} _% `;,z2 _:1 _% .f _: is a l9e> trans=ma;n ( vector spaces "4 ,let u compute ! k}nel ( _% .f _:4 ,obs}ve t _% f(a0, a1, a2) .k (000000) _: exactly :5 _% #0+0x+0x~2"+0x~3"+0x~4"+0x~5" .k (1+x~3")(a0+a1x+a2x~2") .k a0+a1x+a2x~2"+a0x~3"+a1x~4"+a2x~5 _: 4 ,s9ce ! polynomials ov} a field =m an 9tegral doma91 _% a0+a1x+a2x~2 _: m/ 2 ! z}o polynomial4 ,"!=e1 _% ker .f .k .((000).) _: & _% .f _: is "o-to-"o4 ,to calculate a g5}ator matrix = .2;,c1 we m}ely ne$ to exam9e ! way ! polynomials #a1 .2;x1 & _% x~2 _: >e 5cod$3 #ajej _% (1+x~3")*1 .k #1+x~3" (1+x~3")x .k x+x~4" (1+x~3")x~2" .k x~2"+x~5 _: 4 ,we obta9 ! code correspond+ to ! g5}ator matrix _% ,g1 _: 9 ,example #bb4ad4 ,! p>;y-*eck matrix = ? code is _% ,h .k ,(#1 #0 #0 #1 #0 #0,) ,(#0 #1 #0 #0 #1 #0,) ,(#0 #0 #1 #0 #0 #1,) _: 4 ,s9ce ! smalle/ weie isomorphic z vector spaces4 ,we w (t5 id5tify ele;ts 9 _% `;,z2~n _: ) ele;ts 9 _% `;,z`(x`)_/..(x~n"-1..) _:4 ,9 ? mann} we c 9t}pret a l9e> code z a subset ( _% `;,z`(x`)_/..(x~n"-1..) _:4 ,! addi;nal r+ /ructure on polynomial codes is v p{};l 9 describ+ cyclic codes4 ,a cyclic %ift ( an .2;n-tuple c 2 describ$ by polynomial multiplica;n4 ,if _% f(t) .k a0+a1t+''' +a;n-1"t~n-1 _: is a code polynomial 9 _% ,r;n _:1 !n _% tf(t) .k a;n-1"+a0t+''' +a;n-2"t~n-1 _: is ! cyclically %ift$ ~w obta9$ f multiply+ _% f(t) _: by .2;t4 ,! foll{+ !orem gives a b1uti;l classifica;n ( cyclic codes 9 t}ms ( ! id1ls ( #ajeb _% ,r;n _:4 7777777777777777777777777777777777777777 ,!orem #bb4af 4 ,a l9e> code .2;,c 9 _% `;,z2~n _: is cyclic if & only if x is an id1l 9 _% ,r;n .k `;,z`(x`)_/..(x~n"-1..) _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,let .2;,c 2 a l9e> cyclic code & suppose t _% f(t) _: is 9 .2;,c4 ,!n _% tf(t) _: m/ al 2 9 .2;,c4 ,3sequ5tly1 _% t~k"f(t) _: is 9 .2;,c = all _% k `e `;,n _:4 ,s9ce .2;,c is a l9e> code1 any l9e> comb9a;n ( ! code~ws _% f(t), tf(t), t~2"f(t), ''', t~n-1"f(t) _: is al a code~w2 "!=e1 = e polynomial _% p(t) _:1 _% p(t)f(t) _: is 9 .2;,c4 ,h;e1 .2;,c is an id1l4 ,3v}sely1 let .2;,c 2 an id1l 9 _% `;,z2`(x`)_/..(x~n"+1..) _:4 ,suppose t _% f(t) .k a0+a1t+''' +a;n-1"t~n-1 _: is a code~w 9 .2;,c4 ,!n _% tf(t) _: is a code~w 9 .2;,c2 t is1 #ajec _% (a1, ''', a;n-1, a0) _: is 9 .2;,c4 gggggggggggggggggggggggggggggggggggggggg ,!orem #bb4af tells u t "k+ ! id1ls ( _% ,r;n _: is equival5t to "k+ ! l9e> cyclic codes 9 _% `;,z2~n _:4 ,=tunately1 ! id1ls 9 _% ,r;n _: >e easy to describe4 ,! natural r+ homomorphism _% .f_3 `;,z2`(x`) $o ,r;n _: def9$ by _% f`(f(x)`) .k f(t) _: is a surjective homomorphism4 ,! k}nel ( _% .f _: is ! id1l g5}at$ by _% x~n"-1 _:4 ,by ,!orem #af4cd1 e id1l .2;,c 9 _% ,r;n _: is ( ! =m _% f(,i) _:1 ": .2,i is an id1l 9 _% `;,z2`(x`) _: t 3ta9s _% ..(x~n"-1..) _:4 ,by ,!orem #ag4bj1 we "k t e id1l .2,i 9 _% `;,z2`(x`) _: is a pr9cipal id1l1 s9ce _% `;,z2 _: is a field4 ,"!=e1 _% ,i .k ..(g(x)..) _: = "s unique monic polynomial 9 _% `;,z2`(x`) _:4 ,s9ce _% ..(x~n"-1..) _: is 3ta9$ 9 .2,i1 x m/ 2 ! case t _% g(x) _: divides _% x~n"-1 _:4 ,3sequ5tly1 e id1l .2;,c 9 _% ,r;n _: is ( ! =m #ajed _% ,c .k ..(g(t)..) .k .(f(t)g(t)_3f(t) `e ,r;n" and g(x)|(x~n"-1) in `;,z2`(x`).) _: 4 ,! unique monic polynomial ( ! smalle/ degree t g5}ates .2;,c is call$ ! ~7m9imal g5}ator polynomial~' ( .2;,c4 7777777777777777777777777777777777777777 ,example #bb4ag 4 ,if we factor _% x~7"-1 _: 9to irr$ucible compon5ts1 we h _% x~7"-1 .k (1+x)(1+x+x~3")(1+x~2"+x~3") _: 4 ,we see t _% g(t) .k (1+t+t~3") _: g5}ates an id1l .2;,c 9 _% ,r7 _:4 ,? code is a _% (7, 4) _:-block code4 ,z 9 ,example #bb4ae1 x is easy to calculate a g5}ator matrix by exam9+ :at _% g(t) _: does to ! polynomials #a1 .2;t1 _% t~2 _:1 & _% t~3 _:4 ,a g5}ator matrix = .2;,c is #ajee _% ,g .k ,(#1 #0 #0 #0,) ,(#1 #1 #0 #0,) ,(#0 #1 #1 #0,) ,(#1 #0 #1 #1,) ,(#0 #1 #0 #1,) ,(#0 #0 #1 #0,) ,(#0 #0 #0 #1,) _: 4 gggggggggggggggggggggggggggggggggggggggg ,9 g5}al1 we c det}m9e a g5}ator matrix = an _% (n, k) _:-code .2;,c by ! mann} 9 : ! ele;ts _% t~k _: >e 5cod$4 ,let _% x~n"-1 .k g(x)h(x) _: 9 _% `;,z2`(x`) _:4 ,if _% g(x) .k g0+g1x+''' +g;n-k"x~n-k _: & _% h(x) .k h0+h1x+''' +h;k"x~k _:1 !n ! _% n`*k _: matrix #ajef _% ,g .k ,(g0 #0 ''' #0 ,) ,(g1 g0 ''' #0 ,) ,(''' ''' ''' ''' ,) ,(g;n-k" g;n-k-1" ''' g0 ,) ,(#0 g;n-k" ''' g1 ,) ,(''' ''' ''' ''' ,) ,(#0 #0 ''' g;n-k,) _: is a g5}ator matrix = ! code .2;,c ) g5}ator polynomial _% g(t) _:4 ,! p>;y-*eck matrix = .2;,c is ! _% (n-k)`*n _: matrix _% ,h .k ,(#0 ''' #0 #0 h;k" ''' h0 ,) ,(#0 ''' #0 h;k" ''' h0 #0 ,) ,(''' ''' ''' ''' ''' ''' ''',) ,(h;k" ''' h0 #0 #0 ''' #0 ,) _: 4 ,we w l1ve ! details ( ! pro( ( ! foll{+ proposi;n z an ex}cise4 7777777777777777777777777777777777777777 ,proposi;n #bb4ah 4 ,let _% ,c .k ..(g(t)..) _: 2 a cyclic code 9 _% ,r;n _: & suppose t #ajeg _% x~n"-1 .k g(x)h(x) _:4 ,!n .2;,g & .2;,h >e g5}ator & p>;y-*eck matrices = .2;,c1 respectively4 ,fur!rmore1 _% ,h,g .k #0 _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,example #bb4ai 4 ,9 ,example #bb4ag1 _% x~7"-1 .k g(x)h(x) .k (1+x+x~3")(1+x+x~2"+x~4") _: 4 ,"!=e1 a p>;y-*eck matrix = ? code is _% ,h .k ,(#0 #0 #1 #0 #1 #1 #1,) ,(#0 #1 #0 #1 #1 #1 #0,) ,(#1 #0 #1 #1 #1 #0 #0,) _: 4 gggggggggggggggggggggggggggggggggggggggg ,to det}m9e ! }ror-detect+ & }ror-correct+ capabilities ( a cyclic code1 we ne$ to "k "s?+ ab det}m9ants4 ,if _% .a1, ''', .a;n _: >e ele;ts 9 a field .2;,f1 !n ! _% n`*n _: #ajeh matrix _% ,(#1 #1 ''' #1 ,) ,(.a1 .a2 ''' .a;n" ,) ,(.a1~2" .a2~2" ''' .a;n~2" ,) ,(''' ''' ''' ''' ,) ,(.a1~n-1" .a2~n-1" ''' .a;n~n-1,) _: is call$ ! ~1,v&}monde ~1matrix~'4 ,! det}m9ant ( ? matrix is call$ ! ~1,v&}monde ~1det}m9ant~'4 ,we w ne$ ! foll{+ lemma 9 |r 9ve/iga;n ( cyclic codes4 7777777777777777777777777777777777777777 ,lemma #bb4bj 4 ,let _% .a1, ''', .a;n _: 2 ele;ts 9 a field .2;,f ) _% n .1: #2 _:4 ,!n _% det ,(#1 #1 ''' #1 ,) .k "%#1 "k: j "k i "k: n}(.a;i"-.a;j") ,(.a1 .a2 ''' .a;n" ,) ,(.a1~2" .a2~2" ''' .a;n~2" ,) ,(''' ''' ''' ''' ,) ,(.a1~n-1" .a2~n-1" ''' .a;n~n-1,) _: #ajei 4 ,9 "picul>1 if ! _% .a;i _:'s >e 4t9ct1 !n ! det}m9ant is nonz}o4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,we w 9duct on .2;n4 ,if _% n .k #2 _:1 !n ! det}m9ant is _% .a2-.a1 _:4 ,let u assume ! result = _% n-1 _: & 3sid} ! polynomial _% p(x) _: def9$ by _% p(x) .k det ,(#1 #1 ''' #1 #1 ,) ,(.a1 .a2 ''' .a;n-1" x ,) ,(.a1~2" .a2~2" ''' .a;n-1~2" x~2" ,) ,(''' ''' ''' ''' ''' ,) ,(.a1~n-1" .a2~n-1" ''' .a;n-1~n-1" x~n-1,) _: 4 ,exp&+ ? det}m9ant by cofactors on ! la/ column1 we see t _% p(x) _: #ajfj is a polynomial ( at mo/ degree _% n-1 _:4 ,moreov}1 ! roots ( _% p(x) _: >e _% .a1, ''', .a;n-1 _:1 s9ce ! sub/itu;n ( any "o ( ~! ele;ts 9 ! la/ column w produce a column id5tical to ! la/ column 9 ! matrix4 ,rememb} t ! det}m9ant ( a matrix is z}o if x has two id5tical columns4 ,"!=e1 _% p(x) .k (x-.a1)(x-.a2) ''' (x-.a;n-1").b _: 1 ": _% .b .k (-1)~n+n"det ,(#1 #1 ''' #1 ,) ,(.a1 .a2 ''' .a;n-1" ,) ,(.a1~2" .a2~2" ''' .a;n-1~2" ,) ,(''' ''' ''' ''' ,) ,(.a1~n-2" .a2~n-2" ''' .a;n-1~n-2,) _: 4 ,by |r 9duc;n hypo!sis1 #ajfa _% .b .k (-1)~n+n""%#1 "k: j "k i "k: n-1}(.a;i"-.a;j") _: 4 ,if we let _% x .k .a;n _:1 ! result n{ foll{s immly4 gggggggggggggggggggggggggggggggggggggggg ,! foll{+ !orem gives u an e/imate on ! }ror detec;n & correc;n capabilities = a "picul> g5}ator polynomial4 7777777777777777777777777777777777777777 ,!orem #bb4ba 4 ,let _% ,c .k ..(g(t)..) _: 2 a cyclic code 9 _% ,r;n _: & suppose t _% .w _: is a primitive .2n? root ( un;y ov} _% `;,z2 _:4 ,if .2;s 3secutive p{}s ( _% .w _: >e roots ( _% g(x) _:1 !n ! m9imum 4t.e ( .2;,c is at l1/ _% s+1 _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,suppose t _% g(.w~r") .k g(.w~r+1) .k ''' .k g(.w~r+s-1") .k #0 _: 4 ,let _% f(x) _: 2 "s polynomial #ajfb 9 .2;,c ) .2;s or few} nonz}o coe6ici5ts4 ,we c assume t _% f(x) .k a;i0"x~i0"+a;i1"x~i1+''' +a;i;;s-1;"x~i~;s-1 _: 2 "s polynomial 9 .2;,c4 ,x w su6ice to %{ t all ( ! _% a;i _:'s m/ 2 #j4 ,s9ce _% g(.w~r") .k g(.w~r+1) .k ''' .k g(.w~r+s-1") .k #0 _: & _% g(x) _: divides _% f(x) _:1 _% f(.w~r") .k f(.w~r+1) .k ''' .k f(.w~r+s-1") .k #0 _: 4 ,equival5tly1 we h ! foll{+ sy/em ( equa;ns3 _% a;i0"(.w~r")~i0"+a;i1"(.w~r")~i1+''' +a;i;;s-1;"(.w~r")~i~;s-1~" .k #0 a;i0"(.w~r+1")~i0"+a;i1"(.w~r+1")~i2+''' +a;i;;s-1;"(.w~r+1")~i~;s-1~" .k #0 ''' a;i0"(.w~r+s-1")~i0"+a;i1"(.w~r+s-1")~i- 1+''' +a;i;;s-1;"(.w~r+s-1")~i~;s-1~" .k #0 _: #ajfc 4 ,"!=e1 _% (a;i0, a;i1, ''', a;i;;s-1;") _: is a solu;n to ! homog5e|s sy/em ( l9e> equa;ns _% (.w~i0")~r"x0+(.w~i1")~r"x1+''' +(.w~i~;s-1~")~r"x;n-1" .k #0 (.w~i0")~r+1"x0+(.w~i1")~r+1"x1+''' +(.w~i~;s-1~")~r+1"x;n-1" .k #0 ''' (.w~i0")~r+s-1"x0+(.w~i1")~r+s-1"x1+''' +(.w~i~;s-1~")~r+s-1"x;n-1" .k #0 _: 4 ,h{"e1 ? sy/em has a unique solu;n1 s9ce ! det}m9ant ( ! matrix #ajfd _% ,((.w~i0")~r" (.w~i1")~r" ''' (.w~i~;s-1~")~r" ,) ,((.w~i0")~r+1" (.w~i1")~r+1" ''' (.w~i~;s-1~")~r+1" ,) ,(''' ''' ''' ''' ,) ,((.w~i0")~r+s-1" (.w~i1")~r+s-1" ''' (.w~i~;s-1~")~r+s-1,) _: c 2 %{n to 2 nonz}o us+ ,lemma #bb4bj & ! basic prop}ties ( det}m9ants "<,ex}cise">4 ,"!=e1 ? solu;n m/ 2 _% a;i0 .k a;i1 .k ''' .k a;i;;s-1 .k #0 _:4 gggggggggggggggggggggggggggggggggggggggg ,subsec;n ,,b* ,codes ,"s ( ! mo/ important codes1 4cov}$ 9dep5d5tly by ,a4 ,hocqu5e ,,b* codes4 ,! ,europ1n & transatlantic communica;n sy/ems bo? use ,,b* codes4 ,9=ma;n ~ws to 2 5cod$ >e ( l5g? #bca1 & a #ajfe polynomial ( degree #bd is us$ to g5}ate ! code4 ,s9ce _% #231+24 .k #255 .k #2~8"-1 _:1 we >e d1l+ ) a _% (255, 231) _:-block code4 ,? ,,b* code w detect six }rors & has a failure rate ( #a 9 #af million4 ,"o advantage ( ,,b* codes is t e6ici5t }ror correc;n algori?ms exi/ = !m4 ,! idea 2h ,,b* codes is to *oose a g5}ator polynomial ( smalle/ degree t has ! l>ge/ }ror detec;n & }ror correc;n capabilities4 ,let _% d .k #2r+1 _: = "s _% r .1: #0 _:4 ,suppose t _% .w _: is a primitive .2n? root ( un;y ov} _% `;,z2 _:1 & let _% m;i"(x) _: 2 ! m9imal polynomial ov} _% `;,z2 _: ( _% .w~i _:4 ,if _% g(x) .k lcm`(m1(x), m2(x), ''', m;2r"(x)`) _: 1 !n ! cyclic code _% ..(g(t)..) _: 9 _% ,r;n _: is call$ ! ,,b* ~7code ( l5g?~' .2;n ~1& ~14t.e .2;d4 ,by ,!orem #bb4ba1 ! m9imum 4t.e ( .2;,c is at l1/ .2;d4 #ajff 7777777777777777777777777777777777777777 ,!orem #bb4bb 4 ,let _% ,c .k ..(g(t)..) _: 2 a cyclic code 9 _% ,r;n _:4 ,! foll{+ /ate;ts >e equival5t4 #a4 ,! code .2;,c is a ,,b* code ~: m9imum 4t.e is at l1/ .2;d4 #b4 ,a code polynomial _% f(t) _: is 9 .2;,c if & only if _% f(.w~i") .k #0 _: = _% #1 "k: i "k d _:4 #c4 ,! matrix _% ,h .k ,(#1 .w .w~2" ''' .w~n-1" ,) ,(#1 .w~2" .w~4" ''' .w~(n-1)(2)",) ,(#1 .w~3" .w~6" ''' .w~(n-1)(3)",) ,(''' ''' ''' ''' ''' ,) ,(#1 .w~2r" .w~4r" ''' .w~(n-1)(2r),) _: #ajfg is a p>;y-*eck matrix = .2;,c4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 "<#a"> _% $33oo _: "<#b">4 ,if _% f(t) _: is 9 .2;,c1 !n _% g(x)|f(x) _: 9 _% `;,z2`(x`) _:4 ,h;e1 = _% i .k #1, ''', #2r _:1 _% f(.w~i") .k #0 _: s9ce _% g(.w~i") .k #0 _:4 ,3v}sely1 suppose t _% f(.w~i") .k #0 _: = _% #1 "k: i "k: d _:4 ,!n _% f(x) _: is divisible by ea* _% m;i"(x) _:1 s9ce _% m;i"(x) _: is ! m9imal polynomial ( _% .w~i _:4 ,"!=e1 _% g(x)|f(x) _: by ! def9i;n ( _% g(x) _:4 ,3sequ5tly1 _% f(x) _: is a code~w4 "<#b"> _% $33oo _: "<#c">4 ,let _% f(t) .k a0+a1t+''' +a;n-1"vt~n-1 _: 2 9 _% ,r;n _:4 ,! correspond+ .2;n-tuple 9 _% `;,z2~n _: is _% _;x .k (a0a1 ''' a;n-1")~t _:4 ,by "<#b">1 #ajfh _% ,h_;x .k ,(a0+a1.w+''' +a;n-1".w~n-1" ,) .k ,(f(.w) ,) .k #0 ,(a0+a1.w~2+''' +a;n-1"(.w~2")~n-1" ,) ,(f(.w~2") ,) ,(''' ,) ,(''' ,) ,(a0+a1.w~2r+''' +a;n-1"(.w~2r")~n-1,) ,(f(.w~2r"),) _: exactly :5 _% f(t) _: is 9 .2;,c4 ,?us1 .2;,h is a p>;y-*eck matrix = .2;,c4 "<#c"> _% $33oo _: "<#a">4 ,by "<#c">1 a code polynomial _% f(t) .k a0+a1t+''' +a;n-1"t~n-1 _: is 9 .2;,c exactly :5 _% f(.w~i") .k #0 _: = _% i .k #1, ''', #2r _:4 ,! smalle/ s* polynomial is _% g(t) .k lcm`(m1(t), ''', m;2r"(t)`) _:4 ,"!=e1 _% ,c .k ..(g(t)..) _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,example #bb4bc 4 ,x is easy to v}ify t #ajfi _% x~15"-1 `e `;,z2`(x`) _: has a factoriza;n _% x~15"-1 .k (x+1)(x~2"+x+1)(x~4"+x+1)(x~4"+x~3"+1)(- x~4"+x~3"+x~2"+x+1) _: 1 ": ea* ( ! factors is an irr$ucible polynomial4 ,let _% .w _: 2 a root ( _% #1+x+x~4 _:4 ,! ,galois field _% ,,gf(2~4") _: is _% .(a0+a1.w+a2.w~2"+a3.w~3_3a;i" `e `;,z2 and #1+.w+.w~4" .k #0.) _: 4 ,by ,example #bb4h1 _% .w _: is a primitive #aeth root ( un;y4 ,! m9imal polynomial ( _% .w _: is _% m1(x) .k #1+x+x~4 _:4 ,x is easy to see t _% .w~2 _: & _% .w~4 _: >e al roots ( _% m1(x) _:4 ,! m9imal polynomial ( _% .w~3 _: is _% m2(x) .k #1+x+x~2"+x~3"+x~4 _:4 ,"!=e1 _% g(x) .k m1(x)m2(x) .k #1+x~4"+x~6"+x~7"+x~8 _: has roots _% .w _:1 _% .w~2 _:1 _% .w~3 _:1 _% .w~4 _:4 ,s9ce bo? _% m1(x) _: & _% m2(x) _: divide #ajgj _% x~15"-1 _:1 ! ,,b* code is a _% (15, 7) _:-code4 ,if _% x~15"-1 .k g(x)h(x) _:1 !n _% h(x) .k #1+x~4"+x~6"+x~7 _:2 "!=e1 a p>;y-*eck matrix = ? code is _% ,(#0 #0 #0 #0 #0 #0 #0 #1 #1 #0 #1 #0 #0 #0 #1,) ,(#0 #0 #0 #0 #0 #0 #1 #1 #0 #1 #0 #0 #0 #1 #0,) ,(#0 #0 #0 #0 #0 #1 #1 #0 #1 #0 #0 #0 #1 #0 #0,) ,(#0 #0 #0 #0 #1 #1 #0 #1 #0 #0 #0 #1 #0 #0 #0,) ,(#0 #0 #0 #1 #1 #0 #1 #0 #0 #0 #1 #0 #0 #0 #0,) ,(#0 #0 #1 #1 #0 #1 #0 #0 #0 #1 #0 #0 #0 #0 #0,) ,(#0 #1 #1 #0 #1 #0 #0 #0 #1 #0 #0 #0 #0 #0 #0,) ,(#1 #1 #0 #1 #0 #0 #0 #1 #0 #0 #0 #0 #0 #0 #0,) _: 4 #ajga gggggggggggggggggggggggggggggggggggggggg ,sage4 ,f9ite fields >e important 9 a v>iety ( appli$ 4cipl9es1 s* z cryptography & cod+ !ory "4 ,sage has excell5t support = f9ite fields all{+ = a wide v>iety ( computa;ns4 ,r1d+ ,"qs #bb4c ,r1d+ ,"qs #a 4 ,:5 is a field ext5.n sep>able8 #b 4 ,:at >e ! possible ord}s = subfields ( a f9ite field8 #c 4 ,:at is ! /ructure ( ! non-z}o ele;ts ( a f9ite field8 #d 4 ,provide a "*iza;n ( f9ite fields us+ ! 3cept ( a splitt+ field4 #e 4 ,:y is a !orem 9 ? *apt} titl$ 8,! ,fre%man's ,dr1m80 ,ex}cises #bb4d ,ex}cises #a 4 ,calculate ea* ( ! foll{+4 #ajgb a4 _% `(,,gf(3~6) "1 ,,gf(3~3")`) _: ;b4 _% `(,,gf(128) "1 ,,gf(16)`) _: ;c4 _% `(,,gf(625) "1 ,,gf(25)`) _: ;d4 _% `(,,gf(p~12) "1 ,,gf(p~2")`) _: #b 4 ,calculate _% `(,,gf(p~m) "1 ,,gf(p~n")`) _:1 ": _% n|m _:4 #c 4 ,:at is ! lattice ( subfields = _% ,,gf(p~30") _:;8 #d 4 ,let _% .a _: 2 a z}o ( _% x~3"+x~2"+1 _: ov} _% `;,z2 _:4 ,3/ruct a f9ite field ( ord} #h4 ,%{ t _% x~3"+x~2"+1 _: splits 9 _% `;,z2(.a) _:4 #e 4 ,3/ruct a f9ite field ( ord} #bg4 #f 4 ,prove or 4prove3 _% `;,q~`# _: is cyclic4 #g 4 ,factor ea* ( ! foll{+ #ajgc polynomials 9 _% `;,z2`(x`) _:4 a4 _% x~5"-1 _: ;b4 _% x~6"+x~5"+x~4"+x~3"+x~2"+x+1 _: ;c4 _% x~9"-1 _: ;d4 _% x~4"+x~3"+x~2"+x+1 _: #h 4 ,prove or 4prove3 _% `;,z2`(x`)_/..(x~3"+x+1..) `:.k `;,z2`(x`)_/..(x~3"+x~2"+1..) _: 4 #i 4 ,det}m9e ! numb} ( cyclic codes ( l5g? .2;n = _% n .k #6, #7, #8, #10 _:4 #aj 4 ,prove t ! id1l _% ..(t+1..) _: 9 _% ,r;n _: is ! code 9 _% `;,z2~n _: 3si/+ ( all ~ws ( ev5 p>;y4 #aa 4 ,3/ruct all ,,b* codes ( a4 l5g? #g4 ;b4 l5g? #ae4 #ajgd #ab 4 ,prove or 4prove3 ,"! exi/s a f9ite field t is algebraically clos$4 #ac 4 ,let .2;p 2 prime4 ,prove t ! field ( ra;nal func;ns _% `;,z;p"(x) _: is an 9f9ite field ( "*i/ic .2;p4 #ad 4 ,let .2;,d 2 an 9tegral doma9 ( "*i/ic .2;p4 ,prove t _% (a-b)~p~~n .k a~p~~n~"-b~p~~n _: = all _% a, b `e ,d _:4 #ae 4 ,%{ t e ele;t 9 a f9ite field c 2 writt5 z ! sum ( two squ>es4 #af 4 ,let .2;,e & .2;,f 2 subfields ( a f9ite field .2;,k4 ,if .2;,e is isomorphic to .2;,f1 %{ t _% ,e .k ,f _:4 #ag 4 ,let _% ,f _"k ,e _"k ,k _: 2 fields4 ,if .2;,k is a sep>able ext5.n ( .2;,f1 %{ t .2;,k is al sep>able ext5.n ( .2;,e4 #ajge #ah 4 ,let .2;,e 2 an ext5.n ( a f9ite field .2;,f1 ": .2;,f has .2;q ele;ts4 ,let _% .a `e ,e _: 2 algebraic ov} .2;,f ( degree .2;n4 ,prove t _% ,f(.a) _: has _% q~n _: ele;ts4 #ai 4 ,%{ t e f9ite ext5.n ( a f9ite field .2;,f is simple2 t is1 if .2;,e is a f9ite ext5.n ( a f9ite field .2;,f1 prove t "! exi/s an _% .a `e ,e _: s* t _% ,e .k ,f(.a) _:4 #bj 4 ,%{ t = e .2;n "! exi/s an irr$ucible polynomial ( degree .2;n 9 _% `;,z;p"`(x`) _:4 #ba 4 ,prove t ! ~1,frob5ius ~1map _% .,f_3 ,,gf(p~n") $o ,,gf(p~n") _: giv5 by _% .,f_3 .a $|33o .a~p _: is an automorphism ( ord} .2;n4 #bb 4 ,%{ t e ele;t 9 _% ,,gf(p~n") _: c 2 writt5 9 ! =m _% a~p _: = "s unique _% a `e ,,gf(p~n") _:4 #ajgf #bc 4 ,let .2;,e & .2;,f 2 subfields ( _% ,,gf(p~n") _:4 ,if _% |,e| .k p~r _: & _% |,f| .k p~s _:1 :at is ! ord} ( _% ,e.%,f _:;8 #bd 4 ,wilson's ,!orem4 ,let .2;p 2 prime4 ,prove t _% (p-1)& _l -#1(mod p) _:4 #be 4 ,if _% g(t) _: is ! m9imal g5}ator polynomial = a cyclic code .2;,c 9 _% ,r;n _:1 prove t ! 3/ant t}m ( _% g(x) _: is #a4 #bf 4 ,(t5 x is 3ceivable t a bur/ ( }rors miy bur/ ( 9t}f};e mie isomorphic z vector spaces4 #bh 4 ,let .2;,c 2 a code 9 _% ,r;n _: t is g5}at$ by _% g(t) _:4 ,if _% ..(f(t)..) _: is ano!r code 9 _% ,r;n _:1 %{ t _% ..(g(t)..) _"k ..(f(t)..) _: if & only if _% f(x) _: divides _% g(x) _: 9 _% `;,z2`(x`) _:4 #bi 4 ,let _% ,c .k ..(g(t)..) _: 2 a cyclic code 9 _% ,r;n _: & suppose t _% x~n"-1 .k g(x)h(x) _:1 ": _% g(x) .k g0+g1x+''' +g;n-k"x~n-k _: & _% h(x) .k h0+h1x+''' +h;k"x~k _:4 ,def9e .2;,g to 2 ! _% n`*k _: matrix #ajgh _% ,g .k ,(g0 #0 ''' #0 ,) ,(g1 g0 ''' #0 ,) ,(''' ''' ''' ''' ,) ,(g;n-k" g;n-k-1" ''' g0 ,) ,(#0 g;n-k" ''' g1 ,) ,(''' ''' ''' ''' ,) ,(#0 #0 ''' g;n-k,) _: & .2;,h to 2 ! _% (n-k)`*n _: matrix _% ,h .k ,(#0 ''' #0 #0 h;k" ''' h0 ,) ,(#0 ''' #0 h;k" ''' h0 #0 ,) ,(''' ''' ''' ''' ''' ''' ''',) ,(h;k" ''' h0 #0 #0 ''' #0 ,) _: 4 a4 ,prove t .2;,g is a g5}ator matrix = .2;,c4 ;b4 ,prove t .2;,h is a p>;y-*eck matrix = .2;,c4 ;c4 ,%{ t _% ,h,g .k #0 _:4 ,ex}cises #bb4e ,addi;nal #ajgi ,ex}cises3 ,}ror ,correc;n = ,,b* ,codes ,,b* codes h v attractive }ror correc;n algori?ms4 ,let .2;,c 2 a ,,b* code 9 _% ,r;n _:1 & suppose t a code polynomial _% c(t) .k c0+c1t+''' +c;n-1"t~n-1 _: is transmitt$4 ,let _% w(t) .k w0+w1t+ ''' w;n-1"t~n-1 _: 2 ! polynomial 9 _% ,r;n _: t is rcvd4 ,if }rors h o3urr$ 9 bits _% a1, ''', a;k _:1 !n _% w(t) .k c(t)+e(t) _:1 ": _% e(t) .k t~a1"+t~a2+''' +t~a~;k _: is ! ~1}ror ~1polynomial~'4 ,! decod} m/ det}m9e ! 9teg}s _% a;i _: & !n recov} _% c(t) _: f _% w(t) _: by flipp+ ! _% a;i _:? bit4 ,f _% w(t) _: we c compute _% w(.w~i") .k s;i _: = _% i .k #1, ''', #2r _:1 ": _% .w _: is a primitive .2n? root ( un;y ov} _% `;,z2 _:4 ,we say ! ~1syndrome ( _% w(t) _: is _% s1, ''', s;2r _:4 #a 4 ,%{ t _% w(t) _: is a code polynomial if & only if _% s;i .k #0 _: = #ajhj all .2i4 #b 4 ,%{ t _% s;i .k w(.w~i") .k e(.w~i") .k .w~ia1"+.w~ia2+''' +.w~ia~;k _: = _% i .k #1, ''', #2r _:4 ,! ~1}ror-locator ~1polynomial is def9$ to 2 _% s(x) .k (x+.w~a1")(x+.w~a2) ''' (x+.w~a~;k~") _: 4 #c 4 ,recall ! _% (15, 7) _:-block ,,b* code 9 ,example #bb4ai4 ,by ,!orem #h4ac1 ? code is capable ( correct+ two }rors4 ,suppose t ~! }rors o3ur 9 bits _% a1 _: & _% a2 _:4 ,! }ror-locator polynomial is _% s(x) .k (x+.w~a1")(x+.w~a2") _:4 ,%{ t _% s(x) .k x~2"+s1x+(s1~2"+?s3/s1#) _: 4 #d 4 ,let #ajha _% w(t) .k #1+t~2"+t~4"+t~5"+t~7"+t~12"+t~13 _: 4 ,det}m9e :at ! orig9ally transmitt$ code polynomial was4 ,ref};es #bb4f ,ref};es & ,su7e/$ ,r1d+s .<#a.> ,*ilds1 ;,l4 ,a ,3crete ,9troduc;n to ,hi<} ,algebra4 #bnd $4 ,spr+}-,v}lag1 ,new ,york1 #aiie4 .<#b.> ,g~$ad+1 ;,l4 & ,tamb|r1 ;,t4 ,algebra = ,comput} ,sci;e4 ,spr+}-,v}lag1 ,new ,york1 #aihh4 .<#c.> ,lidl1 ;,r4 & ,pilz1 ;,g4 ,appli$ ,ab/ract ,algebra4 #bnd $4 ,spr+}1 ,new ,york1 #aiih4 ,an excell5t pres5ta;n ( f9ite fields & _! applica;ns4 .<#d.> ,mackiw1 ;,g4 ,applica;ns ( ,ab/ract ,algebra4 ,wiley1 ,new ,york1 #aihe4 .<#e.> ,roman1 ;,s4 ,cod+ & ,9=ma;n ,!ory4 ,spr+}-,v}lag1 ,new ,york1 #aiib4 .<#f.> van ,l9t1 ;,j4 ;,h4 ,9troduc;n to ,cod+ ,!ory4 ,spr+}1 ,new ,york1 #aiii4 #ajhb