问题标签 [chinese-remainder-theorem]

我试图让中国剩余定理算法工作，所以我一直在网上寻找帮助。我试图在 haskell 中编译这个 CRT 的例子，但是我得到了这些错误。我已经实现了自己的extGCD功能。

这是错误：

我正在用 pari/GP 执行中国剩余定理，结果是intmod.

例子：

x是中国剩余定理的输出。

但我想比较 24 和x.

如何从中提取“25”x以便能够将其与常规进行比较int？

我尝试实现中国剩余定理，为此我应该找到一些数字的乘法逆。函数正常工作，但如果它在 while 循环之后工作，则会产生错误的结果。

我想计算价值

F(N) = (F(N-1) * [((N-R+1)^(N-R+1))/(R^R)]) mod M 对于给定的 N,R 和 M 值.

这里 A^B 显示 A 幂 B 而不是任何按位运算

这里 M 不必是素数。如何解决这个问题？请帮忙，因为如果 M 是素数，那么找到 R^R mod M 的倒数就不会那么困难了。

但是因为 M 可以是从 1 到 10^9 的任何值。我无法解决这个问题。

N 可以介于 1 和 10^5 之间，并且 R 小于或等于 N。

通过以下 Openssl 命令生成 PEM 格式的 privateKey 文件以生成.csr.

现在，我想从那个文件中得到一个中国剩余定理 - 关键对象。但我现在不成功。所以也许你可以帮我一把。

这是由 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

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

我搜索了这个问题的答案，我得到了各种有用的链接，但是当我实现这个想法时，我得到了错误的答案。

这就是我的理解：

如果 m 是素数，那么它非常简单。任何数字“a”的反模数可以计算为：inverse_mod(a) = (a^(m-2))%m

但是当 m 不是素数时，我们必须找到 m 的素数，即m= (p1^a1)*(p2^a2)*....*(pk^ak).这里 p1,p2,....,pk 是 m 的素数，a1,a2,....,ak 是它们各自的素数权力。

然后我们必须计算：

…………

然后我们必须使用中国剩余定理（https://en.wikipedia.org/wiki/Chinese_remainder_theorem）组合所有这些余数

我为 m=1000,000,000 实现了这个想法，但我仍然得到错误的答案。

这是我对 m=1000,000,000 的解释，它不是素数

m= (2^9)*(5^9)其中 2 和 5 是 m 的主要因数。

令 a 是必须计算反模 m 的数。

现在要计算 'e1' 和 'e2' ，我使用了Extended Euclidean Algorithm。 https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

代码是：

但是在做了这一切之后，我得到了错误的答案。

请解释并指出我在理解中国剩余定理时所犯的任何错误。

非常感谢您。

我需要在 Haskell 中编写一个或多个函数来解决中国剩余定理。它需要使用以下定义创建：

答案看起来像

我想我有一个整体的想法，我只是没有知识来写它。我知道 crt 函数必须是递归的。我创建了一个辅助函数来将元组列表拆分为两个列表的元组：

在这个例子中，它给了我：

我想我需要知道的是为第一个列表中的每个元素创建一个列表。我将如何开始这样做？

所以我有一个总数，比如说24 ，我需要我的代码来找到最接近10的最高倍数。这当然是30，所以我需要代码来计算(30-24)。如果数字是20，那将是20 ，因为它等于最高的10倍数。然后我需要存储结果以备后用。

我是密码学的新手，我想知道是否有任何已经实现的方法来获取公钥剩余部分。

我发现以下关于公共余数的声明： 它Issuer Public Key Modulus分为两部分，一部分由 N CA 组成——模数的 36 个最高有效字节（颁发者公钥的最左边的数字），第二部分由剩余部分组成N I - (N CA – 36) 模数的最低有效字节 ( the Issuer Public Key Remainder)

在本书中：http: //mech.vub.ac.be/teaching/info/mechatronica/finished_projects_2007/Groep%201/Smartcard_files/EMV%20v4.1%20Book%202.pdf

我正在使用 org.bouncycastle.crypto.params.RSAPrivateCrtKeyParameters#getModulus

得到模量部分。

我可以使用 Bouncy Castle 获取公钥余数，还是应该根据上述规范手动计算？