问题标签 [chinese-remainder-theorem]

我有一个长整数，但它不是以十进制形式存储的，而是作为一组余数存储的。

所以，我没有N数字，而是一组这样的余数：

我知道，N 小于这些素数的乘积，所以中国剩余定理在这里确实有效（http://en.wikipedia.org/wiki/Chinese_remainder_theorem）。

如果我有这 6 个余数，如何N以十进制恢复？任何程序都可以做到这一点（C/C+GMP/C++/perl/java/bc）。

例如，最小 N 可以有这组余数：

我有多个包含多个同余的集合。

在将中国余数定理应用于每组中的一个项目时，我试图找到最小的余数。

以 2 套为例：

设置 1：

7x + 1
7x + 3

第 2 组：

11x
11x + 2
11x + 7
11x + 8

取 7x + 1 & 11x 得到 77x + 22。
我追求最小的余数（在上面的例子中 77x + 8），而不必测试所有组合。

这是我实际问题的非常简化的版本（约 50 组，每组约 100 个同余）。

我被困在如何解决这个问题上，任何建议将不胜感激。

另外，如果我的数学术语不正确，我深表歉意。

给定数组中的模值及其余数值，如何在 Matlab 中找到最小可能值？例如：

这导致了答案93；这是最小的可能值。

编辑：

这是我的代码，但它似乎只将剩余数组的最后一个值显示为最小值：

编辑 - 澄清

我正在尝试使用拉格朗日和中国余数定理在 Java 中实现模幂运算。

例如，如果 N 是 55，给定素数 5 和 11，phi 是 40，所以我知道有 40 个数字与低于 55 的 N 互质。我的导师说这样做的方法是“使用拉格朗日定理, 几个模 5 和 11 的乘法和 CRT 结合两个结果"

我的问题是如何计算这些数字？我需要他们将它们放入中国剩余定理中来完成计算，但我想不出一个聪明的方法来使用 phi(n) 循环遍历 N。N 将是一个非常大的数字，至少 1024 位。我可能在这里走错了路，我什至需要所有这些素数吗？

我确实怀疑答案将与扩展的 euclid 函数有关，我已经对其进行了编码，所以如果我需要使用它的结果，那很好。

我不明白N 以下多少个数与 N 互质？所以这对我没有多大帮助，而且我看的数学论文很难理解，总和和乘积类型符号让我有点困惑。此外，一些答案使用平方根和日志，这不是 BigInteger 的真正选项（如果我错了，请纠正我）

谁能用简单的英语给我答案？？

可以给我看代码，这更像是一个学习练习，因为我要提交的答案使用蒙哥马利。（是的，我知道，奇怪的是我可以从数学公式中算出蒙哥马利，但这个拉格朗日加 CRT 让我完全困惑）

我已经做到了这一点，通过我找到的一个例子来工作。素数是七和五，所以 35 的 phi 是 24（我有一个工作的欧拉函数）。

我需要使用 C# 实现 RSA 加密/解密

我有一个带有以下参数的私钥：

mod n, exponent, p, q, dP, dQ, 和(p-1mod q)

以上参数在中文余数算法中有解释

然而，RSA 的 C#.NET 实现具有不同的参数集，如下所示：

Modulus, Exponent, P, Q, DP, DQ, D,InverseQ

当我尝试将数据从 映射CRT到 时DOTNET，出现错误Bad Data

对于 p, q,dP和dQ映射是显而易见的，但关于其余参数我不确定。

如果我能获得映射这些参数的帮助，那就太好了

我正在尝试D使用P,Q和E( Dp,Dq并且也可用)。(p-1mod q)

根据这个答案和这个答案，并使用以下方法更新这个问题，我应该得到D。

为了测试这一点，我生成了密钥对并尝试从现有的组件中计算组件并将结果与​​原始组件进行比较。所有的结果都很好，除了D。我从上面的答案中复制的计算有问题。如果有人能告诉我我做错了什么，那就太好了。

测试代码

测试结果

我需要用整数编码S任意数量的元素（但有限）的序列K，并且能够解码K以获得初始序列。

我需要这样做，以便计算机能够很好地处理这个数字K。

我这样做了（在 lisp 中）：

• 假设序列 S 有 n 个元素 e1, ... en

• 生成前 n 个素数 p1 ... pn

• 写 K = p1^e1 + p2 ^ e2 + ... + pn ^ en

我试过这个方法。但是，我得到了巨大的数字。

我知道可以用chinese remainder theorem来解决问题，K得到的so并没有那么大。

有人可以帮助我使用这个定理来编码一个序列吗？

编辑：

我希望ch r th使用一个具体的简单示例来查看编码算法。我无法理解维基百科和其他网络资源中的理论思想。

在从元组向量（残差，模数）计算中国剩余定理时，以下代码失败：

将结果设为0（我猜生成的迭代是空的）。然而，以下代码完美运行：

这会产生（a）8851的正确结果。

为什么我必须list(使用第一批发电机之一？添加list到任何后续生成器不会更改失败 (0) 结果。仅列出第一个生成器会产生正确的结果。这里发生了什么 ？

我总是在处理nCr mod MM 通常是质数的在线编码平台上遇到很多问题。在不是的情况下，我们通常更喜欢使用中国剩余定理

我们是否可以比中国剩余定理更容易做到这一点，即如果我们只需要计算 N mod M 其中 M 不是素数，则可以编写更少的代码？

/* 在页面下方的 3/4 处，我有直接在本段下方列出的代码。我需要它来打印剩余部分，但似乎无法正确处理。我知道使用 Modulus 运算符是此功能的关键，但我不知道如何正确使用它。

*/