Odpowiednik mnożenia z dodawaniem modulo 2^n w ciałach Galois

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

Odpowiednik mnożenia z dodawaniem modulo 2^n w ciałach Galois

Post autor: matemix »

Próbuję skonstruować generator liczb pseudolosowych LCG mod \(\displaystyle{ 2^{n}}\), ale w GF. Generator LCG tworzy kolejne liczby poprzez iterowanie:

\(\displaystyle{ x_{n+1} = x_{n} \cdot a + c \mod 2^{m}}\)

Nie wdając się w szczegóły, przyjmijmy, że \(\displaystyle{ a}\) i \(\displaystyle{ c}\) są liczbami 16-bitowymi i na potrzeby przykładu \(\displaystyle{ m=16}\).

Potrzebuję zatem analogu 16-bitowego mnożenia i dodawania w GF. To znaczy funkcja ma mieć zdefiniowane jakieś dwie stałe i przyjmować liczbę 16-bitową oraz zwracać liczbę 16-bitową. Ale działania mają być w GF. Pytanie jakiego GF użyć? Co jest w GF naturalnym odpowiednikiem mnożenia 16-bitowego?

Myślałem o tym, żeby rozpatrywać GF(2), z jakimś wielomianem nierozkładalnym, np. \(\displaystyle{ x+1}\). Ale, czy to ma sens? Możemy sobie mnożyć wtedy dowolne liczby:

Kod: Zaznacz cały

ee.unb.ca/cgi-bin/tervo/calc2.pl
a współczynniki wielomianów będą jak w liczbach binarnych równe zawsze tylko zero lub jeden (i ciągi tych współczynników możemy traktować jak zwykłe liczby binarne). Ale te liczby mogą być dowolnie duże, jeśli dobrze rozumiem arytmetykę GF. Więc następnie i tak musimy je skrócić \(\displaystyle{ \mod 2^{16}}\), żeby pozostać w liczbach 16-bitowych. I tutaj coś mi się nie zgadza, bo wydawało mi się, że wielomian nierozkładalny stopnia \(\displaystyle{ n}\) nie powinien pozwolić na uzyskanie liczby większej niż n-bitowa. I po co mi w ogóle wielomian nierozkładalny, skoro i tak skracam wynik \(\displaystyle{ \mod 2^{16}}\).

Więc jak zdefiniować mnożenie 16-bitowe, ale w GF?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Odpowiednik mnożenia z dodawaniem modulo 2^n w ciałach Galois

Post autor: Dasio11 »

Jeśli dobrze rozumiem, pytasz jak elementy ciała skończonego mocy \(\displaystyle{ 2^{16}}\) reprezentować za pomocą liczb szesnastobitowych i jak w tej reprezentacji wygląda mnożenie i dodawanie.

Takie ciało jest postaci \(\displaystyle{ \ZZ_2[x]/(p(x))}\) dla jakiegokolwiek wielomianu \(\displaystyle{ p(x) \in \ZZ_2[x]}\) stopnia \(\displaystyle{ 16}\) nierozkładalnego w \(\displaystyle{ \ZZ_2[x]}\). Musisz zatem wybrać taki wielomian, a wtedy:

1. Dowolny element ciała jest postaci \(\displaystyle{ c_0 + c_1 x + c_2 x^2 + \ldots + c_{15} x^{15} + (p(x))}\), gdzie \(\displaystyle{ c_i \in \{ 0, 1 \}}\), i można go reprezentować ciągiem bitów \(\displaystyle{ c_{15} \ldots c_1 c_0}\).

2. Dodawanie elementów w tej reprezentacji jest bardzo proste, bo to zwyczajny bitwise xor liczb szesnastobitowych.

3. Żeby pomnożyć elementy reprezentowane ciągami \(\displaystyle{ a_{15} \ldots a_1 a_0}\) i \(\displaystyle{ b_{15} \ldots b_1 b_0}\), trzeba:

- zinterpretować te ciągi jako wielomiany \(\displaystyle{ a_0 + a_1 x + \ldots + a_{15} x^{15}}\) i \(\displaystyle{ b_0 + b_1 x + \ldots + b_{15} x^{15}}\);

