Conway polynom (ändliga fält)

Inom matematik är Conway-polynomet C p , n för det finita fältet F p n ett särskilt irreducerbart polynom av grad n över F p som kan användas för att definiera en standardrepresentation av F p n som ett delande fält av C p , n . Conway polynom uppkallades efter John H. Conway av Richard A. Parker , som var den första att definiera dem och beräkna exempel. Conway-polynom uppfyller ett visst kompatibilitetsvillkor som hade föreslagits av Conway mellan representationen av ett fält och representationerna av dess underfält. De är viktiga i datoralgebra där de ger portabilitet mellan olika matematiska databaser och datoralgebrasystem. Eftersom Conway-polynom är dyra att beräkna måste de lagras för att kunna användas i praktiken. Databaser med Conway-polynom är tillgängliga i datoralgebrasystemen GAP , Macaulay2 , Magma , SageMath och på Frank Lübecks webbplats.

Bakgrund

0 Element av F p n kan representeras som summor av formen a n −1 β n −1 + ... + a 1 β + a där β är en rot av ett irreducerbart polynom av grad n över F p och a j är element i F p . Addering av fältelement i denna representation är helt enkelt vektortillägg. Även om det finns ett unikt ändligt ordningsfält p n upp till isomorfism , beror representationen av fältelementen på valet av det irreducerbara polynomet. Conway-polynomet är ett sätt att standardisera detta val.

Elementen som inte är noll i ett ändligt fält bildar en cyklisk grupp under multiplikation. Ett primitivt element , α , av F p n är ett element som genererar denna grupp. Genom att representera fältelementen som inte är noll som potenser av a kan multiplikation i fältet utföras effektivt. Det primitiva polynomet för α är det moniska polynomet av minsta möjliga grad med koefficienter i F p som har α som en rot i F p n (minimalpolynomet för α ) . Det är nödvändigtvis irreducerbart. Conway-polynomet är valt att vara primitivt, så att var och en av dess rötter genererar den multiplikativa gruppen för det associerade finita fältet.

Underfälten för F p n är fält F p m med m som delar n . Den cykliska gruppen som bildas av icke-noll-elementen i pn F p m är en undergrupp av den cykliska gruppen av F . Om α genererar den senare är den minsta potensen av α som genererar den förra α r där r = ( p n − 1)/( p m − 1). Om f n är ett primitivt polynom för F p n med rot α , och om f m är ett primitivt polynom för F p m , så är enligt Conways definition f m och f n kompatibla om α r är en rot av f m . Detta kräver att f m ( x ) delar f n ( x r ). Denna uppfattning om kompatibilitet kallas normkompatibilitet av vissa författare. Conway-polynomet för ett ändligt fält väljs så att det är kompatibelt med Conway-polynomen för vart och ett av dess underfält. Att det går att göra valet på detta sätt bevisade Werner Nickel.

Definition

Conwaypolynomet C p , n definieras som det lexikografiskt minimala moniska primitiva polynomet av grad n över F p som är kompatibelt med C p , m för alla m som delar n . Detta är en induktiv definition på n : basfallet är C p ,1 ( x ) = x − α där α är det lexikografiskt minimala primitiva elementet i F p . Begreppet lexikografisk ordning som används är följande:

  • Elementen i F p är ordnade 0 < 1 < 2 < ... < p − 1.
  • 00 Ett polynom med grad d i F p [ x ] skrivs a d x d − a d −1 x d −1 + ... + (−1) d a och uttrycks sedan som ordet a d a d −1 . .. en . Två polynom av grad d är ordnade enligt den lexikografiska ordningen för deras motsvarande ord.

Eftersom det inte verkar finnas något naturligt matematiskt kriterium som skulle peka ut ett moniskt primitivt polynom som uppfyller kompatibilitetsvillkoren framför alla andra, bör påförandet av lexikografisk ordning i definitionen av Conway-polynomet betraktas som en konvention.

Beräkning

Algoritmer för att beräkna Conway-polynom som är mer effektiva än brute-force-sökning har utvecklats av Heath och Loehr. Lübeck indikerar att deras algoritm är en återupptäckt av Parkers metod.

Anteckningar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Conway_polynomial_(finite_fields)&oldid=931364553 "