{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "Geneva" 0 12 0 0 0 1 0 1 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 257 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 261 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 262 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 263 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 264 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 265 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 266 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 267 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 268 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 269 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 270 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 271 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 272 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 273 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 274 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 275 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 276 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 277 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 278 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 279 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 280 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 281 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 282 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 283 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 284 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 285 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 286 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 287 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 288 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 289 "Geneva" 1 12 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 290 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 291 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 292 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 293 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 294 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 295 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 296 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 297 "Geneva" 1 12 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 298 "Geneva" 1 12 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 299 "Geneva" 0 10 0 0 0 1 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 300 "" 0 10 0 0 0 1 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 301 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 302 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 303 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 304 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 305 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 306 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 307 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 308 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 309 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 310 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 311 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 312 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 313 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 314 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 315 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 316 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 317 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 318 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 319 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 320 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 321 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 322 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 323 "Century \+ Schoolbook" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 324 "Centur y Schoolbook" 0 10 0 0 0 1 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 325 "Cen tury Schoolbook" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 326 "G eneva" 0 10 0 0 0 1 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 327 "Geneva" 1 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 328 "Geneva" 1 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 329 "Geneva" 1 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 330 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 331 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 332 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 333 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 334 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 335 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 336 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 337 "Geneva" 1 12 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 338 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 339 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 340 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 341 "Century Schoolbook" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 342 "Century Schoolbook" 0 10 0 0 0 1 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 343 "Century Schoolbook" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 344 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 345 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 346 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 347 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 348 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 349 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 350 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 351 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 352 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 353 "Geneva" 1 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 354 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 355 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 356 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 357 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 358 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 359 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 360 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 361 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 362 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 363 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 364 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 365 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 366 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 367 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 368 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 369 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 370 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 371 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 372 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 373 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 374 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 375 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 376 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 377 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 378 "Symbol" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 379 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 380 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 381 "Geneva" 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 1 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Gen eva" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 } {PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "Geneva" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Geneva" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Gen eva" 1 10 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 2 8 1 0 1 0 2 2 0 1 } {PSTYLE "R3 Font 0" -1 256 1 {CSTYLE "" -1 -1 "Monaco" 1 9 0 0 255 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "R3 Font 2" -1 257 1 {CSTYLE "" -1 -1 "Geneva" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 } 1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "R3 Font 3" -1 258 1 {CSTYLE "" -1 -1 "Geneva" 1 10 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "R3 Font 4" -1 259 1 {CSTYLE "" -1 -1 "Symbol" 1 10 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Hea ding 2" -1 260 1 {CSTYLE "" -1 -1 "Geneva" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 4 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 261 1 {CSTYLE "" -1 -1 "Century Schoolbook" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 4 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 262 1 {CSTYLE " " -1 -1 "Geneva" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 4 4 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT 256 56 "Generating and Checking \+ Automorphisms over Finite Fields" }}{PARA 19 "" 0 "" {TEXT -1 54 "\251 Mike May, S.J., maymk@slu.edu, Saint Louis University" }}{PARA 0 "" 0 "" {TEXT 289 1 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart :" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 297 422 "This worksheet uses Maple \+ to test examine automorphisms for finite extensions of the rationals. \+ You should probably have worked through the worksheet on Factoring Ex amples and the pair of worksheets on Automorphisms before attempting t his worksheet. \n \nThe pair of worksheets on automorphisms ooked at \+ automorphisms of finite extensions of the rationals. For the material on Galois Theory, that is the primary example. " }{TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 298 602 "For simply studying automorphisms however, finite fields have several attractive features. We know from class that a finite field is gener ated by a single element and its Galois group is a cyclic group genera ted by the Frobenius automorphism. Furthermore, since finite fields a re finite sets, potential automorphisms can be tested by brute force. \+ For a finite field an automorphism is defined by the image of a gene rating element and extended by linearity. This worksheet is set up to allow you to define a potential automorphism, then compute all the im ages and see if the map is an automorphism." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 261 "" 0 "" {TEXT 299 1 "P" }{TEXT 300 42 "re liminaries - setting up the finite field" }{TEXT -1 1 " " }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 296 253 "BE SURE TO START THIS WO RKSHEET BY EVALUATING THE FIRST THREE INPUT BLOCKS. THEY DEFINE THE F IELD AND TOOLS THAT WE NEED FOR OUR CALCULATIONS\nWe need to start by \+ reading in the library that does finite fields and setting up some too ls that we will use." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 599 "readlib(GF):\n`?`:= zeta:\nGextension := proc() Gfunct[ConvertOut](Gfunct[extension]) \n end:\nGorder \+ := proc(a) Gfunct[ConvertOut]\n (Gfunct[order](Gfunct[ConvertIn](a) )) \n end:\nF := x -> subs(zeta = x, Gextension()):\nGreduce : = x -> sort(simplify(x) mod character, alpha, tdeg):\nGredpoly := proc (poly, var)\n sort(collect(simplify(poly) mod character, var, G reduce), var);\n end:\nGquo := proc(bigpoly, divpoly, var, grem)\n \+ if nargs = 3 then\n Quo(bigpoly, divpoly, var) mod characte r;\n else\n Quo(bigpoly, divpoly, var, grem) mod characte r;\n fi\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 301 87 "The second \+ step is to specify the finite field. We are interested in using the f ield \n" }{XPPEDIT 18 0 "GF[p^d] = Z[p]*[x]/[(f(x))]" "6#/&%#GFG6#)%\" pG%\"dG*(&%\"ZG6#F(\"\"\"7#%\"xGF.7#-%\"fG6#F0!\"\"" }{TEXT 302 67 " \+ where f(x) is a polynomial of degree d that is irreducible over " } {XPPEDIT 18 0 "Z[p]" "6#&%\"ZG6#%\"pG" }{TEXT 303 147 ". We will refe r to the current finite field as GF. To follow conventions from class , we want to think of elements of the field as polynomials in " } {XPPEDIT 18 0 "alpha" "6#%&alphaG" }{TEXT 305 6 " over " }{XPPEDIT 18 0 "Z[p]" "6#&%\"ZG6#%\"pG" }{TEXT 304 33 " of degree less than d, wh ere " }{XPPEDIT 18 0 "alpha" "6#%&alphaG" }{TEXT 306 22 " is a root \+ of f(x). " }}{PARA 0 "" 0 "" {TEXT 309 303 "\n[A note for those inter ested in technical detail that can be skipped by others - We want to u se the polynomial f(x) in several different ways and that gives potent ial for colliding names on Maple. To eliminate problems, we will set \+ things up so that when a field is created, it is created in terms of \+ " }{XPPEDIT 18 0 "zeta" "6#%%zetaG" }{TEXT 308 16 ". This leaves " } {XPPEDIT 18 0 "alpha" "6#%&alphaG" }{TEXT 307 98 " to be used for the format we are interested in.]\n\nTo set up our field we need two line s of code." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 105 "character := 2; fzeta := zeta^3 + zeta + 1; deg := degree(fzeta, zeta);\nGfunct:=G F(character,deg, fzeta):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 157 "The \+ first line of code gives the characteristic of the prime field, an irr educible polynomial over Z[p], and the degree of the polynomial. The \+ second line " }{TEXT 315 17 "functions for Gf(" }{XPPEDIT 18 0 "p^d" "6#)%\"pG%\"dG" }{TEXT 316 23 "), the finite field of " }{XPPEDIT 18 0 "p^d" "6#)%\"pG%\"dG" }{TEXT 312 37 " elements, by using the polynom ial f(" }{XPPEDIT 18 0 "zeta" "6#%%zetaG" }{TEXT 311 40 ") which is ir reducible of degree d over " }{XPPEDIT 18 0 "Z[p]" "6#&%\"ZG6#%\"pG" } {TEXT 313 126 ". As a default, we start with a field of 8 elements wh ere the polynomial used for the extension field is \n \+ " }{XPPEDIT 18 0 "f(zeta) = zeta^3 + zeta + 1" "6#/-%\"fG6#%%zetaG,( *$F'\"\"$\"\"\"F'F+F+F+" }{TEXT 310 68 ".\nMaple will produce the irre ducible polynomial if needed, so the f(" }{XPPEDIT 18 0 "zeta" "6#%%ze taG" }{TEXT 314 14 ") is optional." }}}{EXCHG {PARA 0 "" 0 "" {TEXT 320 261 "TO CHANGE FIELDS, YOU NEED TO REEVALUATE BOTH OF THE LINES ABOVE AS WELL AS THE INPUT SECTIONS BELOW THAT DEFINES TOOLS.\n\nFor \+ example, if you want to change to the field of 64 = 2^6 elements, repl ace the two lines above with:\n character := 2; deg := 6" }} {PARA 0 "" 0 "" {TEXT 321 148 " Gfunct:=GF(character, deg):\n \nIF YOU ARE GOING TO CHANGE FIELDS, YOU NEED TO REEVALUATE THE INPUT \+ SECTION BELOW AFTER YOU CHANGE THE FIELD." }}}{EXCHG {PARA 0 "" 0 "" {TEXT 322 96 "Finally we need to define some functions that need to be evaluated after the field is defined. " }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 181 "alias (alpha = RootOf(Gextension())):\nf := F(x);\ndeg := degree(f, x):\nIn t2alpha:= a -> simplify(subs(zeta = alpha, \n Gfunct[Conver tOut](Gfunct[input](a)))) mod character:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 317 119 "The polynomial f(x) given above is the irreducible poly nomial used in the construction of the field. Let's check that " } {TEXT 318 1 "a" }{TEXT 319 56 " raised to the degree of the extension \+ reduces properly." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 106 "alpha ^deg;\nsimplify(alpha^deg) mod character;\nprint(`F(`,alpha,`) = `,F(a lpha),` = `, simplify(F(alpha)));" }}}}{SECT 0 {PARA 262 "" 0 "" {TEXT 325 0 "" }{TEXT 324 63 "Checking for possible automorphisms - Fi rst Brute Force Attempt" }{TEXT 323 1 " " }}{PARA 0 "" 0 "" {TEXT 326 24 "(Not really Brute Force)" }{TEXT 327 1 "\n" }{TEXT -1 0 "" }} {EXCHG {PARA 0 "" 0 "" {TEXT 290 130 "Recall that an automorphism of G F must respect both addition and multiplication. Since all the elemen ts of GF are polynomials in " }{TEXT 257 1 "a" }{TEXT 258 90 ", it is \+ clear that to specify an automorphism of GF, it suffices to specify th e image of " }{XPPEDIT 18 0 "alpha" "6#%&alphaG" }{TEXT 291 59 ". We want to test which field elements could be images of " }{XPPEDIT 18 0 "alpha" "6#%&alphaG" }{TEXT 292 41 ".\n\nThe first test of possible \+ images of " }{XPPEDIT 18 0 "alpha" "6#%&alphaG" }{TEXT 293 18 " is to evaluate f(" }{TEXT 259 1 "b" }{TEXT 260 18 ") for all nonzero " } {XPPEDIT 18 0 "beta" "6#%%betaG" }{TEXT 294 14 " in GF. Thus " } {XPPEDIT 18 0 "beta" "6#%%betaG" }{TEXT 261 26 " can only be the image of " }{TEXT 262 1 "a" }{TEXT 263 32 " under an automorphism phi if f( " }{TEXT 264 1 "b" }{TEXT 265 40 ") = 0.\n\nThe following loop evaluat es f(" }{TEXT 266 1 "b" }{TEXT 267 19 ") for the nonzero " }{TEXT 268 3 "b " }{TEXT 269 31 "in GF. For the field elements " }{TEXT 270 1 "b" }{TEXT 271 8 " with f(" }{TEXT 272 1 "b" }{TEXT 273 24 " ) = 0, the loop prints " }{TEXT 274 1 "b" }{TEXT 275 4 ", f(" }{TEXT 276 1 "b" }{TEXT 277 9 "), and f(" }{TEXT 278 1 "b" }{TEXT 279 50 ") in no rmal form. (To print these values for all " }{TEXT 280 1 "b" }{TEXT 281 73 " in GF, switch the # sign from the second last line to the one above it.)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 261 "for i from \+ 0 to Gfunct[size] -1 do \n a := Int2alpha(i):\n b := F(a):\n \+ c := simplify(b) mod character:\n if c = 0 then print(`If a \+ = `,a,` then F(a) = `, b,` = `, c); fi;\n # c = 0 then print(`If \+ a = `,a,` then F(a) = `, b,` = `, c);\n od:" }}}{EXCHG {PARA 256 " " 0 "" {TEXT 328 1 "\n" }{TEXT 337 49 "To check our work, we factor th e polynomial f(x)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "Facto r(f, alpha) mod character;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 329 1 "\n " }{TEXT 336 13 "As expected, " }{TEXT 330 1 "b" }{TEXT 331 42 " is a \+ root of f(x) if and only if (x - " }{TEXT 332 1 "b" }{TEXT 333 214 ") is a factor. The roots of f(x) form a patern that is not immediat ely visible, but is easy to explain. Recall that the only automorphis ms of a finite field are powers of the Frobenius automorphism which ra ises " }{XPPEDIT 18 0 "alpha" "6#%&alphaG" }{TEXT 338 70 " to the \"ch aracter\" power. Compare the roots above with the values " }{TEXT 334 1 "a" }{TEXT 335 30 "^(character^i) computed below." }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 197 "for i from 1 to d eg do \n print(`If `,'i' = i,` then `, 'character'^i = character^ i, ` and `,\n alpha^(character^i) = \n simplify(alp ha^(character^i)) mod character);\n od;" }}}{EXCHG {PARA 0 "" 0 " " {TEXT 339 5 "Thus " }{XPPEDIT 18 0 "alpha^i" "6#)%&alphaG%\"iG" } {TEXT 340 70 " is a root of f(x) if and only if i is a power of the c haracteristic." }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 10 "Exercises:" }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 80 "1) Change fields to the field of \+ 125 elements using the irreducible polynomial " }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "x^3 + x + 1" "6#,(*$%\"xG\"\"$\"\"\"F%F'F'F'" }{TEXT -1 83 ". Verify that the only possible automorphisms are the powers o f the Frobenius map." }}}{EXCHG }{EXCHG {PARA 0 "" 0 "" {TEXT -1 129 " 2) Change fields to a field of 128 elements. Verify that the only po ssible automorphisms are the powers of the Frobenius map. " }}} {EXCHG }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 61 "Remember to change back t o your original field of 8 elements." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 0 {PARA 262 "" 0 "" {TEXT 343 0 "" }{TEXT 342 60 "Brute Force Checking of automorphisms - (Really Brute Force)" }{TEXT 341 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT 282 195 "It is time now to try showing that the substitutions identified above are automorphi sms and that any other substitution is not an automorphism. \nThe pro cedure we are using, substituting a value " }{TEXT 283 1 "b" }{TEXT 284 6 " for " }{TEXT 285 1 "a" }{TEXT 286 251 ", clearly produces a g roup homomorphism for addition. (It is defined on linear combinations so that it respects addition.) Thus we need to focus our attention o n respecting multiplication. If we name the substitution map phi, we \+ need to show that " }{XPPEDIT 18 0 "phi(alpha^i) = phi(alpha)^i" "6#/ -%$phiG6#)%&alphaG%\"iG)-F%6#F(F)" }{TEXT 295 41 " with i ranging fr om 1 to the order of " }{TEXT 287 1 "a" }{TEXT 288 94 ".\n\nWe now set up this method to examine potential automorphisms and refine it sever al times.\n " }{MPLTEXT 1 0 0 "" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 68 "Method 1 - Sift through lots of output to test a single automorphi sm" }}{EXCHG {PARA 0 "" 0 "" {TEXT 364 8 "Specify " }{TEXT 365 1 "b" } {TEXT 366 16 ", the image of " }{TEXT 367 1 "a" }{TEXT 368 16 ", and \+ compute " }{TEXT 369 1 "f" }{TEXT 370 1 "(" }{TEXT 371 1 "a" }{TEXT 372 8 "^i) and " }{TEXT 373 1 "f" }{TEXT 374 1 "(" }{TEXT 375 1 "a" } {TEXT 376 26 ")^i for all i. Print (i, " }{XPPEDIT 18 0 "phi(alpha^i) , phi(alpha)^i" "6$-%$phiG6#)%&alphaG%\"iG)-F$6#F'F(" }{TEXT 377 46 " ) and visually check. (We start with beta = " }{TEXT 378 1 "a" } {TEXT 379 19 " + 1 as a default.)" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 316 "beta := alpha + 1;\nfor i from 1 to\nGfunct[ size] -1 do \n a := simplify(alpha^i) mod character:\n b := si mplify(subs(alpha = beta, a)) mod character:\n c := simplify(beta^ i) mod character:\n print(`If `,'i' = i,` then `, alpha^i = a,` s o`,\n phi(alpha^i) = b, ` and `, phi(alpha)^i = c);\n od: \+ " }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 9 "Exercise:" }}{EXCHG {PARA 0 " " 0 "" {TEXT -1 16 "3) Is the map " }{XPPEDIT 18 0 "phi" "6#%$phiG" }{TEXT -1 11 " sending " }{XPPEDIT 18 0 "alpha" "6#%&alphaG" }{TEXT -1 6 " to " }{XPPEDIT 18 0 "alpha +1" "6#,&%&alphaG\"\"\"F%F%" } {TEXT -1 71 " an automorphism? Justify your answer from the output p roduced above." }}}{EXCHG }{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}}} {SECT 0 {PARA 5 "" 0 "" {TEXT -1 69 "Method 2 - Have Maple sift throug h the output to test an automorphism" }}{EXCHG {PARA 0 "" 0 "" {TEXT 350 8 "Specify " }{XPPEDIT 18 0 "beta" "6#%%betaG" }{TEXT 363 16 ", th e image of " }{XPPEDIT 18 0 "alpha" "6#%&alphaG" }{TEXT -1 2 ", " } {TEXT 354 14 " and compute " }{XPPEDIT 18 0 "phi(alpha^i)" "6#-%$phiG 6#)%&alphaG%\"iG" }{TEXT 355 7 " and " }{XPPEDIT 18 0 "phi(alpha)^i " "6#)-%$phiG6#%&alphaG%\"iG" }{TEXT 356 25 " with i starting at 1. \+ " }}{PARA 0 "" 0 "" {TEXT 380 10 "Print (i, " }{XPPEDIT 18 0 "phi(alph a^i)" "6#-%$phiG6#)%&alphaG%\"iG" }{TEXT 351 3 ", " }{XPPEDIT 18 0 "p hi(alpha)^i" "6#)-%$phiG6#%&alphaG%\"iG" }{TEXT 362 17 ") until eithe r " }{XPPEDIT 18 0 "phi(alpha^i)" "6#-%$phiG6#)%&alphaG%\"iG" }{TEXT 357 19 " is not equal to " }{XPPEDIT 18 0 "phi(alpha)^i" "6#)-%$phiG 6#%&alphaG%\"iG" }{TEXT 352 74 ", or until all values of i have been \+ tested. (Once again, we start with " }{XPPEDIT 18 0 "beta = alpha + 1 " "6#/%%betaG,&%&alphaG\"\"\"F'F'" }{TEXT 358 15 " as a default." } {TEXT 353 1 ")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 415 "beta := \+ alpha + 1;\nfor i from 1 to\nGfunct[size] -1 do \n a := simplify(a lpha^i) mod character:\n b := simplify(subs(alpha = beta, a)) mod \+ character:\n c := simplify(beta^i) mod character:\nif c <> b then \+ \nprint(`the map `, phi, ` taking `,alpha,` to `,beta,\n` is not a hom omorphism since if `, 'i' = i);\nprint( phi(alpha^i) = b,` while `, ph i(alpha)^i = c);\nprint;\nbreak;\nelse print(i, a, b, c);\nfi:\n od: " }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "4) Pick a different value for " }{XPPEDIT 18 0 " beta" "6#%%betaG" }{TEXT -1 104 ", and either show that the map is an \+ automorphism, or that it not an automorphism. Justify your answer." } }}{EXCHG }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 54 "Method 3 - Have Maple test all possible automorphisms " }}{EXCHG {PARA 0 "" 0 "" {TEXT 344 114 "To automate the procedure set up in the previous case we can set \+ up a double loop to check all possible values of " }{TEXT 345 1 "b" } {TEXT 346 21 ". For each value of " }{TEXT 347 1 "b" }{TEXT 348 14 ", we compare " }{XPPEDIT 18 0 "phi(alpha^i)" "6#-%$phiG6#)%&alphaG%\"i G" }{TEXT 359 7 " and " }{XPPEDIT 18 0 "phi(alpha)^i" "6#)-%$phiG6#% &alphaG%\"iG" }{TEXT 360 73 " with i starting at 1 until either all v alues of i have been tested or " }{XPPEDIT 18 0 "phi(alpha^i)" "6#-%$ phiG6#)%&alphaG%\"iG" }{TEXT 361 19 " is not equal to " }{XPPEDIT 18 0 "phi(alpha)^i" "6#)-%$phiG6#%&alphaG%\"iG" }{TEXT 349 1 "." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 664 "for j from 1 to\nGfunct[siz e] -1 do\nbeta := Int2alpha(j):\ntst := 1:\nfor i from 1 to\nGfunct[s ize] -1 do \n a := simplify(alpha^i) mod character:\n b := s implify(subs(alpha = beta, a)) mod character:\n c := simplify(bet a^i) mod character:\n if c <> b then \n print(`the map `, phi,` ta king `,alpha,` to `,beta, \n ` is not a homomorphism since \+ if i =`||i);\n print( alpha^i = a,` and `, phi(a) = b);\n print(`w hile `, phi(alpha)^i = beta^i , `and `, beta^i = c);\n print(` `) ;\n tst := 0;\n break;\n fi:\n od:\n if tst = 1 then\n pr int(`the map taking `||alpha||` to `||beta||` is a homomorphism`);\n \+ print(` `);\n fi:\nod:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 225 "Notice that in all cases where the map is not an automorphism, th e problem shows up when i is the degree of the polynomial f(x) used to generate the field. This lets us simplify the procedure by eliminati ng one of the loops." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 564 "i \+ := deg: \nfor j from 1 to\n Gfunct[size] -1 do\n beta := Int2alpha(j ):\n a := simplify(alpha^i) mod character:\n b := simplify(s ubs(alpha = beta, a)) mod character:\n c := simplify(beta^i) mod \+ character:\n if c <> b then \n print(`the map `, phi,` taking `,al pha,` to `,beta, \n ` is not a homomorphism since if i =`|| i);\n print( alpha^i = a,` and `, phi(a) = b);\n print(`while `, p hi(alpha)^i = beta^i , `and `, beta^i = c);\n else\n print(`the m ap taking `||alpha||` to `||beta||` is a homomorphism`);\n fi:\n p rint(` `);\nod:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 78 "This lets u s shorten the printing to only show the maps that are homomrphisms." } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 336 "i := deg: \nfor j from 1 \+ to\n Gfunct[size] -1 do\n beta := Int2alpha(j):\n a := simplify (alpha^i) mod character:\n b := simplify(subs(alpha = beta, a)) m od character:\n c := simplify(beta^i) mod character:\n if c = b then \n print(`the map taking `||alpha||` to `||beta||` is a homom orphism`);\n print(` `);\n fi:\nod:" }}}{SECT 0 {PARA 5 "" 0 " " {TEXT -1 10 "Exercises:" }}{EXCHG {PARA 0 "" 0 "" {TEXT 381 1 "5" } {TEXT -1 81 ") Show that the reduction above is valid. That is show \+ that if we define a map " }{XPPEDIT 18 0 "phi" "6#%$phiG" }{TEXT -1 13 " by defining " }{XPPEDIT 18 0 "phi(alpha)" "6#-%$phiG6#%&alphaG" } {TEXT -1 67 " and extending by linearity, then we have an automorphism whenever " }{XPPEDIT 18 0 "phi(alpha^i) = phi(alpha)^i" "6#/-%$phiG6# )%&alphaG%\"iG)-F%6#F(F)" }{TEXT -1 156 " when i is the degree of the polynomial used to define the field. (This is not a Maple question, \+ but a question that lets you use Maple more efficiently.)" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}}{EXCHG }{EXCHG {PARA 0 "" 0 "" {TEXT -1 85 "6) Using one of the loops above find the automorphisms of the field of \+ 125 elements." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG }{EXCHG }}}}} {MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }