Arytmetyka pól skończonych - Finite field arithmetic

W matematyce , arytmetyka ciał skończonych jest arytmetyka na polu skończonym ( pole zawierające skończoną liczbę elementów ) w przeciwieństwie do arytmetyki na polu o nieskończonej liczbie elementów, takim jak pole liczb wymiernych .

Istnieje nieskończenie wiele różnych pól skończonych. Ich liczba elementów jest z konieczności postaci p ^{n ,} gdzie p jest liczbą pierwszą , a n jest dodatnią liczbą całkowitą , a dwa skończone ciała tej samej wielkości są izomorficzne . Liczba pierwsza p nazywana jest charakterystyką pola, a dodatnia liczba całkowita n nazywana jest wymiarem pola nad jego ciałem pierwszym .

Pola skończone są używane w różnych zastosowaniach, w tym w klasycznej teorii kodowania w liniowych kodach blokowych, takich jak kody BCH i korekcja błędów Reed-Solomon , w algorytmach kryptograficznych , takich jak algorytm szyfrowania Rijndaela ( AES ), w planowaniu turniejów oraz w projektowanie eksperymentów .

Efektywna reprezentacja wielomianowa

Pole skończone z elementami p ⁿ jest oznaczone jako GF( p ⁿ ) i jest również nazywane polem Galois , na cześć twórcy teorii pola skończonego, Évariste'a Galois . GF( p ), gdzie p jest liczbą pierwszą, jest po prostu pierścieniem liczb całkowitych modulo p . Oznacza to, że można wykonywać operacje (dodawanie, odejmowanie, mnożenie) używając zwykłych operacji na liczbach całkowitych, po których następuje redukcja modulo p . Na przykład w GF(5), 4 + 3 = 7 jest zredukowane do 2 modulo 5. Dzielenie jest mnożeniem przez odwrotność modulo p , która może być obliczona przy użyciu rozszerzonego algorytmu Euklidesa .

Szczególnym przypadkiem jest GF(2), gdzie dodawanie jest wyłącznym OR (XOR), a mnożenie to AND . Ponieważ jedynym elementem odwracalnym jest 1, dzielenie jest funkcją tożsamości .

Elementy GF( p ⁿ ) mogą być reprezentowane jako wielomiany stopnia ściśle mniejszego niż n przez GF( p ). Operacje są następnie wykonywane modulo R, gdzie R jest nierozkładalnym wielomianem stopnia n nad GF( p ), na przykład przy użyciu wielomianu długiego dzielenia . Dodawanie dwóch wielomianów P i Q odbywa się jak zwykle; mnożenie można wykonać w następujący sposób: obliczyć W = P ⋅ Q jak zwykle, a następnie obliczyć resztę modulo R (istnieją lepsze sposoby na zrobienie tego).

Istnieją inne reprezentacje elementów GF( p ⁿ ), niektóre są izomorficzne z powyższą reprezentacją wielomianową, a inne wyglądają zupełnie inaczej (na przykład przy użyciu macierzy).

Gdy liczba pierwsza wynosi 2, konwencjonalnie wyraża się elementy GF( p ⁿ ) jako liczby binarne , przy czym każdy termin w wielomianu jest reprezentowany przez jeden bit w wyrażeniu binarnym odpowiedniego elementu. Nawiasy klamrowe ( "{" i "}" ) lub podobne ograniczniki są zwykle dodawane do liczb binarnych lub ich odpowiedników szesnastkowych, aby wskazać, że wartość jest elementem pola. Na przykład poniżej są równoważne reprezentacje tej samej wartości w charakterystycznym 2 skończonym polu:

Wielomian	x ⁶ + x ⁴ + x + 1
Dwójkowy	{01010011}
Szesnastkowy	{53}

Pierwotne wielomiany

Istnieje wiele wielomianów nierozkładalnych (czasami nazywanych wielomianami redukującymi ), których można użyć do wygenerowania skończonego pola, ale nie wszystkie dają początek tej samej reprezentacji tego pola.

