Kody i szyfry

Zapis resztowy to inaczej zapis rezidualny lub zapis RNS (od ang. Residue Number System). Koncepcja zapisu rezidualnego (lub nieco ogólniej arytmetyki ) pochodzi od A.Svobody i M.Valacha i została podana w pracy zamieszczonej w czeskim czasopiśmie ”Stroje na Zapracovani Informaci” w roku 1955. Niezależnie od A.Svobody i M.Valacha pomysł zapisu rezidualnego podał w 1959 r. H.L.Garner w pracy opublikowanej w IRE Transactions EC-8.

Zapis resztowy umożliwia realizację szybkiej arytmetyki (dokładniej: dodawania, odejmowania i mnożenia) bez propagacji przeniesień. Mnożenia które są dosyć złożonymi działaniami (a np. w cyfrowym przetwarzaniu sygnałów mnożeń wykonujemy bardzo dużo) można jak zobaczymy wykonywać bardzo szybko i prosto. Skomplikowane stają się natomiast w zapisie RNS algorytmy dzielenia i porównania liczb.

Symbolem $[x]_m$ lub x (mod m) będziemy w dalszym ciągu oznaczać resztę z dzielenia liczby x ∈ Z przez liczbę m ∈ N, m ≥ N, m ≥ 2. Potrzebne nam będzie ponadto pojęcie kongruencji. Niech m ∈ N, m ≥ 2, mówimy, że dwie liczby a, b ∈ Z przystają modulo m jeśli dają tę samą resztę z dzielenia przez m. Zapisujemy to pisząc a ≡ b (mod m). Zapis taki nazywamy kongruencją modulo m.

Podstawą zapisu resztowego jest następujące chińskie twierdzenie o resztach.

Dowód: Możemy znaleźć n liczb c₁c₂,...c_n takich, że c_i ∈ $Z{_m}_{_i}$oraz c_i $\otimes _{m_i} \left[ \frac{M}{m_i} \right]_{m_{i}}$ = 1 (lub równoważnie c_i jest elementem odwrotnym do elementu $\left[ \frac{M}{m_i} \right]_{m_i}$ w pierścieniu $Z_{m_{i}}$ czyli c_i = $\left[ \frac{M}{m_i} \right]^{-i}_{m_{i}}$). Łatwo sprawdzić, że k_i = c_i $\frac{M}{m_i}$ i = 1,2,3,...,n spełniają warunek (**). Wynika to z tego, że NWD($m_i,\left[ \frac{M}{m_i} \right]_{m_i}$) = 1.

Niech będzie dana liczba x ∈ Z i niech liczby naturalne m₁,m₂,...m_n większe od jedności będą parami względnie pierwsze. Zapisem resztowym liczby x nazywamy ciąg skończony

$([x]_{m_1},[x]_{m_2},...x]_{m_n})\qquad$(4)

W ten sposób definiujemy kod numeryczny $f:$ → $Z{_{m_1}} \times Z{_{m_2}} \times ... \times Z{_{m_n}}$. Zakres tak zdefiniowanego zapisu RNS jest oczywiście równy .

