问题标签 [modular-arithmetic]

我已经实现了一个非递归模幂运算

另一个是递归的

但是这两个代码没有产生正确的结果。来自维基百科的迭代代码给出了正确的结果。我在递归版本中做错了什么，我应该怎么做才能修复它？

设h(y)是定义为 的函数(a*y+b)mod m。所以h(y)可以取值from 0 to m-1. 现在我们得到 7 个整数 - a,b,x,n,c,d,m。我们的任务是找到这样的总计数，h(x),h(x+1),h(x+2)...h(x+n)使得 的值h(x+i)落在[c,d].where0<=i<=n 整数限制的范围内：

例如。对于输入set {1,0,0,8,0,8,9}，输出应为 9。请提出一个有效的算法。谢谢！！！

在 JavaScript 中，我有两个变量，每个变量都包含一个十六进制数字作为字符串。例如：

现在我想添加它们（所以，结果应该是'c0cb'）。为了让事情变得更容易一些，让我们对此进行一些限制：

• 这些数字总是由相同数量的数字组成（即字符串的长度相同）。
• 如有必要，数字会以 s 为前缀0，因此它将是'001a'，而不仅仅是'1a'。

另一方面，有一些限制让事情变得有点困难：

• 这些数字不像上面的例子那样由四位数字组成，而是由 20 位数字组成。因此，您不能简单地将它们转换为十进制，将它们相加，然后再将它们转换回来。换句话说：对于 JavaScript 的number类型来说，数字太大了（这就是这个答案不起作用的原因）。
• 不允许溢出。如果加上'ffff'and '0001'，结果应该是'0000', not '10000'。换句话说：所有计算都必须使用模除法。

我目前有一个算法可以解决所有这些问题，但它很长，效率不高，而且一切都很优雅。它的想法是逐个字符地遍历字符串，将它们转换为十进制，添加它们，将它们转换回来，记住潜在的溢出等等。如前所述，它工作得很好，但我认为这不是最好的解决方案。

我怎样才能以更好的方式解决这个问题？

PS：我需要在 Node.js 中执行此操作，因此如果有可用的现成模块可以执行此操作，我对此非常满意 :-)

我缺乏关于性能如何受 CPU 规格影响的知识。我正在使用以下参数在 Windows 平台上运行一个应用程序来执行模块化计算（DH 密钥交换）：

模块化：素数 = 4096 位

发电机：2

指数：256 位

当应用程序在具有 2.4 GHz 处理器和 4G RAM 的 32 位 Windows 7 上运行时，需要 3-4 秒。但是，当我在具有相同处理器速度和 8G RAM 的 64 位 Windows 7 上运行相同的应用程序时，需要 1-2 秒。

我试图理解，但我很困惑模块化计算速度是否受 ARM 大小或 CPU 支持（64 位与 32 位）的影响

现在我的服务器在这条线上运行了几天后崩溃了两次。

m_list 在哪里

崩溃是

应该保证获取列表的大小不是负数。什么可能导致此崩溃？与rand有关的东西可能是原因吗？我在我的服务器开始时播种 rand

任何提示表示赞赏！

我正在尝试解方程：

我目前的解决方案：

工作正常，直到我遇到一个问题集，其中任何 (n + k) 都没有模逆，因为

所以我的问题是，是否有另一种不涉及乘以模逆的方法来解决这个问题？例如，这些建议中的任何一个都可以解决我的问题吗？

mod的概念只保留余数而不是大数。

计算公式：

=> 求和 i=1 到 i=N { i%m }

约束

1 ≤ N ≤ 10^9 1 ≤ m ≤ 10^9

如何使用模数以便我们不需要求和到 10^9（大数）。Java 代码因超时或 CPU 代码被大量执行错误而终止。

CODE：k是要打印的求和结果。

在过去的几天里，我一直在努力帮助 Spektre 先生，由于兼容性问题，他不得不为 FFT 乘法编写自己的数论变换。
模块化算法和 NTT（有限域 DFT）优化

他有一个工作得很好，但他一直想知道是否有任何方法可以加快速度。想到的一个想法是使用蒙哥马利乘法来避免过度除法。我过去使用过它，但由于某种原因，我无法让它在这里工作，而且我不确定这是蒙哥马利乘法还是 NTT 的问题。

它使用 32 位字长，因此减少量也是 2^32，素数模数是 3221225473。欧几里得算法，我发现倒数是：
2^32 * 2415919104 = (3221225473 * 3221225471) + 1

下面是我正在处理的代码，以及调用它的 main 函数。
注意：此时我并不担心逆变换，因为如果常规变换根本不起作用，那就没有意义了。

这是主要的

我觉得这很简单，但我不知道它是什么。感谢你们提供的任何帮助！

[编辑] 因此，为了排除它，我修改了 modmul 函数，以便将其输入从蒙哥马利形式转换为常规形式，执行标准 (A * B) % p，然后将其转换回蒙哥马利形式并我仍然得到相同的错误答案。这让我认为问题在于与蒙哥马利形式的转换，但我不知道我做错了什么。

我想构建一个节省空间的模块化算术类。这个想法是模数 M 是一个在实例化期间固定的不可变属性，因此如果我们有一个具有相同 M 值的大型数组（std::vector 或其他容器），则 M 只需要存储一次。

如果 M 可以在编译时固定，这可以使用模板来完成：

但是，在我的应用程序中，我们应该能够表达 M 运行时。我所拥有的看起来像这样：

这可行，但是 mod M 值的大向量使用它需要的空间的 2 倍。

我认为潜在的概念问题是不同模数的 Mod 在语法上属于相同类型，即使它们“应该”是不同的类型。例如，像这样的语句

应该“自然”引发运行时错误（在我的版本中，它“手动”这样做：检查内置于复制构造函数以及我实现的每个二元运算符中）。

那么，有没有办法实现某种动态类型，以便 Mod 对象的类型记住模数？我真的很感激任何想法如何解决这个问题。

这对我来说是一个反复出现的问题，涉及各种数学结构（例如，在同一集合上存储许多排列、同一组的元素等）

编辑：据我所知，

• 模板是由类或文字参数化的类型。

• 我想要什么：由 const 对象参数化的类型（const num在这种情况下，const Group&或const Group *const用于组等）。

这可能吗？

在 C++ 中使用模算术（或）（%）运算符，我们可以循环遍历具有范围的连续数字。

例如：

如果范围是 5（或）模 5，那么我们可以循环遍历

0 1 2 3 4 0 (5) 1(6) 2(7) 3(8) 4(9) 0(10)............0 1 2 3 等

问题：

在类似的意义上，我们可以使用任何算术关系/C++技巧来在一定范围内向前移动增加的数字（直到上限）和反向移动（直到下限或0）的数字。

例如：

如果范围 = 5 那么

0 1 2 3 4 3 2 1 0 1 2 3 4 3 2 1 0 .....0 1 2 3 等

在下面的程序中，我使用了两种方法在给定范围内向前/向后迭代。

但我很感兴趣-有没有最好的方法（C++ 技巧/数学关系）在给定范围内迭代正向和反向？