Monic nierozkładalny wielomianem stopnia $n$ współczynników mających w GF skończonego ( $q$ ), gdzie $P = P T$ przez pewien główny $p$ i dodatnią liczbą całkowitą $t$ nazywany jest prymitywny wielomianu gdy wszystkie korzenie pierwotne elementy GF ( $q n$ ). W wielomianowej reprezentacji ciała skończonego oznacza to, że $x$ jest elementem pierwotnym. Istnieje co najmniej jeden wielomian nieredukowalny, dla którego $x$ jest pierwiastkiem pierwotnym. Innymi słowy, dla prymitywnego wielomianu, potęgi $x$ generują każdą niezerową wartość w polu.

W poniższych przykładach najlepiej nie używać reprezentacji wielomianowej, ponieważ znaczenie $x$ zmienia się między przykładami. Wielomian moniczny nierozkładalny $x 8 + x 4 + x 3 + x + 1$ nad GF(2) nie jest pierwotny. Niech $λ$ będzie pierwiastkiem tego wielomianu (w reprezentacji wielomianowej będzie to $x$ ), czyli $λ 8 + λ 4 + λ 3 + λ + 1 = 0$ . Teraz $λ 51 = 1$ , więc $λ$ nie jest pierwotnym elementem GF( ²⁸ ) i generuje multiplikatywną podgrupę rzędu 51. Rozważmy element pola $λ + 1$ (w reprezentacji wielomianowej byłoby to $x$ + 1). Teraz $(λ+1) 8 + (λ+1) 4 + (λ+1) 3 + (λ+1) 2 + 1 = λ 8 + λ 4 + λ 3 + λ + 1 = 0$ . Ponieważ wszystkie pierwiastki tego prymitywnego wielomianu są elementami pierwotnymi, $λ + 1$ jest elementem pierwotnym GF( ²⁸ ) ( $(λ + 1) 255 = 1$ i nie mniejsza potęga. GF(2 ⁸ ) ma 128 generatorów (patrz Liczba elementów pierwotnych ). Posiadanie $x$ jako generatora dla skończonego pola jest korzystne dla wielu matematycznych operacji obliczeniowych.

Dodawanie i odejmowanie

Dodawanie i odejmowanie wykonuje się przez dodanie lub odjęcie dwóch z tych wielomianów razem i zmniejszenie wyniku modulo charakterystyki.

W skończonym polu o charakterystyce 2 dodawanie modulo 2, odejmowanie modulo 2 i XOR są identyczne. Zatem,

Wielomian	( x ⁶ + x ⁴ + x + 1) + ( x ⁷ + x ⁶ + x ³ + x ) = x ⁷ + x ⁴ + x ³ + 1
Dwójkowy	{01010011} + {11001010} = {10011001}
Szesnastkowy	{53} + {CA} = {99}

Przy regularnym dodawaniu wielomianów suma zawierałaby wyraz 2 x ⁶ . Ten wyraz staje się 0 x ⁶ i jest odrzucany, gdy odpowiedź jest zmniejszona modulo 2.

Oto tabela z normalną sumą algebraiczną i charakterystyczną 2 skończoną sumą pól kilku wielomianów:

p ₁	p ₂	p ₁ + p ₂ pod...
p ₁	p ₂	K[x]	GF( ²ⁿ )
x ³ + x + 1	x ³ + x ²	2 x ³ + x ² + x + 1	x ² + x + 1
x ⁴ + x ²	x ⁶ + x ²	x ⁶ + x ⁴ + 2 x ²	x ⁶ + x ⁴
x + 1	x ² + 1	x ² + x + 2	x ² + x
x ³ + x	x ² + 1	x ³ + x ² + x + 1	x ³ + x ² + x + 1
x ² + x	x ² + x	2 x ² i 2 x	0

W zastosowaniach informatycznych uproszczono operacje dla pól skończonych o charakterystyce 2, zwanych również polami GF(2 ⁿ ) Galois , co sprawia, że pola te są szczególnie popularne w zastosowaniach.

Mnożenie

Mnożenie w dziedzinie skończonych mnożenie modulo nierozkładalny zmniejszenie Wielomian wykorzystywany do określenia skończonego. (Tj. jest to mnożenie, po którym następuje dzielenie, przy użyciu wielomianu redukującego jako dzielnika — reszta jest iloczynem). Symbolu „•” można użyć do oznaczenia mnożenia w skończonym polu.

Pole skończone Rijndaela (AES)

Rijndael (standaryzowany jako AES) wykorzystuje charakterystyczne 2 pole skończone z 256 elementami, które można również nazwać polem Galois GF (2 ⁸ ). Wykorzystuje następujący wielomian redukcyjny do mnożenia:

x ⁸ + x ⁴ + x ³ + x + 1.

Na przykład {53} • {CA} = {01} w polu Rijndaela, ponieważ

	( x ⁶ + x ⁴ + x + 1)( x ⁷ + x ⁶ + x ³ + x )
=	( x ¹³ + x ¹² + x ⁹ + x ⁷ ) + ( x ¹¹ + x ¹⁰ + x ⁷ + x ⁵ ) + ( x ⁸ + x ⁷ + x ⁴ + x ² ) + ( x ⁷ + x ⁶ + x ³ + x )
=	x ¹³ + x ¹² + x ⁹ + x ¹¹ + x ¹⁰ + x ⁵ + x ⁸ + x ⁴ + x ² + x ⁶ + x ³ + x
=	x ¹³ + x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x

oraz

	x ¹³ + x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x mod x ⁸ + x ⁴ + x ³ + x ¹ + 1
=	(11111101111110 mod 100011011)
=	{3F7E mod 11B} = {01}
=	1 (dziesiętny)

To ostatnie można zademonstrować za pomocą dzielenia długiego (pokazanego za pomocą notacji binarnej, ponieważ dobrze nadaje się do zadania. Zwróć uwagę, że w przykładzie zastosowano wyłączne OR, a nie odejmowanie arytmetyczne, jak można by użyć w przypadku dzielenia w szkole podstawowej):

                        
          11111101111110 (mod) 100011011
         ^100011011     
          01110000011110
          ^100011011    
           0110110101110
           ^100011011   
            010101110110
            ^100011011  
             00100011010
              ^100011011  
               000000001

(Elementy {53} i {CA} są odwrotnością multiplikatywną, ponieważ ich iloczyn wynosi 1 .)

Mnożenie w tym konkretnym polu skończonym można również wykonać za pomocą zmodyfikowanej wersji „ algorytmu chłopskiego ”. Każdy wielomian jest reprezentowany przy użyciu tej samej notacji binarnej, jak powyżej. Osiem bitów jest wystarczające, ponieważ możliwe są tylko stopnie od 0 do 7 w warunkach każdego (zredukowanego) wielomianu.

Algorytm ten wykorzystuje trzy zmienne (w sensie programowania komputerowego), z których każda zawiera ośmiobitową reprezentację. a i b są inicjowane z mnożnikami; p akumuluje produkt i musi być zainicjowany na 0.

Na początku i na końcu algorytmu oraz na początku i na końcu każdej iteracji ten niezmiennik jest prawdziwy: a b + p jest iloczynem. Jest to oczywiście prawdą, gdy algorytm się uruchamia. Gdy algorytm się zakończy, a lub b będą wynosić zero, więc p będzie zawierało iloczyn.

Uruchom następującą pętlę osiem razy (raz na bit). Można zatrzymać się, gdy a lub b wynosi zero przed iteracją:
1. Jeśli ustawiony jest najbardziej prawy bit z b , wyłącz LUB iloczyn p o wartość a . To jest dodawanie wielomianowe.
2. Przesuń b o jeden bit w prawo, odrzucając skrajny prawy bit i sprawiając, że skrajny lewy bit ma wartość zero. Dzieli wielomian przez x , odrzucając wyraz x ⁰ .
3. Śledź, czy skrajny lewy bit a jest ustawiony na jeden i wywołaj tę wartość carry .
4. Przesuń o jeden bit w lewo, odrzucając skrajny lewy bit i zmieniając nowy skrajny prawy bit na zero. To mnoży wielomian przez x , ale nadal musimy wziąć pod uwagę przeniesienie, które reprezentuje współczynnik x ⁷ .
5. Jeśli przeniesienie miało wartość jeden, wyłączne lub a z liczbą szesnastkową 0x1b(00011011 w formacie binarnym). 0x1bodpowiada wielomianowi nierozkładalnemu z wyeliminowanym wysokim członem. Koncepcyjnie, wysoki człon wielomianu nierozkładalnego i przeniesienia dodają modulo 2 do 0.
p ma teraz produkt

Algorytm ten łatwo uogólnia się na mnożenie przez inne pola o charakterystyce 2, zmieniając odpowiednio długości a , b , p oraz wartość 0x1b.

Odwrotność mnożenia

Zobacz także Algorytm inwersji Itoh-Tsujii .

Liczba odwrotna dla elementu A skończonego pola można obliczyć wiele różnych sposobów:

Mnożąc a przez każdą liczbę w polu, aż iloczyn będzie jeden. To jest wyszukiwanie brutalne .
Ponieważ niezerowe elementy GF( p ⁿ ) tworzą skończoną grupę w odniesieniu do mnożenia, a ^{p ⁿ -1} = 1 (dla a ≠ 0 ), stąd odwrotnością a jest a ^{p ⁿ -2} .
Korzystając z rozszerzonego algorytmu Euklidesa .
Tworząc logarytm i tabele potęgowania dla ciała skończonego, odejmując logarytm od p ⁿ -1 i potęgując wynik.
Tworząc modułową tablicę odwrotną multiplikatywną dla ciała skończonego i wykonując wyszukiwanie.
Przez mapowanie do pola złożonego, w którym inwersja jest prostsza, i mapowanie wsteczne.
Poprzez skonstruowanie specjalnego całkowitą (w przypadku ograniczonym zakresie doskonałej aby) lub specjalnym wielomianu (w przypadku ograniczonym zakresie z drugorzędnych kolejności), a następnie dzieląc je przez .

Sztuczki wdrożeniowe

Tabele oparte na generatorach

Podczas opracowywania algorytmów do obliczania pola Galois na małych polach Galois, powszechnym podejściem do optymalizacji wydajności jest znalezienie generatora g i użycie tożsamości:

{\ Displaystyle ab = g ^ {\ log _ {g} (ab)} = g ^ {\ log _ {g} (a) + \ log _ {g} (b)}}

zaimplementować mnożenie jako sekwencję wyszukiwań w tabeli dla funkcji log _g ( a ) i g ^y oraz operacji dodawania liczb całkowitych. Wykorzystuje to właściwość, że każde skończone pole zawiera generatory. W przykładzie pola Rijndaela, wielomian x + 1 (lub {03}) jest jednym z takich generatorów. Warunkiem koniecznym, ale niewystarczającym, aby wielomian był generatorem, jest bycie nieredukowalnym .

Implementacja musi testować pod kątem szczególnego przypadku, gdy a lub b ma wartość zero, ponieważ iloczyn również będzie wynosił zero.

Ta sama strategia może być użyta do określenia odwrotności multiplikatywnej z tożsamością:

{\ Displaystyle a ^ {-1} = g ^ {\ log _ {g} \ lewo (a ^ {-1} \ prawej)} = g ^ {- \ log _ {g} (a)} = g ^ {|g|-\log _{g}(a)}}

Tutaj kolejność generatora, | g |, to liczba niezerowych elementów pola. W przypadku GF(2 ⁸ ) jest to 2 ⁸ − 1 = 255 . To znaczy, dla przykładu Rijndaela: (x + 1) ²⁵⁵ = 1 . Można to zrobić za pomocą dwóch tabel przeglądowych i odejmowania liczb całkowitych. Korzystanie z tego pomysłu do potęgowania również czerpie korzyści:

{\ Displaystyle a ^ {n} = g ^ {\ log _ {g} \ lewo (a ^ {n} \ prawej)} = g ^ {n \ log _ {g} (a)} = g ^ {n \log _{g}(a){\pmod {|g|}}}}

Wymaga to dwóch przeszukań tabeli, mnożenia liczb całkowitych i operacji modulo na liczbach całkowitych. Ponownie należy przeprowadzić test dla szczególnego przypadku a = 0.

Jednak w implementacjach kryptograficznych należy być ostrożnym z takimi implementacjami, ponieważ architektura pamięci podręcznej wielu mikroprocesorów prowadzi do zmiennego taktowania dostępu do pamięci. Może to prowadzić do implementacji, które są podatne na atak czasowy .

Mnożenie bez noszenia

Dla pól binarnych GF(2^ n ), mnożenie pól może być zaimplementowane przy użyciu mnożenia bez przenoszenia, takiego jak zestaw instrukcji CLMUL , który jest dobry dla n <= 64. Mnożenie używa jednego mnożenia bez przenoszenia w celu wytworzenia iloczynu (do 2 n - 1 bit), kolejna beznośna wielokrotność wstępnie obliczonej odwrotności wielomianu pola w celu uzyskania ilorazu = ⌊ produkt / (wielomian pola) ⌋ , pomnożenie ilorazu przez wielomian pola, a następnie xor: wynik = iloczyn ⊕ ( (wielomian pola) ⌊ iloczyn / (wielomian pola) ⌋). Ostatnie 3 kroki (pclmulqdq, pclmulqdq, xor) są używane w kroku redukcji Barretta do szybkiego obliczenia CRC przy użyciu instrukcji X86 pclmulqdq.

Pole złożone

Gdy $k$ jest liczbą złożoną , będą istniały izomorfizmy od pola binarnego GF(2 ^k ) do pola rozszerzenia jednego z jego podpól, czyli GF((2 ^m ) ⁿ ) gdzie k = m n . Wykorzystanie jednego z tych izomorfizmów może uprościć rozważania matematyczne, ponieważ stopień rozszerzenia jest mniejszy, ponieważ elementy są teraz reprezentowane na większym podpolu. Aby zmniejszyć liczbę bramek dla implementacji sprzętowych, proces może obejmować wielokrotne zagnieżdżanie, takie jak mapowanie z GF( ²⁸ ) na GF((( ²² ) ² ) ² ). Istnieje ograniczenie implementacyjne, operacje w dwóch reprezentacjach muszą być kompatybilne, więc potrzebne jest wyraźne użycie izomorfizmu. Dokładniej, izomorfizm będzie oznaczany przez map(), jest to bijekcja odwzorowująca element GF(2 ^k ) na GF((2 ^m ) ⁿ ), spełniając: map(a+b) = map(a) + map(b) i map(ab) = map(a) map(b), gdzie operacje po lewej stronie występują w GF(2 ^k ) przed mapowaniem, a operacje po prawej stronie występują w GF((2 ^m ) ⁿ ) po mapowaniu. Izomorfizm jest zwykle implementowany z macierzą k wiersz przez k bitów, używaną do wykonania mnożenia macierzy przez GF(2) elementu GF(2 ^k ) traktowanego jako macierz k wiersz przez 1 bit. Zdefiniuj α jako element pierwotny GF(2 ^k ), a β jako element pierwotny GF((2 ^m ) ⁿ ). Wtedy β ^j = mapa(α ^j ) i α ^j = mapa ^-1 (β ^j ). Wartości α i β określają macierz odwzorowania i jej odwrotność. Ponieważ rzeczywista matematyka jest wykonywana w GF(( ^2m ) ⁿ ), wielomian redukujący dla GF(( ^2m ) ⁿ ) jest zwykle prymitywny, a β = x w GF(( ^2m ) ⁿ ). W celu spełnienia ograniczenia kompatybilności dla dodawania i mnożenia, przeprowadza się wyszukiwanie w celu wybrania dowolnego elementu pierwotnego α z GF( ^2k ), który spełni to ograniczenie. W przypadku, gdy wielomian redukcyjny dla GF(2 ^k ) jest pierwotny, możliwa jest alternatywna metoda mapowania: 1-bitowe współczynniki wielomianu redukującego dla GF(2 ^k ) są interpretowane jako m bitowych elementów 0 lub 1 z GF(2 ^m ) i będzie m prymitywnych czynników stopnia n , z których każdy może być użyty jako wielomian redukujący dla GF((2 ^m ) ⁿ ). Mapowanie polu kompozytowego może być uogólnione do mapowania GF ( s ^k ) w dziedzinie kompozytowych, takich jak GF (( P ^m ) ⁿ ), na str doskonałą wartość większą niż 2, a te obszary nie są powszechnie stosowane w praktyce.

Przykłady programów

Przykład programowania w C

Oto kod w języku C, który będzie dodawał i mnożył liczby w charakterystycznym 2 skończonym polu rzędu 2 ⁸ , używanym na przykład przez algorytm Rijndaela lub Reeda-Solomona, wykorzystujący algorytm mnożenia rosyjskiego chłopa :

/* Add two numbers in the GF(2^8) finite field */
uint8_t gadd(uint8_t a, uint8_t b) {
	return a ^ b;
}

/* Multiply two numbers in the GF(2^8) finite field defined 
 * by the polynomial x^8 + x^4 + x^3 + x + 1 = 0
 * using the Russian Peasant Multiplication algorithm
 * (the other way being to do carry-less multiplication followed by a modular reduction)
 */
uint8_t gmul(uint8_t a, uint8_t b) {
	uint8_t p = 0; /* the product of the multiplication */
	while (a && b) {
            if (b & 1) /* if b is odd, then add the corresponding a to p (final product = sum of all a's corresponding to odd b's) */
                p ^= a; /* since we're in GF(2^m), addition is an XOR */

            if (a & 0x80) /* GF modulo: if a >= 128, then it will overflow when shifted left, so reduce */
                a = (a << 1) ^ 0x11b; /* XOR with the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
            else
                a <<= 1; /* equivalent to a*2 */
            b >>= 1; /* equivalent to b // 2 */
	}
	return p;
}

W tym przykładzie występują wycieki w pamięci podręcznej, taktowaniu i przewidywaniu rozgałęzień w kanale bocznym i nie nadaje się do użytku w kryptografii.

Przykład programowania D

Ten program D mnoży liczby w skończonym polu Rijndaela i generuje obraz PGM :

/**
Multiply two numbers in the GF(2^8) finite field defined
by the polynomial x^8 + x^4 + x^3 + x + 1.
*/
ubyte gMul(ubyte a, ubyte b) pure nothrow {
    ubyte p = 0;

    foreach (immutable ubyte counter; 0 .. 8) {
        p ^= -(b & 1) & a;
        auto mask = -((a >> 7) & 1);
        // 0b1_0001_1011 is x^8 + x^4 + x^3 + x + 1.
        a = cast(ubyte)((a << 1) ^ (0b1_0001_1011 & mask));
        b >>= 1;
    }

    return p;
}

void main() {
    import std.stdio, std.conv;
    enum width = ubyte.max + 1, height = width;

    auto f = File("rijndael_finite_field_multiplication.pgm", "wb");
    f.writefln("P5\n%d %d\n255", width, height);
    foreach (immutable y; 0 .. height)
        foreach (immutable x; 0 .. width) {
            immutable char c = gMul(x.to!ubyte, y.to!ubyte);
            f.write(c);
        }
}

Ten przykład nie używa żadnych rozgałęzień ani przeszukiwania tabel w celu uniknięcia kanałów bocznych i dlatego nadaje się do użycia w kryptografii.

Zobacz też

logarytm Zecha

Bibliografia

Źródła

Lidla, Rudolfa; Niederreiter, Harald (1983), Pola skończone , Addison-Wesley, ISBN 0-201-13519-1(ponownie wydany w 1984 roku przez Cambridge University Press ISBN 0-521-30240-4 ).
Mullen, Gary L.; Panario, Daniel (2013), Podręcznik pól skończonych , CRC Press, ISBN 978-1-4398-7378-6

Zewnętrzne linki

Gordon, G. (1976). „Bardzo prosta metoda znajdowania minimalnego wielomianu dowolnego niezerowego elementu pola skończonego”. Listy elektroniczne . 12 (25): 663-664. doi : 10.1049/el: 19760508 .
da Rocha, VC; Markarian, G. (2006). „Prosta metoda znalezienia śladu dowolnego elementu pola skończonego”. Listy elektroniczne . 42 (7): 423-325. doi : 10.1049/el:20060473 .
Trenholme, Sam. "Pole Galois AE" .
Planck, James S. (2007). "Szybka biblioteka arytmetyczna pól Galois w C/C++" .
Wikiversity: Reed–Solomon for Coders – Arytmetyka pól skończonych

Languages

In other projects