问题标签 [modular-arithmetic]

-当x是二进制数时如何找到x mod 3？不允许使用转换为十进制然后使用 % 运算符。

-eg- 如果 x 为 1101，则输出应为 1，但不要将 1101 转换为 13，然后按 % 3 查找

我正在尝试用 Java 重写代码，以求解一组对浮点数进行高斯消元的线性方程，以处理以素数为模的方程。问题是它不起作用，我无法弄清楚出了什么问题。它似乎适用于小型方程组，但不适用于大型方程组，这使得调试变得困难。

我的算法取第一行，通过找到第一个元素的倒数对其进行归一化，并将行中的每个元素乘以这个倒数。然后它从其他行中减去这一行足够的次数以使它们的第一个元素为零。在下一次迭代中，它转到下一行并执行相同的过程，直到第 i 行的枢轴元素在第 i 列中。最后，它从前几行中减去每一行，以使每一列只有一个非零元素（最后一个除外）。（到目前为止，我使用双打，这不是必需的，但这应该不是问题）。这是我的代码：

这适用于小例子（mod 29）：

哪个是正确的（第一个变量 = 0，第二个 = 1.0，第三个 = 0），可以通过 WolframAlpha 检查 0*k^0 + 1*k^1 + 0*k^2 对于 k = 1..3。

对于这个例子，有 10 个变量，方程 a*k^0 + b*k^1 + c*k^2... (mod 29) for k = 1..11，我有这个矩阵：

使用我的算法，我得到了答案：

但这是错误的！（可以用 WolframAlpha 检查）。正确答案应该是 (abc ...) = (8 13 9 13 4 27 18 10 12 24 15)。

有人能看出我的错误吗？还是我误解了如何做 Gauss mod p？

我正在尝试对 Enigma 编码机进行编程。我已经设法让转子和反射器工作正常，但我正在尝试计算转子的前进。

对于任何不熟悉这个的人。Enigma Machine 由 3 个作为替换密码的转子和一个包含 13 对字符的反射器组成。为了对字符进行编码，首先由第一个转子对其进行编码，然后将由此编码的字符传递到第二个转子，然后再通过一个转子到达反射器，该反射器将这个新字符与与之配对的字符交换。然后，这个配对字符通过转子以相反的方式反向编码，直到最终得到最终编码字符。

在对单个字符进行编码之前，转子会移动。如果你有一个很长的消息，在任何东西被编码之前，第一个转子被移动一个位置，然后这个字符通过系统并被编码。然后在第二个字符被编码之前，第一个转子再次移动。转子不断移动，直到它再次到达启动位置。在第 25 个字符被编码后，第一个转子到达它开始的位置，但现在第二个转子移动了一个位置。在第二个转子再次转动之前，第一个转子再转动 26 次。当第二个转子转动 26 次时，第三个转子转动一次。这种情况一直发生，直到达到 25 25 25 ，此时它们重置回 0 0 0 并且循环再次开始。这让我想起了一个分小时的时钟，

我知道这可能可以用模算术编程，但我看不出怎么做？因此，任何帮助将不胜感激。

我需要计算两个 BigIntegers 的乘积，这些 BigIntegers 被提升为 BigIntegers 模素数。

我正在计算 - y^r * r^s (mod p)。

我正在使用的代码有效，但我不禁感到它正在执行不必要的计算，当涉及大型 BigInteger 时，这些计算非常昂贵。

理想情况下，我想要一种一次性计算 v1 的方法。这可能吗？

我想知道是否可以将二进制数据存储在一个数字中，以及如何将尽可能多的二进制数据存储在一个数字中。

例如，假设我想将以下文本存储在一个数字中：

Lorem ipsum dolor sit amet, consectetur adipiscing elit。Donec egestas nunc eget rhoncus blandit。

二进制形式是：

现在，如果我将其转换为数字，我会得到：2.15146353486 * 10^16

将其转换回二进制是问题所在，我得到00000010.

现在显然我不知道我在这里做什么，所以请理解这不是“为什么这不起作用？” 问题，我要问的是，我想做的事情是否可能，如果可以，怎么做？

