【HR】哥德尔编码计算

无名

可以将非负整数序列（向量）与自然数建立起对应关系

具体来说，就是无穷序列(a1,x2,...,xm)(a1,x2,...,xm)借助素数序列(p1,p2,...,pm)(p1,p2,...,pm)，建立对应关系：

[a1,x2,...,xm][a1,x2,...,xm]称作有穷序列(a1,x2,...,xm)(a1,x2,...,xm)的哥德尔数。

原理#
根据算数基本定理，任何自然数可以唯一分解为多个素数的乘积，而构成哥德尔数的素数序列(p1,p2,...,pm)(p1,p2,...,pm)是已知的，因此，由[a1,x2,...,xm][a1,x2,...,xm]可以很容易得到序列(a1,x2,...,xm)(a1,x2,...,xm)。

同态加密算法#
该方案只用到了加法或者乘法同态性，下面分别介绍两种同态加密算法：

ElGamal#
具有乘法同态性，相比于RSA，能抵抗重放攻击（加密时加入了随机数）
1、加密结构：

2、乘法计算：


Paillier#
具有加法同态性和一次"乘法"同态性，主要用到的还是加法同态