- pomnożyć te wielomiany w \(\displaystyle{ \ZZ_2[x]}\), otrzymując

\(\displaystyle{ c_0 + c_1 x + \ldots + c_{30} x^{30} = \big( a_0 + a_1 x + \ldots + a_{15} x^{15} \big) \odot \big( b_0 + b_1 x + \ldots + b_{15} x^{15} \big)}\);

- podzielić ten wielomian pisemnie przez wybrany na początku \(\displaystyle{ p(x)}\) w pierścieniu \(\displaystyle{ \ZZ_2[x]}\), otrzymując resztę \(\displaystyle{ d_0 + d_1 x + \ldots + d_{15} x^{15}}\);

- wynik mnożenia jest reprezentowany ciągiem \(\displaystyle{ d_{15} \ldots d_1 d_0}\).

Kod w C++ wyglądałby mniej-więcej tak:

Kod: Zaznacz cały

typedef unsigned short int uint;

uint p = ...; 


uint add( uint a, uint b )
{
    return a ^ b;
}

uint multiply( uint a, uint b )
{
    unsigned int c = 0;
    
    for( unsigned int i = 0; i < 16; ++i )
    {
        c ^= a & ( 1 << i ) ? (unsigned int) b << i : 0;
    }
    
    for( unsigned int i = 16; i --> 0 ; )
    {
        if( c & ( 1 << ( i + 16 ) ) )
        {
            c ^= 1 << ( i + 16 );
            c ^= (unsigned int) p << i;
        }
    }
    
    return (uint) c;
}
Do zmiennej p musisz wpisać ciąg bitów \(\displaystyle{ p_{15} \ldots p_1 p_0}\), gdzie \(\displaystyle{ p(x) = p_0 + p_1 x + \ldots + p_{15} x^{15} + x^{16}}\) jest wybranym wielomianem nierozkładalnym nad \(\displaystyle{ \ZZ_2[x]}\) stopnia \(\displaystyle{ 16}\).
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

Re: Odpowiednik mnożenia z dodawaniem modulo 2^n w ciałach Galois

Post autor: matemix »

Ok. Trochę mi rozjaśniło, ale mam dużo pytań.

1. Piszesz, że:
Dodawanie elementów w tej reprezentacji jest bardzo proste, bo to zwyczajny bitwise xor liczb szesnastobitowych.
To robisz jak rozumiem w pętli:

Kod: Zaznacz cały

for( unsigned int i = 0; i < 16; ++i )
    {
        c ^= a & ( 1 << i ) ? (unsigned int) b << i : 0;
    }
Czyli przesuwamy naszą liczbę w lewo i xorujemy z poprzednikiem, pod warunkiem, że bit liczby \(\displaystyle{ a}\) jest równy jeden. Rozumiem, że unsigned int jest 32-bitowe - czyli wystarczy, żeby zmieścić dowolny wynik mnożenia dwóch liczb 16-bitowych. A ja tak naprawdę chciałem działać na liczbach 64-bitowych. Przykład liczb 16-bitowych podałem, żeby nie komplikować. W c++ jest jednak problem, żeby robić te operacje na 128-bitowych intach, ja u siebie na Windowsie nie mam żadnych 128-bitowych intów dostępnych (podobno występują na Linuxie), a nie chcę używać SSE. Generalnie komputery działają na architekturze 64-bitowej, więc większość nie będzie potrafiła przesunąć 64-bitowej liczby w lewo. Czy da się to jakoś ominąć?

Ogólnie zastanawiają mnie zwłaszcza urządzenia bez wbudowanych instrukcji mnożenia (tam nie doinstalujemy żadnych 128-intowych bibliotek, ani nie ma SSE, nie ma w ogóle instrukcji mnożenia). Dlatego też myślę o mnożeniu w GF (bo do tego wystarczy tylko << i &). Pytanie, czy wykonywanie tam mnożenia 64-bitowego w GF nie będzie jeszcze większym problemem, niż normalnie mnożenie 64-bitowe?

2. Rozumiem, że w tej pętli:

