RNS (Residue Number System)
Берем набор простых чисел a1,...,aN.
(в принципе можно просто набор взаимно простых чисел)
(для повышения эффективности удобнее брать числа вида 2^k и 2^(k-1) )
С помощью этого набора мы можен представить все числа от 0 до a1*...*aN-1
Записывая числа как набор остатков от деления по модулю a{i}
Например возмем простые числа: {2,3,5}
RNS(2|3|5)
C помощью этого набора мы сможен представить числа от 0 до
2*3*5 = 30
-------------------
0 {0,0,0}
1 {1,1,1}
2 {0,2,2}
3 {1,0,3}
4 {0,1,4}
5 {1,2,0}
6 {0,0,1}
7 {1,1,2}
8 {0,2,3}
9 {1,0,4}
10 {0,1,0}
11 {1,2,1}
12 {0,0,2}
13 {1,1,3}
14 {0,2,4}
15 {1,0,0}
16 {0,1,1}
17 {1,2,2}
18 {0,0,3}
19 {1,1,4}
20 {0,2,0}
21 {1,0,1}
22 {0,1,2}
23 {1,2,3}
24 {0,0,4}
25 {1,1,0}
26 {0,2,1}
27 {1,0,2}
28 {0,1,3}
29 {1,2,4}
-------------------
-------------------
0 {0,0,0}
6 {0,0,1}
12 {0,0,2}
18 {0,0,3}
24 {0,0,4}
10 {0,1,0}
16 {0,1,1}
22 {0,1,2}
28 {0,1,3}
4 {0,1,4}
20 {0,2,0}
26 {0,2,1}
2 {0,2,2}
8 {0,2,3}
14 {0,2,4}
15 {1,0,0}
21 {1,0,1}
27 {1,0,2}
3 {1,0,3}
9 {1,0,4}
25 {1,1,0}
1 {1,1,1}
7 {1,1,2}
13 {1,1,3}
19 {1,1,4}
5 {1,2,0}
11 {1,2,1}
17 {1,2,2}
23 {1,2,3}
29 {1,2,4}
-------------------
Самое интересное что в таком кольце операции сложения/вычитания и умножения
выполняются как операции над каждой из его частей определяемых своим простым
числом:
(таким образом сумматорам не надо тащить перенос, а все может реализовываться
в кольце маленького размера).
Например:
12+15
12 {0,0,2}
15 {1,0,0}
----------------
12+15 {1,0,2} = 27
3*7
3 {1,0,3}
7 {1,1,2}
----------------
3*7 {1,0,1} = 21
Существование обратного элемента по сложению
13 {1,1,3}
-13 {2-1,3-1,5-3} = {1,2,2}
13 {1,2,2}
+ -13 {1,1,3}
-----------------
0 {0,0,0}
Нахождение обратных элементов по умножению труднее.
Понятно что есть единица {1,1,1}
Для каждого разряда можно найти свои обратные элементы по умножению.
RSN(2|3|5)
2:
* | 0 1
---+-------
0 | 0 0
1 | 0 1
3:
* | 0 1 2
---+---------
0 | 0 0 0
1 | 0 1 2
2 | 0 2 1
5:
* | 0 1 2 3 4
---+----------------
0 | 0 0 0 0 0
1 | 0 1 2 3 4
2 | 0 2 4 1 3
3 | 0 3 1 4 2
4 | 0 4 3 2 1
Xi / Mi = Xi * (1/Mi) mod P
Пример:
28/7 = {0,1,3} / {1,1,2}
2: 0/1 = 0
3: 1/1 = 1
5: 3/2 = 4 (3*4 = 2)
{0,1,4} = 4
28/27 = {0,1,3} / {1,0,2}
2: 0/1 = 0
3: 1/0 = ? Вот она проблема с делителями нуля
5: 3/2 = 4
типа не делиться - нет такого числа
а что же вы хотели у нас же не поле, а кольцо.
Но в нашем кольце очень много делителей нуля (больше двух третей кольца):
Это числа вида:
{ *, *, 0 }
{ *, 0, * }
{ 0, *, * }
Пример:
{1,2,0}
* {0,0,2}
------------
{0,0,0}
Конвертация из обычного формата
22 -> RNS(2|3|5)
22 mod 2 = 0
22 mod 3 = 1
22 mod 5 = 2
{0,1,2} 22
Это можно упростить для бинарного случая например (да и для любого)
используя таблицы P^j mod M, где p - основание СЧ из которой переводить,
M - каждый из RNS баз.
Например для RNS(7|5|3)
----------------------------------------------------------
j 2^j (2^j)mod7 (2^j)mod5 (2^j)mod3
----------------------------------------------------------
0 1 1 1 1
1 2 2 2 2
2 4 4 4 1
3 8 1 3 2
4 16 2 1 1
5 32 4 2 2
6 64 1 4 1
7 128 2 3 2
8 256 4 1 1
9 512 1 2 2
----------------------------------------------------------
Соответсвенно:
11011 -> RSN(7|5|3):
------------------------------------------------------------
current sum current sum current sum
Xi*2^i 7 7 5 5 3 3
-----------------------------------------------------------
- 0 - 0 - 0
1*2^0 1 1 1 1 1 1
1*2^1 2 3 2 3 2 0
0*2^2 0 3 0 3 0 0
1*2^3 1 4 3 1 2 2
1*2^4 2 6 1 2 1 0
------------------------------------------------------------
Значит 11011{2} = (6,2,0){RSN(7|5|3)}
Конвертация обратно:
RNS(2|3|5)
{0,0,1} 6 multiple of 6 (2*3) which is 1 mod 5 = 6
{0,1,0} 10 multiple of 10 (2*5) which is 1 mod 3 = 10
{1,0,0} 15 multiple of 15 (3*5) which is 1 mod 2 = 15
23 {1,2,3} = 1 * {1,0,0}
+ 2 * {0,1,0}
+ 3 * {0,0,1}
= 1* 15 + 2*10 + 3*6 = 15 + 20 + 18 =
= 53 mod (2*3*5) = 53 mod 30 = 23.
так что конвертация обратно в нормальный формат делается без особых проблем.
Представление отрицательных чисел в RSN:
-X = M - X, где N - произведение всех чисел в базе RNS
Например для RNS(2|3|5)
0 {0,0,0}
-0 {2-0,3-0,5-0} = {0,0,0} специальный случай
1 {1,1,1}
-1 {2-1,3-1,5-1} = {1,2,4} 29
2 {0,2,2}
-2 {2-0,3-2,5-2} = {0,1,3} 28
итд
15 {1,0,0}
-15 {2-1,0,0} = {1,0,0} 15 типа специальный случай
-------------------
0 {0,0,0}
1 {1,1,1}
2 {0,2,2}
3 {1,0,3}
4 {0,1,4}
5 {1,2,0}
6 {0,0,1}
7 {1,1,2}
8 {0,2,3}
9 {1,0,4}
10 {0,1,0}
11 {1,2,1}
12 {0,0,2}
13 {1,1,3}
14 {0,2,4}
15 {1,0,0}
-14 {0,1,1}
-13 {1,2,2}
-12 {0,0,3}
-11 {1,1,4}
-10 {0,2,0}
-9 {1,0,1}
-8 {0,1,2}
-7 {1,2,3}
-6 {0,0,4}
-5 {1,1,0}
-4 {0,2,1}
-3 {1,0,2}
-2 {0,1,3}
-1 {1,2,4}
-------------------
Что трудно в RNS?
Узнать какое число положительное, какое отрицательное
Узнать произошло ли у нас переполнение во время операции
Сравнивать числа (трудно вычислить модуль)