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: <0, m_1 \cdot m_2 \cdot ... \cdot m_n - 1 >\) → \(Z{_{m_1}} \times Z{_{m_2}} \times ... \times Z{_{m_n}}\). Zakres tak zdefiniowanego zapisu RNS jest oczywiście równy \(<0, m_1 \cdot m_2 \cdot ... \cdot m_n - 1 >\).

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)