Kod: Zaznacz cały

for( unsigned int i = 16; i --> 0 ; )
    {
        if( c & ( 1 << ( i + 16 ) ) )
        {
            c ^= 1 << ( i + 16 );
            c ^= (unsigned int) p << i;
        }
    }
Skracasz wynik mod nierozkładalny wielomian? Jeśli dobrze rozumiem, to, jeśli najwyższy bit jest jedynką, zamieniamy go na zero i xorujemy \(\displaystyle{ c}\) z wielomaniem. Pierwszy raz widzę tę procedurę i nie wiedziałem jak można to robić szybko w praktyce. Zastanawia mnie tylko dlaczego \(\displaystyle{ i}\) jest zmniejszane o 2. Jak rozumiem za pomocą

Kod: Zaznacz cały

if( c & ( 1 << ( i + 16 ) ) )
sprawdzamy bity \(\displaystyle{ 32,30,28,...}\), a później xorujemy z przesuniętym wielomianem. Skąd wynika ten skok o \(\displaystyle{ 2}\) w pętli? Choć domyślam się, że tak pewnie po prostu wychodzi z definicji i nie ma głębszego wyjaśnienia.

3. Ten kalkulator wydaje się przeczyć przykładom powyżej albo coś w nim działa źle:

Kod: Zaznacz cały

ee.unb.ca/cgi-bin/tervo/calc2.pl?num=1+0+1&den=1+1+1+1+1+0+1&f=m&p=7&d=1&y=1
Można tam pomnożyć dwie dowolne liczby ze współczynnikami zero i jeden, ale nigdy nie są one skracane za pomocą wielomianu. W wyniku dostaję np:
1 x8 + 1 x7 + 0 x6 + 0 x5 + 0 x4 + 1 x3 + 0 x2 + 0 x + 1
Pomimo wielomianu:
x5 + x3 + 1
Jak może być w wyniku \(\displaystyle{ x^{8}}\), skoro stopień wielomianu to \(\displaystyle{ x^{5}}\)? Czy oni podają wyniki mnożenia bez skrócenia tego za pomocą wielomianu? Po co więc jest opcja wyboru wielomianu?

Dodano po 1 godzinie 13 minutach 32 sekundach:
Dasio11 pisze: 10 maja 2022, o 17:28 Do zmiennej p musisz wpisać ciąg bitów \(\displaystyle{ p_{15} \ldots p_1 p_0}\), gdzie \(\displaystyle{ p(x) = p_0 + p_1 x + \ldots + p_{15} x^{15} + x^{16}}\) jest wybranym wielomianem nierozkładalnym nad \(\displaystyle{ \ZZ_2[x]}\) stopnia \(\displaystyle{ 16}\).
Czy ten wielomian nie powinien być stopnia \(\displaystyle{ 15}\), skoro chcemy 16-bitowych wyników?

Dodano po 6 godzinach 51 minutach 30 sekundach:
Widzę, że do mnożenia 64-bitowego w GF nadaje się CLMUL instruction set:

Kod: Zaznacz cały

en.wikipedia.org/wiki/CLMUL_instruction_set
CLMUL instruction set

Ale jak tego użyć w c++ nie mam pojęcia.

Dodano po 22 godzinach 34 minutach 15 sekundach:
W kodzie takie rzeczy jak:

Kod: Zaznacz cały

1 << ( i + 16 )
Trzeba zmienić na:

Kod: Zaznacz cały

1L << ( i + 16 )
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Odpowiednik mnożenia z dodawaniem modulo 2^n w ciałach Galois

Post autor: Dasio11 »

matemix pisze: 12 maja 2022, o 09:19W c++ jest jednak problem, żeby robić te operacje na 128-bitowych intach, ja u siebie na Windowsie nie mam żadnych 128-bitowych intów dostępnych (podobno występują na Linuxie), a nie chcę używać SSE. Generalnie komputery działają na architekturze 64-bitowej, więc większość nie będzie potrafiła przesunąć 64-bitowej liczby w lewo. Czy da się to jakoś ominąć?
Matematycznie raczej nie, ale na poziomie kodu oczywiście jest mnóstwo spososów. Można zwyczajnie zdefiniować typ przechowujący liczby 128-bitowe i operacje arytmetyczne na takich liczbach. Można też nieco sprytniej napisać algorytm mnożenia - znów mniej-więcej:

