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ą
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:
Trzeba zmienić na: