问题标签 [greatest-common-divisor]

我是一名高中生，正在写一篇关于 RSA 的论文，我正在用一些非常小的素数做一个例子。我了解系统的工作原理，但我无法终生使用扩展欧几里得算法计算私钥。

这是我到目前为止所做的：

• 我选择了质数 p=37 和 q=89 并计算出 N=3293
• 我计算出 (p-1)(q-1)=3168
• 我选择了一个数字 e，以便 e 和 3168 互质。我正在用标准的欧几里得算法检查这个，效果很好。我的 e=25

现在我只需要计算私钥 d，它应该满足 ed=1 (mod 3168)

使用扩展欧几里得算法找到 d 使得 de+tN=1 我得到 -887•25+7•3168=1。我把 7 扔掉，得到 d=-887。但是，尝试解密消息是行不通的。

我从我的书中知道 d 应该是 2281，它有效，但我不知道他们是如何得出这个数字的。

任何人都可以帮忙吗？在过去的 4 个小时里，我一直在尝试解决这个问题，并且到处寻找答案。我正在手动执行扩展欧几里得算法，但由于结果有效，我的计算应该是正确的。

提前致谢，

麦兹

使用 Mathematica (v.7) 基本上我想带一个这样的表达式

至

将像 GCD 这样的术语从一个被提升到一个幂并且是因式形式的表达式中提取出来的最佳方法是什么？然后将该项放在括号外并保留它被提升到的指数值。在将其取出之前，它必须知道该值已被提升到一个幂。这是我的尝试。

我一直在研究与该领域相关的所有不同功能，例如；收集、分解、扩展、简化、求解。我认为他们中的任何一个都不能产生我想要的输出。是否有一种内置的、更高效、可扩展和更短的方法可以使用模式/形式匹配来做到这一点？

计算n个数的最大公约数的最快方法是什么？

我的 LCM 程序得到了错误的结果。

我首先找到数字的 gcd，然后用 gcd 划分产品。

非常感谢任何帮助。

以下关系仅适用于两个 (3, 12) 数字，当用于三个数字 (3,12,10) 时无法产生正确答案。只是想知道这是我的理解还是仅适用于两个数字，对我来说，欧几里得算法也是如此。

我刚刚在我的讲义中发现了这个算法来计算最大公约数：

所以r是将b除为a时的余数（获取 mod）。然后将b分配给a，将余数分配给b，然后返回a。我一辈子都看不到这是如何工作的！

然后，显然这个算法不适用于所有情况，然后必须使用这个：

我不明白这背后的原因。我通常会递归并且擅长Java，但这让我望而却步。请帮忙？

为什么这段代码给我的答案是 25？

这是主要方法：

谁能向我提供所有程序如何运行或运行的完整过程？

所以我写了

就这样：

1. gcd(12, 9)
2. 9 <> 0 表示真
3. gcd(9, 12 % 9 = 3)
4. 3 <> 0 表示真
5. gcd(3, 9 % 3 = 0)
6. 0 <> 0 表示错误
7. 返回 a 这是 3 但它什么也不返回

你能帮我找出我的错误吗？

我正在尝试为 Euclid 查找两个数字的 GCD 的方法编写一个简单的缓存机制：

请注意gcd(a,b) == gcd(b,a).

对于缓存，我需要为给定的(a,b)or找到一个键(b,a)，使用0 < a < 20and 0 < b < 20。

当然，我可以使用key = a*20 + b, 或key = a + b*20，但它们是不对称的 - for 的密钥与 for(1,5)不同(5,1)。

我怎么能实现这个？

我已经启动了这个程序来计算最大公约数。这是我到目前为止所拥有的：

我总是得到 GCD 的 0。我究竟做错了什么？