Residue number system

Residue number system

Congrunces

A=a mod bで定義される関係のこと。
Aは a modulo bの関係にあると読む。
これは次のようにも書ける。
A=a+bt

A:number
a:residue
b:base or modulus

tが最大のときleast positiveであるという

congruncesの性質

(A1+A2)=(a1+a2) mod b

(A1*A2)=(a1*a2) mod b

Residue Code

Number を　mod n1,n2,...(least positive)の羅列で表す。

例:
Number Mod 2 Mod 6
0 0 0
1 1 1
2 0 2
3 1 3
4 0 4
5 1 5

bには素数を選ぶと良い

• >素数を選んだほうが表現できる数の幅が広がる