数論変換
primes: [2, 3, 5] なら 532 =30 までの数を一意的に表せる
carryがないので高速に計算できる
e.g.
primes: [5, 3, 2]
9 + 16 = 25
[4, 0, 1] + [1, 1, 0] = [0, 1, 1]
7 * 4 = 28
[2, 1, 1] * [4, 1, 0] = [3, 1, 0]
中国剰余定理
primes [5, 3, 2] の時 M = 30 より
0~14を正, 15-29までを負とすることにより整数が表現できる.
(Xの補数)
e.g. 8 = [3, 2, 0],
より
8 - 9
= 8 + (-9)
= 8 + (9)^c
= [3, 2, 0] + [1, 0, 1]
= [4, 2, 1]
= 29
= -1
よってRNS上で高速に四則演算が可能