2021SC@SDUSC
2021-12-12
第十一周完成事项 工作内容本周的工作是继续完成上周的rns剩余数系统的代码分析。首先还是让我们先了解一下剩余数系统。
RNS——剩余数系统与冗余数相反，剩余数表示系统（RNS，residue number system）是一种用较少的数表示较多的数的表示系统。RNS可显著提高信号处理应用中某些算法密集型场景的算法速度。此外，RNS也是研究快速算法极限理论的一个工具。
RNS相关内容的补充上星期在介绍rns的时候没有提到剩余数系统真正的内涵：用好几个小一点的数去表示大一点的数。
这样运算的时候就可以分别计算小一点的数来加快效率了，这就是为什么使用rns来表示原本数能加快运算速度的原因。
运用RNS进行加快运算举例假如有一个数157，而我们的计算机居然只支持表示5比特的数（假如），也就是他uint类型的UINT_MAX为
2
5
−
1
=
31
2^5-1=31
25−1=31。那我们找到了这样两个互素的数17,23，那就可以将157表示为{4,19}，其中4 = 157 mod 17 , 19 = 157 mod 23。
通过中国剩余定理，我们可以来恢复一下原数，已知：
{
4
=
x
m
o
d
17
19
=
x
m
o
d
23
begin{cases} 4 = x mod 17 \ 19 = x mod 23 end{cases}
{4=xmod1719=xmod23
那么可以求x = 4 ∗ 23 ∗ 3 + 19 ∗ 17 ∗ 19 = 6413 ≡ 157 mod (17 ∗ 23 = 391)
其中19是17模23的逆元，3是23模17的逆元。
那假如我们要计算157 + 35 = 192 mod 391，以及21 = 157 ∗ 35 mod 391
那我们将35也进行RNS表达为{1,12}，
5 = 1 + 4 mod 17, 8 = 19 + 12 mod 23
4 = 1 × 4 mod 17, 21 = 19 × 12 mod 23
我们分别对{5,8}，{4,21}进行CRT恢复，神奇的事情发生啦，恢复的结果正好为192和21。
代码分析承接上周的进度，上周讲到了对RNSbase模数的更改，这周将继续分析相关代码。
void decompose(std::uint64_t *value, MemoryPoolHandle pool) const; void decompose_array(std::uint64_t *value, std::size_t count, MemoryPoolHandle pool) const; void compose(std::uint64_t *value, MemoryPoolHandle pool) const; void compose_array(std::uint64_t *value, std::size_t count, MemoryPoolHandle pool) const;
首先是数与RNS表示的转换，decompose函数是将原本的数分解为RNS表示的数，decompose_array函数是将一组数转化为RNS表示的数，compose与之相反。
这里主要讲解一下decompose和compose，对于decompose_array和compose_array来说，相当于decompose和compose的变体，与之类似，这里就不再过多陈述。
首先我们来看一下decompose函数的主要内容。
void RNSbase::decompose(uint64_t *value, MemoryPoolHandle pool) const
{
if (!value)
{
throw invalid_argument("value cannot be null");
}
if (!pool)
{
throw invalid_argument("pool is uninitialized");
}
if (size_ > 1)
{
// Copy the value
auto value_copy(allocate_uint(size_, pool));
set_uint(value, size_, value_copy.get());
SEAL_ITERATE(iter(value, base_), size_, [&](auto I) {
get<0>(I) = modulo_uint(value_copy.get(), size_, get<1>(I));
});
}
}
decompose函数首先是对传进来的数进行判断，判断value值是否为空以及判断内存池句柄是否初始化，如果没有就弹出警告。
然后判断当前RNSbase的size是否大于1，如果是则进行复制和迭代操作。
然后是compose函数的主要内容。
void RNSbase::compose(uint64_t *value, MemoryPoolHandle pool) const
{
if (!value)
{
throw invalid_argument("value cannot be null");
}
if (!pool)
{
throw invalid_argument("pool is uninitialized");
}
if (size_ > 1)
{
// Copy the value
auto temp_value(allocate_uint(size_, pool));
set_uint(value, size_, temp_value.get());
// Clear the result
set_zero_uint(size_, value);
StrideIter punctured_prod(punctured_prod_array_.get(), size_);
// Compose an array of integers (one per base element) into a single multi-precision integer
auto temp_mpi(allocate_uint(size_, pool));
SEAL_ITERATE(
iter(temp_value, inv_punctured_prod_mod_base_array_, punctured_prod, base_), size_, [&](auto I) {
uint64_t temp_prod = multiply_uint_mod(get<0>(I), get<1>(I), get<3>(I));
multiply_uint(get<2>(I), size_, temp_prod, size_, temp_mpi.get());
add_uint_uint_mod(temp_mpi.get(), value, base_prod_.get(), size_, value);
});
}
}
compose函数首先也是判断value值和pool值，然后判断RNSbase的size是否大于1。接下来的操作基本上大同小异，先根据value创建一个副本，然后根据迭代器，还原出数。
关于RNSbase最后的内容就是相关变量的获取，这里涉及到尚未分析的内容这里就不再过多的陈述。
SEAL_NODISCARD inline const Modulus *base() const noexcept
{
return base_.get();
}
SEAL_NODISCARD inline const std::uint64_t *base_prod() const noexcept
{
return base_prod_.get();
}
SEAL_NODISCARD inline const std::uint64_t *punctured_prod_array() const noexcept
{
return punctured_prod_array_.get();
}
SEAL_NODISCARD inline const MultiplyUIntModOperand *inv_punctured_prod_mod_base_array() const noexcept
{
return inv_punctured_prod_mod_base_array_.get();
}
至此关于RNSbase，也就是和剩余数系统的基本内容到这里就分析完成了。
从上周分析到现在，看到了RNSbase的构造函数、复制构造函数以及复制构造函数，看到了判断包含和子集的函数，看到了添加和删除元素的函数，也看到了合成和分解的函数，到这里，整个RNS的内容完成了三分之一，接下来下周将对里面所包含的变量内容进行分析。
总结这次首先是回顾了上星期分析的有关剩余数系统的相关内容，并沿着上星期的代码分析进度继续分析了剩余数系统的相关代码。
最后，感谢孔老师的指导，感谢戴老师和其他审核老师的阅读！
