想要做两个大数的乘法，但是这两个数不能输入计算机，怎么做到？

[fbxshit]

为了安全性，这两个数不能存到内存中，也不能保存到 cpu 寄存器中。

对于两数 a 和 b 加法，我能想到的是，取一个随机数 c，把 a 加 c 的结果输入计算机，然后把 b 减 c 的结果输入计算机。

那么对于 a 乘 b,如何做到让计算机得出答案，但是没有办法推测出 a 和 b?

[ylrshui]

ab=((a+b)^2-(a-b)^2)/4
a+b、a-b 已经有方法了

[jie170601]

@ylrshui 输入 a+b,a-b 的结果时还是能推算出 a 和 b 的值

[akira]

a b 分别做二进制展开，然后分别做多项式加法 乘法运算

[skadi]

同态加密.我记得密码学上讲过.

[morethansean]

@TomVista 都不对，你应该好好学习，这样你既不会计组挂科，还能看懂这个帖子到底要讨论啥。

[geelaw]

这个问题只有 a、b 来自两个人的时候才有意义，否则你可以自己计算。（对于一个人自己想要委托别人进行计算的情况，恐怕同态加密并不划算，因为同态加密、解密本身的时间已经远远超过两个数相乘。）

假设两个数的乘积不超过 p （不需要是质数），把所有的运算搬运到 mod p 里面进行，为了计算 ab，先计算 u=a+r, v=b+s, x=-sa+t, y=-rb-t-rs，其中 rst 是随机数，那么 ab=uv+x+y。

给定 ab （乘积），uvx 是三个独立随机数，而 y 是惟一满足方程 uv+x+y=ab 的数，所以这几个数只透露了 ab。

这个方法就是信息论安全的乱码电路，见于论文 How to Garble Arithmetic Circuits。

[linhua]

KaraTsuba 乘法

[ldm0]

一个完美解法：
找到两个随机数 x,y，满足 x*y - 1 > a * b
向计算方提供 x * a, y * b, x * y - 1，
然后计算函数就是 a * b = ((x * a) * (y * b)) mod (x * y - 1)
研究了很久希望能对楼主有帮助

[fbxshit]

@ldm0 如果需要提供 x*y-1，还不如自己本地计算 a*b 了。

如果用随机数做安全处理后再把计算任务交给远程计算机做，前提是这个预处理
消耗的资源要小于本身要计算的任务，否则还不如我自己算 a*b。

[ldm0]

@fbxshit
首先，我觉得可以查表来分解计算压力，首先在本地预先构建一个足够大的 x, y, x*y - 1 表，发布的时候查一下，而且 x 和 y 的值不一定要很复杂，找一些好计算的数值就可以，方便计算 x * a 和 y * b。
第二，其实那个 x * y - 1 是一个 workaround。我第一眼想到的解法是给 a + p 和 b + p （其中 p > a * b)，然后计算机计算相乘，结果返回之后自己模 p。这整个流程就不需要相乘，只是结果不是到手就能用的。

[b00tyhunt3r]

分布式就是干这个的啊