Wielomian Conwaya (pola skończone)

W matematyce wielomian Conwaya C _{p , n} dla ciała skończonego F _{p ⁿ} jest szczególnym nieredukowalnym wielomianem stopnia n nad F _p , którego można użyć do zdefiniowania standardowej reprezentacji F _{p ⁿ} jako ciała rozdzielającego C _{p , n} . Wielomiany Conwaya zostały nazwane na cześć Johna H. Conwaya przez Richarda A. Parkera , który jako pierwszy je zdefiniował i obliczył przykłady. Wielomiany Conwaya spełniają pewien warunek zgodności zaproponowany przez Conwaya między reprezentacją pola a reprezentacjami jego podpól. Są ważne w algebrze komputerowej , gdzie zapewniają przenośność między różnymi matematycznymi bazami danych i systemami algebry komputerowej. Ponieważ obliczenia wielomianów Conwaya są drogie, muszą być przechowywane, aby można je było wykorzystać w praktyce. Bazy danych wielomianów Conwaya są dostępne w systemach algebry komputerowej GAP , Macaulay2 , Magma , SageMath oraz na stronie internetowej Franka Lübecka.

Tło

₀ Elementy F _{p ⁿ} można przedstawić jako sumy postaci a _{n −1} β ^{n −1} + ... + a ₁ β + a gdzie β jest pierwiastkiem nierozkładalnego wielomianu stopnia n nad F _p i a _j są elementami F _p . Dodawanie elementów pola w tej reprezentacji jest po prostu dodawaniem wektorów. Chociaż istnieje unikalne skończone pole rzędu p ⁿ aż do izomorfizmu , reprezentacja elementów pola zależy od wyboru nieredukowalnego wielomianu. Wielomian Conwaya jest sposobem na standaryzację tego wyboru.

Niezerowe elementy ciała skończonego tworzą grupę cykliczną podczas mnożenia. Prymitywny element α z F _{p ⁿ} jest elementem, który generuje tę grupę . Reprezentacja niezerowych elementów pola jako potęg α umożliwia wydajne wykonywanie mnożenia w polu. Prymitywny wielomian dla α jest wielomianem monicznym najmniejszego możliwego stopnia ze współczynnikami w F _p , którego pierwiastkiem jest α w F _{p ⁿ} ( wielomian minimalny dla α ). Jest koniecznie nieredukowalny. Wielomian Conwaya jest wybrany jako prymitywny, tak że każdy z jego pierwiastków generuje grupę multiplikatywną powiązanego pola skończonego.

Podpolami F _{p ⁿ} są _{pm ^pola} F z m dzielącym n . Grupa cykliczna _{pm ^utworzona} z niezerowych elementów F jest podgrupą grupy cyklicznej F _{p ⁿ} . Jeśli α generuje to drugie, to najmniejszą potęgą α , która generuje to pierwsze, jest α ^r , gdzie r = ( p ⁿ - 1)/( p ^m - 1). Jeśli f _n jest pierwotnym wielomianem dla F _{p ⁿ} z pierwiastkiem _{pm ^α} , a f _m jest wielomianem pierwotnym dla F , to zgodnie z definicją Conwaya f _m i f _n są zgodne , jeśli α ^r jest pierwiastkiem z f _m . Wymaga to, że f _m ( x ) dzieli f _n ( x ^r ). To pojęcie kompatybilności jest nazywane kompatybilnością z normami . Wielomian Conwaya dla ciała skończonego jest tak dobrany, aby był zgodny z wielomianami Conwaya każdego z jego podpól. Że można dokonać wyboru w ten sposób, udowodnił Werner Nickel.

Definicja

Wielomian Conwaya C _{p , n} jest zdefiniowany jako leksykograficznie minimalny wielomian pierwotny moniczny stopnia n nad F _p , który jest zgodny z C _{p , m} dla wszystkich m dzielących n . Jest to definicja indukcyjna na n : przypadek bazowy to C _{p ,1} ( x ) = x − α gdzie α jest leksykograficznie minimalnym elementem pierwotnym F _p . Użyte pojęcie porządku leksykograficznego jest następujące:

• Elementy F _p są uporządkowane 0 < 1 < 2 < ... < p - 1.
• ₀₀ Wielomian stopnia d w F _p [ x ] jest zapisywany jako a _d x ^d − a _{d −1} x ^{d −1} + ... + (−1) ^da a następnie wyrażany jako słowo a _d a _{d −1} . .. _ _ Dwa wielomiany stopnia d są uporządkowane zgodnie z uporządkowaniem leksykograficznym odpowiadających im słów.

Ponieważ wydaje się, że nie ma żadnego naturalnego kryterium matematycznego, które wyróżniałoby jeden moniczny wielomian pierwotny spełniający warunki zgodności spośród wszystkich innych, narzucenie uporządkowania leksykograficznego w definicji wielomianu Conwaya należy uznać za konwencję.

Obliczenie

Algorytmy do obliczania wielomianów Conwaya, które są bardziej wydajne niż wyszukiwanie siłowe, zostały opracowane przez Heatha i Loehra. Lübeck wskazuje, że ich algorytm jest ponownym odkryciem metody Parkera.

Notatki

•   Holt, Derek F.; Eick, Bettina; O'Brien, Eamonn A. (2005), Podręcznik obliczeniowej teorii grup , Matematyka dyskretna i jej zastosowania, tom. 24, CRC Press, ISBN 978-1-58488-372-2