Kod: Zaznacz cały

uint multiply( uint a, uint b )
{
    uint m = 0;
    
    while( a > 0 )
    {
        if( a & 1 ) m ^= b;
        a >>= 1;
        
        b = ( b << 1 ) ^ ( b >> 31 ? p : 0 );
    }
    
    return m;
}
Funkcja działa dzięki tożsamości

\(\displaystyle{ (a_0 + a_1 x + \ldots + a_{15} x^{15}) \odot b(x) = \sum_{\substack{0 \le k \le 15 \\ a_k = 1}} x^k \cdot b(x)}\).

Instrukcja b = ( b << 1 ) ^ ( b >> 31 ? p : 0 ); sprawia, że po \(\displaystyle{ k}\)-tym przebiegu pętli zmienna b zawiera reprezentację elementu \(\displaystyle{ x^k \cdot b(x)}\) (w duchu programowania dynamicznego), a reszta kodu odpowiada za sumę.

matemix pisze: 12 maja 2022, o 09:19Ogólnie zastanawiają mnie zwłaszcza urządzenia bez wbudowanych instrukcji mnożenia [...] Pytanie, czy wykonywanie tam mnożenia 64-bitowego w GF nie będzie jeszcze większym problemem, niż normalnie mnożenie 64-bitowe?
Nie sądzę, bo przecież nawet powyższy algorytm jest wcale nie trudniejszy niż ręcznie napisane mnożenie.

matemix pisze: 12 maja 2022, o 09:192. Rozumiem, że w tej pętli:

Kod: Zaznacz cały

for( unsigned int i = 16; i --> 0 ; )
    {
        if( c & ( 1 << ( i + 16 ) ) )
        {
            c ^= 1 << ( i + 16 );
            c ^= (unsigned int) p << i;
        }
    }
Skracasz wynik mod nierozkładalny wielomian?
Tak - ale o poprzednim algorytmie możesz w zasadzie zapomnieć, bo ten nowy bardziej mi się podoba. ;P

matemix pisze: 12 maja 2022, o 09:19Zastanawia mnie tylko dlaczego \(\displaystyle{ i}\) jest zmniejszane o 2.
A jest?

matemix pisze: 12 maja 2022, o 09:193. Ten kalkulator wydaje się przeczyć przykładom powyżej albo coś w nim działa źle:
Istotnie, ten kalkulator jest bez sensu, bo podaje tylko iloczyn wielomianów bez jego redukowania.

matemix pisze: 12 maja 2022, o 09:19Czy ten wielomian nie powinien być stopnia \(\displaystyle{ 15}\), skoro chcemy 16-bitowych wyników?
Nie, dlaczego? Reszta z dzielenia przez wielomian stopnia \(\displaystyle{ 16}\) jest zawsze wielomianem stopnia najwyżej \(\displaystyle{ 15}\), czyli dokładnie takim, jakiego potrzeba by reprezentować elementy ciała mocy \(\displaystyle{ 2^{16}}\).

matemix pisze: 12 maja 2022, o 09:19W kodzie takie rzeczy jak:

Kod: Zaznacz cały

1 << ( i + 16 )
Trzeba zmienić na:

Kod: Zaznacz cały

1L << ( i + 16 )
Dlaczego?
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

Re: Odpowiednik mnożenia z dodawaniem modulo 2^n w ciałach Galois

Post autor: matemix »

Dasio11 pisze: 12 maja 2022, o 16:53 Można też nieco sprytniej napisać algorytm mnożenia - znów mniej-więcej:
Tego jak na razie nie rozumiem. Ale działa tak samo, jak poprzedni.
Tak - ale o poprzednim algorytmie możesz w zasadzie zapomnieć, bo ten nowy bardziej mi się podoba. ;P
Ten stary jest dla mnie przydatny, bo wykonuje osobno mnożenie, a nawiązując do CLMUL instruction set, który służy do szybszego mnożenia carry-less, o którym pisałem, udało mi się wdrożyć te instrukcje:

