我试图器件的算法，可以告诉一些是由 [英] I am trying to device an algorithm which can tell what a number is made of

问题描述

我加入两个位对应的位蒸Java中象下面这样：

  0 1 1 1 0 0
1 0 1 0 1 0
====================
2 0 2 1 1 0
 

在此我加入结果为：

  2 + 0 + 2 + 1 + 1 + 0 = 6
 

现在，我必须找出1ns的和2S的数量在结果（6），该位匹配和非匹配位。我用力装置这样的算法，可以告诉我为1ns的准确数量和2S的结果是由但我不能创造任何至今。 它允许每次加入的乘法用恒定数量的结果。各个位可以被减去，以达到上述目标。

进一步的细节： 我使用的Pascal Paillier同态算法将这些单个位加密。帕斯卡尔Paillier支持除了只对加密的数据，所以我必须只添加。我要这个号码发送的一些应用程序，它必须找出1ns的确切数量和2S结果正在由

更新： 我还可以乘这些单个位像我加入以上。但我不能添加这些位没有结果。位可乘以自身或任何其他位。甚至我可以重新present这些位与我选择的号码。这就是我可以说，1 = 2和0 = 3，那么我就可以有：

有关加（帕斯卡Paillier）：

  2 3 2 2 3 3
2 3 2 3 2 3
====================
4 6 4 5 5 9
 

有关乘法（RSA）

  2 3 2 2 3 3
2 3 2 3 2 3
====================
4 9 4 6 6 9
 

<强>的唯一目的是要找出相似的比特数（1和1）和非类似比特（0安培; 1，1和0），从总数将生成或者通过加入（帕斯卡Paillier）或乘（RSA）。 此外，第二比特流可以被重新psented用不同的数字比上面的$ P $。

以下也可以使用：

1. 乘以位，结果和指数具有恒定
2. 在加法/减法间位和结果，并乘以一个唯一不变的

解决方案

我希望我正确地理解你的问题：如果你想找出多少1ns的和2S一个数x由，没有独特的解决方案。 想象一下，数 100 。现在告诉我很多三三两两如何在那里。 100 1和0三三两两？ 0 1和50三三两两？或者，也许80 1和10三三两两？

另一个例子：你给出一个数 X 和是，而 X 是一个除数和是是一个从余数。

让我们设置 X 3和是 2。现在找到的红利。再次，这是不可能的，因为11/3叶2，也：14/3;三分之十七; 20/3等等..

有两种可能你可以做什么：

• 不知怎么抢号，他们得到sum'ed之前
• 或者，如果有用的话，你的情况，计算1ns的和2S其总结为你的目标号码的所有组合。 但是：如果您尝试这样做，你可能会面对的子集和问题这是 NP完全。

I am adding corresponding bits of two bit steams in Java like below:

1 0 1 1 0 0
1 0 1 0 1 0
====================
2 0 2 1 1 0

After this I am adding result as:

2+0+2+1+1+0 = 6

Now, I have to find out number of 1ns and 2s in the result (6) that is matched bits and non-matched bits. I tried hard to device such an algorithm which can tell me exact number of 1ns and 2s the result is made up of but I am unable to create any so far. It allows multiplying of each addition result with a constant number. Individual bits can be subtracted to achieve above goal.

Further detail: I am using Pascal Paillier Homomorphic algorithm to encrypt these individual bits. Pascal Paillier supports addition only over encrypted data so I have to add only. I have to send this number to some application which have to find out the exact number of 1ns and 2s result is being made up of.

Update: I can also multiply these individual bits like I am adding above. But I cannot add these bits neither the result. Bits can be multiplied with itself or any other bit. Even I can represent these bits with number of my choice. That is I can say that 1=2 and 0=3 then I can have:

For addition (Pascal Paillier):

2 3 2 2 3 3
2 3 2 3 2 3
====================
4 6 4 5 5 9

For Multiplication (RSA)

2 3 2 2 3 3
2 3 2 3 2 3
====================
4 9 4 6 6 9

The only purpose is to find out the number of similar bits (1&1) and non similar bits (0&1, 1&0) from the overall number will be generated either by addition (Pascal Paillier) or by multiplication (RSA). Furthermore, 2nd bit-stream can be represented with different numbers than the above.

Following can also be used:

1. Multiplication with bits and results and exponential with a constant
2. Addition/Subtraction among bits and result and multiplication with a constant only

解决方案

I hope that I understood your question correctly: if you want to find out how much 1ns and 2s a number x is made of, there is no unique solution. Imagine the number 100. Now tell me how many ones and twos are in there. 100 ones and 0 twos? 0 ones and 50 twos? Or maybe 80 ones and 10 twos?

Another example: Your are given a number x and y whereas x is a divisor and y is a remainder from a division.

Let's set x to 3 and y to 2. Now find the dividend. Again, it is not possible because 11 / 3 leaves 2, but also : 14 / 3; 17 / 3; 20 / 3 and so on..

There are two possibilities what you can do:

• Somehow grab the numbers before they get sum'ed up
• Or, if useful in your case, calculate all combinations of 1ns and 2s which sum up to your target number. But: If you try to do this you will probably face the subset sum problem which is NP-Complete.

这篇关于我试图器件的算法，可以告诉一些是由的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！