问题标签 [modular-arithmetic]

我遇到了一个 C 代码片段，它使用按位逻辑执行漂亮的模数运算：

c 的值是 b 大于 a+b 的最小倍数（根据 John Bollinger 的回答进行了编辑）。我试图向自己解释这是如何工作的（我对模算术和 & 操作之间的关系有一个模糊的理解），但缺乏洞察力。另一方面，看起来我可以将其表达为

这个表达很容易理解。此外，模块化的外观和？操作表明各个部分可以表示为按位逻辑，并以某种方式简化为顶部的表达式。但是怎么做？如果有人想试一试，我会把它留作练习（这不是家庭作业）。实现不需要在 C 中，如果有一个在线参考解释了这一点，欢迎您提供它，但不会是一个完整的答案。我想以清晰的步骤看到从底部到顶部表达式的过渡......

评论 此链接表明当 b 是 2 的幂时这可能适用。此其他链接解释了按位 & 不分布在加法上。

假设在表达式...&(-b)中 ，(-b)可以替换为(nums(int)-b)，其中nums(int)是表示中可能的整数的总数。

随意指定您最喜欢的编译器/C 版本。

示例代码：

样本输出：

问题- 使用 Intel86 模拟器，给定三个单字节数字 X、Y 和 Z (1<X,Y,Z<100)，编写计算模幂 X^y mod Z 的代码（示例，X=4，Y=3，Z=5 结果 = 4） . X、Y 和 Z 位于程序的内存位置 107H、108H 和 109H，因此请确保不要将这些字节用于指令。计算结果必须存储在 DL 中。用于计算模幂 X^y mod Z 的算法代码为：d,1。假设 Y 由位表示 Yk,Yk-1,Yk-2,...Y0 For j <-- k 到零 d <-- (d d) % Z IF Y1 == 1 then d <-- (d X) % Z 结果在 d 中。

如果我知道 parameter a，k那么p如何在 C# 中计算它？

它用于加密目的，我是新手。如果问题不恰当，请不要感到被冒犯。

请注意，它k^-1是模逆运算符，k (mod p)而不是幂运算符。

假设我已经知道 java BigIntegers c、e 和 n，有没有办法快速计算 BigInteger m，其中：

我正在寻找范围：pow(2,i)除了 MOD =1000000007i0<=i<=100000.i

因为i=100000功率值不会大于 MOD 吗？

如何正确储存电源？

手术对我来说似乎不可行。i=70我猜我得到了最大的正确值。

我必须找到 sum+= ar[i]*power(2,i) 最后打印 sum%1000000007 其中 ar[i] 是一个附加数组，其中一些大数字高达 10^5

我现在正在学习 C 基础知识。我有一个让我有点困惑的问题。
我的问题是以下程序的输出如何 - 2 ？

以下问题，当必须编写快速代码时：我有一个包含 2 个整数 a_i 和 b_i 的列表，我必须计算等式：y = (a_i * x + b_i)，其中我只对 y 感兴趣，而不对X。所有 a_i 都是素数并且彼此不同。a_i = y / x，b_i = y % x。

y 有多个解，即使所有 a_i、b_i 对的 y 必须相同，因为 x 可以是任何整数。因此我们有一个上限 k 并且 y <= k。我想要尽可能高的 y（如果有解决方案）。最大值（y）。

简而言之：我想知道最大整数 y（如果存在的话），其中 y <= k 和给出的等式。x >= 1。

我已经有了一个理论上可行的“解决方案”，但这太慢了：

解释：minK 是 max(a_i + b_i)，因为我认为 y = a_i *1 + b_i 是一个方程的最小可能解，并且由于所有方程的 y 都是相同的，所以最大值是最好的下限。

stepSize 不是 1（为了使程序更快），而是 max(a_i)，正如我所想，max(a_i) 必须适合 y 和 y = a_i * x + b_i，因此 x 是整数值，stepSize 是 a_i，而 max(a_i) 是最好的，因为这样会减少循环运行的次数。

我现在用 stepSize 尝试从 k 到 minK 的所有 y，并测试所有对 a_i 和 b_i，如果它们满足方程。如果其中一个失败，我必须继续，直到找到解决方案或没有解决方案（-1）。

不幸的是，该算法太慢了（因为 a_i 和 b_i 可以达到 10^12），我想不出更多的优化。我已经在互联网上搜索了数论和算术，但找不到任何类似的东西。

你能帮我加快这段代码的速度，或者提示我到一些处理这个问题的网站吗？

我正在尝试实现一个以梅森素数 (2 ³¹ -1) 作为模数的随机数生成器。以下工作代码基于几个相关帖子：

1. 如何在 C 中提取 32 位无符号整数的特定“n”位？
2. 以素数为模的快速乘法和减法
3. 快速乘法模 2^16 + 1

然而，

它不适用于uint32_t hi, lo;，这意味着我不了解问题的有符号与无符号方面。

基于上面的＃2，我期待答案是（hi + lo）。这意味着，我不明白为什么需要以下语句。

• 有人可以澄清我的困惑的根源吗？

• 代码本身可以改进吗？

• 生成器应该避免 0 或 2 ³¹ -1 作为种子吗？

• ^{素数（2 p} -k）的代码将如何变化？

原始代码

对于我的项目，我需要在给定矩阵 Y 和 K 的情况下求解矩阵 X。 (XY=K) 每个矩阵的元素必须是模数为随机 256 位素数的整数。我第一次尝试解决这个问题时使用了 SymPy 的mod_inv(n)函数。这样做的问题是我的内存不足，矩阵大小约为 30。我的下一个想法是执行矩阵分解，因为这可能会减少内存的负担。但是，SymPy 似乎不包含可以找到模数矩阵的求解器。我可以使用任何解决方法或自制代码吗？

我对python相当陌生，我试图用它来制作一个程序来找出Stern-Brocot序列的第n项（你可以查一下，这就是我的函数被称为SBSeq的原因）。由于某种原因，它不起作用，并且会出现错误，如下所示：

最终到了这个：

这是原始代码。

任何帮助，将不胜感激！