TFHE中的数据结构Torus
点个关注吧！！
一、理论概念
Torus是一个
[
0
,
1
)
[0,1)
[0,1)的集合（数模1运算）。取值范围通常有符号实数：
[
−
1
/
2
,
0
)
∪
[
0
,
1
/
2
)
[-1/2,0)\cup [0,1/2)
[−1/2,0)∪[0,1/2)
本文用T表示Torus。
T满足加法交换群（阿贝尔群），乘法定义了外积（T中元素和整数群中元素做乘法）但未定义内积（T中元素做乘法）。因此T不是一个环。
如果T是一个环，那么满足 ( a + b ) × c = a c + b c (a+b)\times c=ac+bc (a+b)×c=ac+bc
反例：$a=2/5，b=4/5，c=1/3. $
( a + b ) × c = 1 / 5 × 1 / 3 = 1 / 15 (a+b)\times c=1/5\times 1/3=1/15 (a+b)×c=1/5×1/3=1/15,
a c + b c = 2 / 15 + 4 / 15 = 6 / 15 ac+bc=2/15+4/15=6/15 ac+bc=2/15+4/15=6/15
外积： k ∈ Z k\in \mathbb{Z} k∈Z, t ∈ T t\in T t∈T,定义 k ⋅ t = t + t + , . . . , + t k\cdot t=t+t+,...,+t k⋅t=t+t+,...,+t
离散Torus
对于元素
t
∈
T
t\in T
t∈T和基值
B
B
B，可以将
t
t
t表示为
t
=
∑
1
∞
t
j
B
−
j
t=\sum_{1}^{\infty} t_jB^{-j}
t=∑1∞tjB−j。
举例：
B = 10 , A = 2 = 0.4142..... = 4 ⋅ 1 0 − 1 + 1 ⋅ 1 0 − 2 + 4 ⋅ 1 0 − 3 + 2 ⋅ 1 0 − 4 + . . . . B=10,A=\sqrt{2}=0.4142.....=4\cdot10^{-1}+1\cdot10^{-2}+4\cdot10^{-3}+2\cdot10^{-4}+.... B=10,A=2=0.4142.....=4⋅10−1+1⋅10−2+4⋅10−3+2⋅10−4+....
当我们值保留3位小数位数时
B = 10 , A = 2 = 0.4142..... = 4 ⋅ 1 0 − 1 + 1 ⋅ 1 0 − 2 + 4 ⋅ 1 0 − 3 B=10,A=\sqrt{2}=0.4142.....=4\cdot10^{-1}+1\cdot10^{-2}+4\cdot10^{-3} B=10,A=2=0.4142.....=4⋅10−1+1⋅10−2+4⋅10−3
3称为比特精度。
代码实现时， B = 2 B=2 B=2,比特精度取64或32。 t j ∈ { 0 , 1 } t_j\in \{0,1\} tj∈{0,1}。具体见一下篇文章代码介绍。
下面定义新的结构
T
q
=
1
q
Z
/
Z
T_q=\frac{1}{q}\mathbb{Z}/\mathbb{Z}
Tq=q1Z/Z \sqsubset T：$
\phi$是比特精度
{
i
q
(
m
o
d
1
)
∣
i
∈
Z
}
=
{
0
,
1
q
,
.
.
.
,
q
−
1
q
}
,
q
=
2
ϕ
\{\frac{i}{q}(mod~1)|i\in \mathbb{Z}\}=\{0,\frac{1}{q},...,\frac{q-1}{q}\},q=2^{\phi}
{qi(mod 1)∣i∈Z}={0,q1,...,qq−1},q=2ϕ
T
q
⊏
T
T_q \sqsubset T
Tq⊏T称为离散Torus
离散Torus实际使用结构
给定两个元素 t = a q , u = b q ∈ T q t=\frac{a}{q},u=\frac{b}{q}\in T_q t=qa,u=qb∈Tq.如果 v = t + c = c q ∈ T q v=t+c=\frac{c}{q}\in T_q v=t+c=qc∈Tq，那么有 c = a + b ( m o d q ) c=a+b(mod~q) c=a+b(mod q).同样的对于 k ∈ Z k\in\mathbb{Z} k∈Z, k t = d q ∈ T q kt=\frac{d}{q}\in T_q kt=qd∈Tq，那么有 d = k a ( m o d q ) d=ka(mod~q) d=ka(mod q)。
T q T_q Tq上的运算被转换为模 q q q运算！
原文地址：https://blog.csdn.net/qq_41359358/article/details/140607851
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！