问题标签 [modular-arithmetic]

根据费马小定理，a^(p-1) mod(p) 为 1。因此，a^k(p-1) mod(p) 通过拆分为 k 个部分并独立应用模数也将为 1，我们得到“1” . 我错过了什么吗？

我想计算一个^m mod n，其中n是一个素数，而m非常大。我想用二进制幂计算来做这个，我想找到这样的x，a ^x = a (mod n)然后计算a ^{(m mod x)} mod n。

显然，任何a都存在这样的x，因为在某些时候为 mod n 循环提供了动力，但我没有找到如何用模运算来计算它。我想知道我是否遗漏了什么，或者是否存在一些数值方法？

我正在尝试构建一个可以解决模块化同余的 C++ 程序：

n^p = x (mod q ),

其中 n 是一个小数，p 和 q 是非常大的任意素数。我曾多次尝试这样做，但我总是遇到内存溢出问题。任何帮助表示赞赏。

我在一次采访中被问到以下问题：

如何解决这个问题：((3000000!)/(30!)^100000)%(任何素数。)

我使用蛮力编写了相同的 C 程序，但我确信他没有预料到这一点。对解决方案有什么建议吗？

我正在尝试找到解决方案的数量

其中 b<=50 但 a 和 u 可以很大。我的方法是从 0 到 min(b,u) 遍历 x 的每个值，如果它满足等式添加 ceil((ux)/b) （以说明 x 的值的数量大于 b但在 b) 的乘法域中等价于解的数量。我不确定我的算法的正确性。我可以将我的方法扩展到多个变量，例如是否存在

我可以生成所有无序的 x 和 y 对，使得 x<=y 直到 (x,y)<=min(b,u) 并再次计算 i=ceil((ux)/b) 和 j=ceil((uy )/b) 并将总和相乘为：

并对 t 求和。我想知道我的算法是否正确以及是否有其他更有效的算法。

我需要找到 的值a mod m。但我没有a直接的价值。我有以下模数值a。
a mod 2 ¹
a mod 2 ²
a mod 2 ³
...
a mod 2 ⁿ

现在我需要找到a mod m可以 在 O(n) 时间内完成的地方吗？m < 2n

我有一个数组 Array = {}，数组的大小是 n

我的约束是这样的：

n <= 100000 和数组_i <=100

我必须找到数组中所有元素的乘积，我将得到一个 mod 值，我必须用它来修改乘积。mod 的值会一直变化，并且这个 mod 的值总是小于或等于 n。

我的问题是当我选择时，全局 mod 值说 R = 1000000000（远大于 mod 约束）并且每当我的产品超过这个值时，我都会修改结果。

但我不知道为什么我得到的结果是零。

我的问题是在这种情况下如何选择 R？

我编写了用于在数组上触发产品范围查询的代码。

注意：这个问题与Multiplication in a range不重复。我的问题是不同的

我为此编写了代码，

我很确定我选择的 R 没有通过一些测试用例。^{我也用 10 18}尝试了R。但仍然是同样的问题。不知道为什么会这样？

我的问题是，是 RI 选择的问题，还是每个测试用例中通过的不同 M 的问题。

注意：真的不期待解决方案，只是期待线索

问候

A 是一个最多包含 10 ^{5 个}整数的数组。

我们必须以 log(N) 复杂度对这个数组进行 2 种操作（其中，N= A中的元素数）。

操作 1，给定v，i，j我们必须将v添加到A[k] (i<=k<=j)。

操作 2，给定i & j计算( A[i] * A[i+1] * A[i+2] * .... * A[j] ) % M。（M 是一个素数，并且对于所有操作都是相同的）。

将进行近 10 ⁵次操作。

如果在 log(N) 中不可能，那么执行操作的最佳复杂度是多少？

我想使用 NTT 进行快速平方计算（请参阅 Fast bignum square calculation），但即使对于非常大的数字，结果也很慢......超过 12000 位。

所以我的问题是：

1. 有没有办法优化我的 NTT 转换？我并不是要通过并行（线程）来加速它；这只是低级层。
2. 有没有办法加快我的模运算？

这是我在 C++ 中为 NTT 编写的（已经优化的）源代码（它是完整的，并且 100% 在 C++ 中工作，不需要第三方库，也应该是线程安全的。当心源数组被用作临时的！！！ , 它也不能将数组转换为自身）。

我的 NTT 类的使用示例：

优化前的一些测量（非 NTT 类）：

我优化后的一些测量（当前代码、更低的递归参数大小/计数和更好的模块化算法）：

检查 NTT mul 和 NTT sqr 时间（我的优化将其加快了 3 倍多一点）。它只有 1 倍循环，所以它不是很精确（误差 ~ 10%），但即使现在加速也很明显（通常我循环它 1000 倍甚至更多，但我的 NTT 太慢了）。

您可以自由使用我的代码...只需将我的昵称和/或指向此页面的链接保留在某处（代码中的 rem、readme.txt、about 或其他）。我希望它有所帮助......（我在任何地方都没有看到快速 NTT 的 C++ 源代码，所以我不得不自己编写）。对所有接受的 N 进行了统一根测试，请参见fourier_NTT::init(DWORD n)函数。

PS：有关 NTT 的更多信息，请参阅Translation from Complex-FFT to Finite-Field-FFT。此代码基于我在该链接中的帖子。

[edit1:] 代码中的进一步更改

通过利用模素数始终为 0xC0000001 并消除不必要的调用，我设法进一步优化了我的模运算。现在产生的加速效果令人惊叹（超过 40 倍），并且在大约 1500 * 32 位阈值之后，NTT 乘法比 karatsuba 更快。顺便说一句，我的 NTT 的速度现在与我在 64 位双精度上优化的 DFFT 相同。

一些测量：

模运算的新源代码：

如您所见，函数shl并shr不再使用。我认为 modpow 可以进一步优化，但它不是一个关键函数，因为它只被调用很少。最关键的功能是 modmul，它似乎处于最佳状态。

进一步的问题：

• 有没有其他加速 NTT 的选项？
• 我对模运算的优化是否安全？（结果似乎是一样的，但我可能会错过一些东西。）

[edit2] 新的优化

我从您的所有评论中实现了所有可用的东西（感谢您的洞察力）。

加速：

• +2.5% 移除不必要的安全模组（Mandalf The Beige）
• +34.9% 使用预先计算的 W,iW 力量（神秘）
• +35% 总计

实际完整源代码：

NTT_fast通过分离为两个函数，仍然有可能使用更少的堆垃圾。一个 withWW[]和另一个 with iWW[]which 导致递归调用中的一个参数减少。但我对它的期望并不高（仅限 32 位指针），而是有一个功能可以在将来更好地管理代码。许多功能现在处于休眠状态（用于测试），例如慢速变体mod和较旧的快速功能（使用w参数而不是*w2,i2）。

为避免大数据集溢出，请将输入数字限制为p/4位。每个NTT元素p的位数在哪里，因此对于这个 32 位版本，使用最大输入值。(32 bit/4 -> 8 bit)

[edit3]bigint用于测试的简单字符串乘法

我使用AnsiString's，所以我char*希望将它移植到，我没有做错什么。看起来它工作正常（与AnsiString版本相比）。

• sx,sy是十进制整数
• 返回分配的字符串(char*)=sx*sy

每个 32 位数据字只有约 4 位，因此没有溢出风险，但它当然更慢。在我的bignum库中，我使用二进制表示并为NTT8 bit使用每个 32 位 WORD 的块。如果大的话，更多的是有风险的......N

玩得开心