由于二进制可以转换为 ASCII 或 BASE-64，反之亦然，因此转换为数字并返回也应该可以工作。毕竟，Base64 基本上是基于 64 的数字系统，而十进制数字是基于 10 的系统，而二进制是基于 2 的系统。

任何意见，将不胜感激。

我正在阅读以下有关如何使用 Intel Westmere 和 AMD Bulldozer 中引入的 PCLMULQDQ 指令有效实现 CRC32 的论文：

五、戈帕尔等人。“使用 PCLMULQDQ 指令对通用多项式进行快速 CRC 计算。” 2009. http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf

我了解算法，但我不确定的一件事是如何计算常数 $k_i$。例如，它们为 IEEE 802.3 多项式提供常量值：

• k1 = x^(4*128+64) 模 P(x) = 0x8833794C
• k4 = x^128 模 P(x) = 0xE8A45605
• mu = x^64 格 P(x) = 0x104D101DF

等等。我可以只使用这些常数，因为我只需要支持一个多项式，但我很感兴趣：他们是如何计算这些数字的？我不能只使用典型的 bignum 实现（例如 Python 提供的那个），因为算术必须发生在 GF(2) 中。

我想有效地计算 ((X+Y)!/(X!Y!))% P (P 就像 10^9+7)

这个讨论给出了一些关于在除法上分配模数的见解。我担心的是，一个数字不一定总是存在模逆。基本上，我正在寻找解决问题的代码实现。

对于乘法，它非常简单：

我也意识到许多因素可以在除法中被取消（在取模之前），但如果除数的数量增加，那么我发现很难有效地提出一个除法算法。（循环遍历 List(factors(X)+factors(Y)...) 以查看哪个除以当前的分子乘数）。

编辑：我不想使用 BigInt 解决方案。

是否有任何基于 java/python 的解决方案或任何标准算法/库来取消因素（如果逆选项不是完全证明）或解决此类问题。

我一直在尝试在 OpenCL 中设计一个快速的二进制求幂实现。我当前的实现与本书中关于 pi的实现非常相似。

有没有改进的余地？现在我的程序大部分时间都花在这个函数上。

嗨，我在代码 sprint5 问题中实现 nCr MODm 时遇到问题。问题的链接是...... https://www.hackerrank.com/contests/codesprint5/challenges/matrix-tracing。我学到的是，我可以将 mudular 算术规则应用于阶乘计算和逆阶乘计算以及计算 pow(a,b) MODm。但我不知道我错过了什么导致错误答案。这是我当前的代码。

这也是一个与数学相关的问题，但我想在 C++ 中实现它......所以，我有一个表单中的数字2^n，我必须计算它的数字总和（以 10;P 为底）。我的想法是用以下公式计算它：

对于它的所有数字：floor(n/floor(log2(10))).

第一项很容易用模幂计算，但我遇到了其他问题。由于n很大，而且我不想使用我的大整数库，pow(2,n)没有模数我无法计算。第一项的代码片段：

但第二个我不知道。我也不能floor单独使用它们，因为它会给出“0”（2/10）。有可能实现这一目标吗？（http://www.mathblog.dk/project-euler-16/更简单的解决方案。）当然，如果不能用这种方法完成，我会寻找其他方法。（例如将数字存储在字节数组中，如链接中的注释中所示）。

编辑：感谢现有的答案，但我正在寻找某种数学方法来解决它。我刚刚想出了一个想法，它可以在没有 bignum 或 digit-vectors 的情况下实现，我将测试它是否有效。

所以，我有上面的等式求和。但2^n/10^k可以写成2^n/2^(log2 10^k)which is 2^(n-k*log2 10)。然后我取它的小数部分和它的整数部分，并对整数部分进行模幂运算：2^(n-k*log2 10) = 2^(floor(n-k*log2 10)) * 2^(fract(n-k*log2 10)). 在最后一次迭代之后，我还将它与分数模 10 相乘。如果它不起作用或者我在上述想法的某个地方错了，我坚持使用向量解决方案并接受答案。

编辑：好的，似乎不可能用非整数模进行模幂运算（？）（或者我还没有找到任何关于它的东西）。所以，我正在做基于数字/矢量的解决方案。

代码不能完全工作！

它没有给出好的价值：（1390而不是1366）：