Kod: Zaznacz cały

uint32_t multiply(uint32_t a, uint32_t b)
{
    uint64_t c = 0;

    __m128i result = _mm_clmulepi64_si128(_mm_set_epi64x(0, a), _mm_set_epi64x(0, b), 0);

    c = _mm_cvtsi128_si64(result);
I trochę przyspieszyć kod, między innymi dzięki temu, że mnożenie mam osobno w kodzie, a dopiero później redukcję mod wielomian. Nadal jednak jest to kosztowne, bo kosztowna jest sama redukcja. Ludzie znaleźli pewne algorytmy, żeby mnożyć szybko i redukować nawet w \(\displaystyle{ GF(2^{128})}\), co jest użyteczne między innymi w trybie Galos Counter Mode w AES:

Kod: Zaznacz cały

sciencedirect.com/science/article/abs/pii/S002001901000092X
Używają tam właśnie instrukcji CLMUL oraz dosyć szczególnego wielomianu stopnia \(\displaystyle{ 128}\). W ogólności jednak w porównaniu do zwykłego mnożenia nawet mając instrukcje PCLMULQDQ mnożenie w \(\displaystyle{ GF(2^k)}\) jest kosztowne w porównaniu do normalnego mnożenia modulo, bo wciąż zostaje problem redukcji wyniku przez wielomian.
A jest?
Nie jest, moja pomyłka, jestem początkujący w c++ i nie zrozumiałem co robi ta pętla.
Istotnie, ten kalkulator jest bez sensu, bo podaje tylko iloczyn wielomianów bez jego redukowania.
Na szczęście, bo już myślałem, że z rozumieniem arytmetyki GF nadal jestem w polu.
Dasio11 pisze: 12 maja 2022, o 16:53
matemix pisze: 12 maja 2022, o 09:19W kodzie takie rzeczy jak:

Kod: Zaznacz cały

1 << ( i + 16 )
Trzeba zmienić na:

Kod: Zaznacz cały

1L << ( i + 16 )
Dlaczego?
Na przykład tutaj:

Kod: Zaznacz cały

programiz.com/cpp-programming/online-compiler/
Oblicza mi \(\displaystyle{ c}\):

Kod: Zaznacz cały

#include <iostream>

uint64_t c;

int main() {

    c = 1 << 37;
    std::cout << c;

    return 0;
}
jako zero. A w tym przypadku dostaję wynik \(\displaystyle{ 32}\):

Kod: Zaznacz cały

#include <iostream>

unsigned int i = 5;
uint64_t c;

int main() {

    c = 1 << (i + 32);
    std::cout << c;

    return 0;
}
Pomimo, że powinien wynosić \(\displaystyle{ 2^{37}}\).
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Odpowiednik mnożenia z dodawaniem modulo 2^n w ciałach Galois

Post autor: Dasio11 »

matemix pisze: 13 maja 2022, o 01:47

Kod: Zaznacz cały

#include <iostream>

uint64_t c;

int main() {

    c = 1 << 37;
    std::cout << c;

    return 0;
}
W C++ przesuwanie o liczbę bitów większą lub równą rozmiarowi przesuwanego typu powoduje undefined behavior. W powyższym kodzie 1 jest typu int mającego zazwyczaj 32 bity, więc nie można jej przesunąć o 37 bitów (a przypisanie do zmiennej c mającej 64 bity niczego nie zmienia, bo wykona się później).

Natomiast tu:
matemix pisze: 12 maja 2022, o 09:19W kodzie takie rzeczy jak:

Kod: Zaznacz cały

1 << ( i + 16 )
przesuwanie jest zawsze o najwyżej 31, więc nie trzeba niczego zmieniać.
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

Re: Odpowiednik mnożenia z dodawaniem modulo 2^n w ciałach Galois

Post autor: matemix »

Tak, masz rację, już doczytałem o co chodzi. Dzięki za te dwa kody, bardzo mi się przydadzą.
ODPOWIEDZ