问题标签 [modular-arithmetic]

Javascript 将以下代码段评估为 -1。

我知道余数定理表明 a = bq + r 使得 0 ≤ r < b。鉴于上述定义，答案不应该是 3 吗？为什么 JavaScript 返回 -1？

在我的项目中，存在一部分问题。但为了简化起见，这里的问题正在制定。有两个正互质整数：a和b，其中a < b。a列出从 1 到的倍数，b-1然后是模运算b。

a mod b, 2*a mod b, 3*a mod b, ... ,(b-1)*a mod b

现在，还有另一个整数，比如说n ( 1 <= n < b)。通过n列表中的第一个数字，我们必须找到小于多少个数字，比如m( 1 <= m < b)。这可以通过蛮力方法完成，从而给出 O(n).

一个例子：

a=6, b=13, n=8, m=6

清单是：

6, 12, 5, 11, 4, 10, 3, 9, 2, 8, 1, 7

这是从 1 到 12 的数字的排列，因为如果我们包含另一个数字，任何两个互质数的模运算都会产生数字的排列，即0。如果我们采用a= 2, b=13，那么列表将是2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11，它给出了一个模式。而如果a和b非常大（在我的项目中它们可以达到 10^20），那么我不知道如何推断出如此大的数字的模式。

现在回到这个例子，我们n = 8从列表中取出第一个数字，这给出了

6, 12, 5, 11, 4, 10, 3, 9

将less-than运算符与应用m = 6，它给出的数字总数小于m如下面的列表中所述

0, 0, 1, 0, 1, 0, 1, 0

其中 0 表示不小于m1 表示小于m。

既然，上面的算法是 a O(n)，在 的范围内是不可接受的[0, 10^20]，那么社区可以给一个提示/线索/提示，让我找到一个O(log n )解决方案，甚至更好的O(1)解决方案吗？

如何计算 (a/b) % m 其中 a = x1*x2*.. 并且数字 x1、x2、.. 非常大。

如果我们只需要找到一个 % m ，我们可以很容易地使用 (x1%m) * (x2%m) *...关于计算它？

我在某处读到此操作为 (a % (m*b)) / b 。我一直想知道这是不是真的，我们如何去证明它？

我有兴趣了解使用多个处理器将大整数模（大）常数相乘的时间复杂度。这归结为基本上只是整数乘法，因为除法和余数也可以使用乘法来实现（例如倒数乘法或巴雷特归约）。

我知道目前已知的整数乘法算法的运行时间大致以下限为界o(n * log n)。我的研究未能确定这是针对单核机器还是多核机器。但是，我认为这是针对单核机器的，因为算法似乎使用了分而治之的方法。

m现在我的问题是，目前已知的在内核上实现的并行整数乘法算法的时间复杂度下限是多少？o(n)给定足够多的内核，是否可以实现具有下限或更少的时间复杂度？（即是否m取决于n？）这里o(n)描述了手头整数的输入大小。

到目前为止，在我的研究中，我已经阅读了几篇声称使用并行 FFT 乘法可以提高速度的论文。不幸的是，这些仅声称经验加速（例如“在某某计算机上使用 6 个内核的速度提高了 56%”），然后无法解释以时间复杂度界限表示的理论加速。

我知道尚未找到“最快”的整数乘法算法，这是计算机科学中一个未解决的问题。我只是在询问目前已知的这种并行算法的界限。

更新 #1：用户@delnan 链接到关于NC 复杂性类的 wiki 页面。该维基页面提到整数乘法在NC中，这意味着处理器上存在O((log n)^c)算法。O(n^k)这有助于更接近答案。现在没有回答的部分是整数乘法的c和k常量是什么，哪种并行算法适合这个目的？

更新 #2：根据康奈尔大学计算机科学课程的PDF 文件中的第 12 页（共 15 页），NC 复杂性课程中的整数乘法需要处理器O(log n)上的时间。O(n^2)它还解释了一个关于如何进行此操作的示例算法。我很快就会为这个问题写一个正确的答案。

最后一个问题来满足我的好奇心：有没有人知道“just”或处理器的当前已知时间O(n)复杂O(sqrt(n))度O(log n)？

我理解模运算的基本数学形式，例如：

但是在下面的加密和解密代码示例中，它与其他数学一起使用，我不明白它的用途。

有人可以向我解释一下吗？

我正在研究这个看似简单的问题，我需要在数字的每个数字上加一个。示例：数字 = 1234；输出 = 2345

这很简单，但是当 9 是其中一个数字时，根据加法定律，9 将被 0 替换，并且 1 将添加到左边的数字（9 + 1 = 10，因此，位置值 = 0 & 结转 = 1) 示例：数字 = 1239 ; 输出 = 2350

有人可以向我解释一下，我应该使用什么逻辑？我可以在模数运算中看到一些东西，但不确定如何实现它。谢谢 ：）

以下是否有可能的模块化表达式：

例如：

我想知道如何找到浮点数的反对数。我的第一种方法是在 Python 和 C 中使用 exp()、pow() 等内置函数，但它们给出了超出范围的错误。

然后我尝试将它分成两部分，一个整数和另一个浮点数，然后分别计算它们的 10 次幂，然后将它们相乘以获得结果。所以当我尝试在 Python 中计算 (a*b) 它说long int too large to convert to float

我最初的任务是计算 antilog(x)%m & 我将它转换为 (a*b)%m 其中 a 是非常非常大的整数 & b 是浮点数。

那么有人可以帮我解决这个问题吗？是否有任何适用于浮动的模块化属性？或者是否有任何“快速”和“高效”的方法来计算 antilog(x)？

我正在尝试采用 ed = 1 mod((p-1)(q-1)) 并求解 d，就像 RSA 算法一样。

e = 5, (p-1)*(q-1) = 249996

我在javascript中尝试了很多代码，例如：

或者

我只是想不出在 javascript 中求解模逆 d 的正确方法。

I want to ask Maple, for example, for which j the following is true:

10^j mod 543 = 82

How can I ask Maple this?

Also, is there a way to solve for j without a computer?