Dodawanie, odejmowanie i mnożenie liczb w zapisie resztowym jest wykonywane po współrzędnych. Dokładniej, jeśli mamy 2 liczby zapisane w zapisie resztowym $a$ = $([a]_{m_1},[a]_{m_2},[a]_{m_n})$ = $(a_1, a_2,..., a_n)$ i $b = ([b]_{m_1}, [b]_{m_2},..., [b]_{m_n}$ = $(b_1, b_2, ..., b_n)$ to wówczas (jeśli wynik działania należy do zakresu zapisu) algorytmy dodawania, odejmowania i mnożenia dane są wzorami

$a+b=(b_1,b_2,...b_n) + (b_1, b_2, ...,b_n) = (a_1\oplus_{m_1}b_1, a_2\oplus_{m_2}b_2, ... a_n\oplus_{m_n}b_n)\qquad$(5)

$a-b=(b_1,b_2,...b_n) - (b_1, b_2, ...,b_n) = (a_1-_{m_1}b_1, a_2-_{m_2}b_2, ... a_n-_{m_n}b_n)\qquad$(6)

$a \cdot b=(b_1,b_2,...b_n) \cdot (b_1, b_2, ...,b_n) = (a_1\oplus_{m_1}b_1, a_2\oplus_{m_2}b_2, ... a_n\oplus_{m_n}b_n)\qquad$(7)

gdzie $a_i \oplus _{m_i} b_i$, $a_i - _{m_i} b_i$, $a_i \otimes _{m_i} b_i$ są odpowiednio dodawaniem, odejmowaniem i mnożeniem modulo $m_i$.

Konwersja zapis NKB liczby x → na zapis RNS liczby x sprowadza się do obliczenia n reszt z dzielenia liczby x przez moduły m₁, m₂, m₃, ..., m_n.

Konwersja zapis RNS →  zapis NKB jest nieco bardziej złożona. Podamy dwa algorytmy konwersji.

Podstawowy algorytm konwersji jest na ogół formułowany w samym chińskim twierdzeniu o resztach. Przypomnijmy algorytm:

Niech a₁, a₂, ..., a_n będzie zapisem RNS liczby x oraz M = m₁, m₂, ..., m_n.

I. Znajdujemy liczby b_j ∈ Z takie, że:

b_j ⋅ $\frac{M}{m_j}$ = 1 (mod $m_j$) dla j = 1,2,...n).$\qquad$(8)

II. Jeśli x ∈ [0, M], to

x = [a₁ ⋅b₁ ⋅ $\frac{M}{m_1}$ + a₂ ⋅b₂ ⋅ $\frac{M}{m_2}$ + ... +  a_n ⋅b_n$\frac{M}{m_n}$]_M,$\qquad$(9)

a ogólnie, jeśli x ∈ [a, a + m), to

x = a + (a₁ ⋅b₁ ⋅ $\frac{M}{m_1}$ + a₂ ⋅b₂ ⋅ $\frac{M}{m_2}$ + ... +  a_n ⋅b_n − a)(mod M).$\qquad$(10)

Konwersja wykorzystująca „mixed radix representation” (algorytm Garnera).

I. Niech (a₁, a₂, a₃) będzie zapisem RNS liczby x. Definiujemy  $\binom{n}{2}$ stałych c_ij (liczymy je tylko jeden raz – wstępnie).

c_ij ⋅ m_i ≡ 1 (mod m_j) dla  1 ≤ i < j ≤ n,$\qquad$(11)

lub co na jedno wychodzi, poszukujemy odwrotności elementu $[m_i]_{m_j}$ w pierścieniu $Z_{m_j}$, czyli takiego c_ij, że c_ij $\otimes_{m_j}$ m_j = 1 w pierścieniu $Z_{m_j}$.

II. Obliczamy ciąg v_1, v₂,...v_n gdzie v₁ ∈ [0, m_i, −1) będący zapisem mixed radix szukanej liczby x,

v₁ := a₁ (mod m₁)

v₂ := (a₁ − v₁)c₁₂(mod m₂)

v₃ := ((a₁ − v₁)c₁₃−v₁)c₂₃(mod m₃)$\qquad$(12)
.
.
.
v_r := ((u_n − v₁)c_1r − v₂)c_2n − ...− v_r−1)c_r−1,n (mod m_n)

III. Obliczamy

x = v_n ⋅m_n−1 ⋅ ...⋅ m₁  + v_n−1 ⋅m_n−2⋅ ...⋅m₁  +...+ v₃ ⋅m₂ ⋅m₁ + v₂ ⋅m₁ ⋅v₁ $\qquad$(13)

Łatwo zauważyć, że w zapisie RNS złożoność konwersji z RNS → zapis binarny; zapis binarny RNS w pewnym stopniu zależy od wyboru modułów m₁,m₂,m₃,...m_n.

Dla modułów postaci 2^e − 1 konwersja liczby x na jej zapis RNS jest bardzo prosta.

Ogólnie rzecz biorąc, jeśli mamy liczbę x ∈ Z otrzymujemy jej reprezentację resztową przez dzielenie x przez kolejne moduły m_i, co daje ciąg (a₁,a₂,...a_r). Jednak dla modułów postaci 2^e_i − 1, można zrobić tak:

x = a_tA^t + a_t−1A^t−1 +...+ a₁A + a₀$\qquad$(14)

gdzie A = 2^e_i i 0 ≤ a_k < 2^e_j i dla każdego k = 0,1,...t.

Zatem:

u = a₁ + a_t −1 + ... + a₁ + a₀ (mod 2^e_j − 1)$\qquad$(15)

ponieważ A ≡ (mod 2^e_j − 1) i ostatecznie:

u_i = a₁ $\oplus$ a_t −1 $\oplus$...$\oplus$ a₁₀$\qquad$(16)

u_i = a_t + a_t −1 + ... + a₀ (mod (2^e_j − 1))$\qquad$(17)

Zajmijmy się modułami postaci m_j = 2^e_j − 1, gdzie e_j ∈ N, e_j ≥ 2, dokładniej. Pokażemy jakie korzyści wynikają z wyboru modułów m₁,m₂,...m_r tak, by było m_j = 2^e_j − 1, e_j ∈ N, e_j ≥ 2. Zależy nam na tym, żeby były to moduły parami względnie pierwsze. Następujące twierdzenie stanowi kryterium na to, by dwie liczby postaci 2^{$^f$}− 1 i 2^e − 1 były względnie pierwsze.

Dowód: 1. Zauważmy, że zachodzi równość:

((2^e − 1)(mod 2^{$^f$}− 1)) = 2^{e, (mod $^f$)} − 1$\qquad$(18)

Jeśli e ≤ $f$, to jest to oczywiste. Niech e>$f$. Równość (18) jest równoważna do kongruencji

(2^e − 1) ≡ 2^{e (mod $^f$)} − 1 (mod (2^{$^f$}− 1))$\qquad$(19)

i dalej

2^e ≡ 2^{e mod $^f$} (mod (2^{$^f$}− 1))$\qquad$(20)

2^{e(mod $^f$)} 2^{$^f$}...q^{$^f$} ≡ 2^{e mod $^f$} (mod (2^{$^f$}− 1))$\qquad$(21)

ale: 2^{$^f$} ≡ 1 (mod (2^{$^f$}− 1)) zatem prawdziwa jest równość (18).

2. Wracamy do dowodzonej równości. Niech e>$f$ (dla e=$f$ równość jest oczywista) wówczas na mocy (18) i algorytmu Euklidesa NWD(2^e − 1,2^{$^f$}− 1) = NWD(2^{$^f$}− 1,2^{e mod $^f$} − 1).

Kolejno stosujemy wzór (18), czyli obliczamy resztę z dzielenia przez liczbę mniejszą, zauważmy przy tym, że NWD(e, $f$) = NWD($f$,e (mod $f$)).

Postępując zgodnie z algorytmem Euklidesa otrzymamy wreszcie, w kolejnym kroku, iloraz reszt =0.

Będziemy więc mieli: NWD(2^e − 1,2^{$^f$}− 1) = NWD(2^a− 1,2⁰ − 1) = 2^a − 1

oraz  NWD(e, $f$) = NWD(a₀) = a

Wniosek: Liczby 2^e − 1 i 2^{$^f$} − 1 są względnie pierwsze wtedy i tylko wtedy, gdy e i $f$ są względnie pierwsze.

Słowo maszynowe k-bitowe, ogólnie rzecz biorąc może być jednak takie, że 2^k > m_i lub 2^k < m_i . Jeśli moduły dają się zapisać w kodzie NKB na słowie maszynowym to jest to oczywiście wygodne, ale nie jest to niezbędne.

Zasadnicze znaczenie dla szybkości wykonywania działań arytmetycznych w zapisie resztowym mają sposoby wykonywania działań modulo m. Działania modulo m powinny być realizowane za pomocą odpowiednio zaprojektowanych układów.

Uogólnieniem zapisu RNS na liczby zespolone jest zapis resztowy QRNS (Quadratic Residue Numer System)