Odpowiednik mnożenia z dodawaniem modulo 2^n w ciałach Galois
: 10 maja 2022, o 11:54
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:
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?
\(\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
Więc jak zdefiniować mnożenie 16-bitowe, ale w GF?