factorization - 关于两个数之间关系的问题

Question

当一个可被另一个整除时，数字的位之间是否存在任何关系？36位与9位或4位或12位，或10（1010）与5（101），或21（10101）与7（00111）的位序列之间有什么关系？

谢谢。如果某些句子不正确，我很抱歉，但我希望你明白我想要什么。

score 4 · Accepted Answer

我知道这不是您要问的，但它可能会有所帮助。有许多技巧可以通过操作位来建立二进制数的可除性。例如，如果一个二进制数的偶数位之和减去其奇数位之和所有模数 3 为零，则二进制数可被 3 整除。这是一个讨论二元可分性的链接。

score 3 · Accepted Answer

让我们以36为例。

36 = 0010 0100

36是4 * 9，即

 4 = 0100
 9 = 1001

如果你将它们相乘（就像你在正常的乘法中一样）你会得到

    0100 x
    1001
 --------
    0100
   0000
  0000
 0100
 -------
 0100100

所以本质上0100 x 1001 = 0010 0100（当然，您可以对任何其他除数重复相同的操作）

现在，是否有任何特殊关系可以让您仅通过查看它的位来获得 36 的所有除数？唉，答案是否定的：）

编辑：至少没有已知的关系，但是，谁知道呢，将来也许一些聪明的数学家会找到一个。时至今日，答案仍然是否定的。

score 1 · Accepted Answer

因此，您想知道是否可以仅通过查看位来“快速”进行整数分解？

祝你好运！

score 0 · Accepted Answer

最容易看到的是最低有效数字中连续 0 的数量表示 2 的最大幂，它是您的数字 n 的一个因数。正如 DonnyD 指出的那样，显然还有其他测试（我不知道那个），但我预计它们的规模不会很好。如果他们这样做了，通常实施的公钥密码学将很快成为过去。

这并不是说这样的方法不能被发现/发明。例如，已经证明使用量子方法可以轻松分解任意大的数字，但实际上没有人能够实现一个工作系统。

底线是我们已经将我们的在线金融系统和国家安全机构委托给基于 PKI 的方法，主要是因为我们假设对于任意大的数字很难分解数字。但正如白痴在他的回答中似乎暗示的那样，欢迎你试一试。

score 0 · Accepted Answer

显然，这a是一个b可以识别的倍数，给定和的二进制表示a（b这是硬件在执行以下代码时所做的事情

boolean isMultiple = a % b == 0;

)，因此存在这样的关系。

提出更具体的问题以获得更具体的答复......

5 回答 5