问题标签 [modular-arithmetic]

我想用几个素数修改一个大约 1.7x10^46 的数字。事情看起来不对，所以我尝试对数字 mod 3 和 5 进行硬编码。它没有给我正确的答案。Mathematica 说它们应该是 1 和 1，但我得到了 2 和 2。

有人可以告诉我发生了什么吗？

这是我第一次处理非常大的数字，我知道数据类型及其范围的限制，但这是硬编码的，没有任何内容存储在变量中。

任何人都知道如何在 java 中实现这样的问题？

“实现一个子程序，它采用三个正整数参数 (a;b;n) 并返回 ((a 的 b 次幂) mod n) 的值，其中参数由大约 100 个十进制数字表示。使用四种不同的方法。”

提前致谢

UPD：方法如下

M1)

M2)

M3)

M4)

我想知道如何计算 x^y mod z。x 和 y 非常大（不适合 64 位整数），而 z 将适合 64 位整数。有一件事不要给出答案，例如 x^y mod z 与 (x mod z)^y mod z 相同。

我知道，

但是有溢出的可能。为简单起见，我们假设整数的大小为 2 位。如果 a = 2（即 10 ₂）和 b = 2（即 10 ₂），m = 3（即 11 ₂），则 a%m 和 b%m 变为 2，乘法后，答案为 4（即100) 不适合整数大小。如果从 4 考虑 2-lsb，则最终答案将为 0。但实际答案为 1。

我应该怎么做才能避免这种情况？

这是由 Python 完成的

假设我们将幂运算集合的总和表示为一个元组列表，其中每个元组包含两个整数：基数和指数。例如，该列表表示2 ⁴ + 3 ⁵ + (-6) ³[(2,4),(3,5),(-6,3)]次方的总和。

实现一个函数sumOfPowers(nes, ps)，它将一个或多个元组的列表nes（即，nes形式[(a1,n1),...,(ak,nk)]为 ）作为其第一个参数，并将一个或多个素数列表ps（即，形式[p1,...,pm]）作为其第二个参数。只要满足以下条件，该函数就应该返回正确的幂和结果（例如，在具有无限内存和时间的计算机上）：

0 ≤ a1 ⁿ¹ + ... + ak ^nk < p1 ⋅ ... ⋅ pm

您可以假设第二个列表包含不同的素数。您可能不会假设第一个输入列表中的数字具有任何特定的模式或关系；它们可以是任何顺序，可以是任何大小，它们可能共享也可能不共享因子。您的实现必须在非常大的输入上有效地工作

有没有一种有效的方法来找到 1111.. ⁿ mod M 的值？
总是可以使用重复平方来找到
10 ⁰ mod M + 10 ¹ mod M + 10 ² mod M + 10 ³ mod M + ...10 ⁿ mod M
有比这更快的方法吗？

所以我试图找出离散对数问题和 RSA 之间的联系。我认为这就是以下问题试图做的事情。

所以我完全不知道如何解决这个问题。如果有人可以为我提供解决此问题的提示/解决方案，我将不胜感激。谢谢。

我试图估计将两个大位数以某个大素数为模相乘所需的时间。我的计算能力仅限于加法、乘法和存储 32 位数字。

由于这个原因，我想使用Karatsuba 算法，因为乘法被简化为一位数运算。然而，该算法不包含模约简。

我的另一个想法是使用蒙哥马利减少，但鉴于我的计算限制，我不确定这将如何执行。

你会建议我使用哪种算法？

在我短暂的体育编程生涯中，我遇到了很多次计算数字模型，例如

我做了一些研究，但只能找到表格中数字模型的计算

任何人都可以解释如何像第一个例子那样计算数字的模数。

当 2^n 除以 m 其中 n 和 m 是随机整数时，如果有任何可能的有效方法可以找到余数，我一直在徘徊。是否有任何方程式可以将 n 和 m 分给我以得到余数，还是我们必须遵循递归方法？请注意，我是初学者，而且我才刚刚开始，所以可能无法理解太复杂的东西。

提前致谢。