问题标签 [bignum]

我的理解是，如今许多公钥密码算法都依赖于大素数来组成密钥，而难以分解两个素数的乘积使得加密难以破解。我的理解也是，分解如此大的数字如此困难的原因之一是，所使用的数字的绝对大小意味着没有 CPU 可以有效地处理这些数字，因为我们的微型 32 位和 64 位 CPU 无法匹配对于 1024、2048 甚至 4096 位数。必须使用专门的 Big Integer 数学库来处理这些数字，而这些库本身就很慢，因为 CPU 一次只能保存（和处理）小块（如 32 位或 64 位）。

所以...

为什么你不能构建一个具有 2048 位寄存器和巨大算术电路的高度专业化的定制芯片，就像我们从 8 位到 16 位到 32 位到 64 位 CPU 一样，只是构建一个更大的芯片？该芯片不需要传统 CPU 上的大部分电路，毕竟它不需要处理虚拟内存、多线程或 I/O 等事情。它甚至不需要是支持存储指令的通用处理器。只是对巨大数字执行必要的算术计算的最低限度。

我对 IC 设计了解不多，但我确实记得学习过逻辑门的工作原理，如何构建半加器、全加器，然后将一堆加法器连接在一起进行多位运算。只是放大。很多。

现在，我相当肯定有一个很好的理由（或 17 个）以上方法行不通（否则许多比我聪明的人中的一个已经这样做了），但我很想知道为什么它行不通。

（注意：这个问题可能需要重新处理，因为我什至不确定这个问题是否有意义）

我正在尝试学习 C，但遇到了无法处理非常大的数字（即 100 位、1000 位等）的问题。我知道存在执行此操作的库，但我想尝试自己实现它。

我只是想知道是否有人已经或可以提供对任意精度算术的非常详细、简单的解释。

这与几周前我自己的问题几乎完全相同。

当没有数据类型可以容纳完整数字时将十六进制转换为十进制

这一次，情况正好相反。我有数字（在一个方便的空终止字符串中），我需要构成这个数字的字节。但是，我正在为微控制器使用 32 位架构，因此我无法使用 atoi，因为该数字大于 32 位。

有没有人知道如何反转第一个链接中提供的算法以取回原始结果？我的模数算术技能让我失望了。

快速示例：155.207.231.135到0x[24][23][12][66][9F]（括号分隔字节）

大约 20 分钟前，我刚刚完成了 C 入门课程的考试。考试的第一个问题让我有点措手不及，涉及找出两个大数的差异。

目标是按值获取两个结构（N1 和 N2），并将差异存储在通过引用传递的结构（N3）中。我们被允许假设 N3 以全 0 启动。MAX 大小可以是任何值，因此如果数字超过 100 位，解决方案仍然必须有效。

这是基本代码（原文可能略有不同，这是凭记忆）

问题不在于找到解决此问题的方法，而是仅提供了大约 20 行来提供完整的答案。我的解决方法包括在转换为整数后一次减去一个数字，然后在结果为负数时进行适当的进位。这比提供的空间大得多。

基于为这个问题提供的少量标记和空间，我相信有一个我没有看到的相当微不足道的解决方案。它是什么？我现在已经完成了课程，但这个问题仍然困扰着我！

不需要完整的解决方案，只需要函数的内部工作difference。

不使用位运算符，以防万一。

emacs 是否支持不适合整数的大数字？如果是这样，我该如何使用它们？

我有四个无符号 32 位整数，代表一个无符号 128 位整数，以小端序排列：

我想将此数字转换为其十进制字符串表示形式并将其输出到文件中。

现在，我正在使用一个bigint_divmod10函数将数字除以 10，并记录余数。我反复调用这个函数，将余数作为数字输出，直到数字为零。这很慢。这是最快的方法吗？如果是这样，是否有一种聪明的方法来实现我没有看到的这个功能？我试过看 GMP 的get_str.c，但我觉得它非常难以理解。

编辑：这是我能够为 divmod10 函数提出的最快代码：

其中 add 函数定义为：

我正在编写自己的小型多精度库，在编写减法方法时，遇到了一些奇怪的错误。这是我为多精度减法编写的代码块：

p_aReverseIter->m_Value 是 32 位无符号整数，而 a,b 是 BigInt。值以 Big Endian 样式存储在向量中。temp 是 __int64 并且进位应该作为 32 位无符号长。

假设我们从 a 中减去 b，a > b（无符号减法），但是 b 中的所有 32 位字都比 a 大。该例程产生以下输出：

但进位应始终为 0xffffffffff。每次为零时，结果都是'13131314'，这是错误的。现在让我们将进位从 unsigned long 更改为 unsigned __int64 和

至

现在进位总是正确计算并设置为 0xffffffff。但是将 2^32 的 64 位值右移应该总是产生 32 位的结果。

我的问题是：要了解不同的结果，我错过了什么？

非常感谢。

我一直在使用 python 的原生 bignums 作为算法，并决定尝试通过将其转换为 C++ 来加速它。当我使用 long long 时，C++ 比 python 快大约 100 倍，但是当我在 C++ 中使用 GMP 绑定时，它只比 python 快 10 倍（对于适合 long long 的相同情况）。

是否有更好的 bignum 实现来进行大量的小加法？例如，我们有一个大数字 N，我们将添加很多小的 +1、+21、+1 等，并且每隔一段时间添加另一个大数字 M？

我正在做一些 Project Euler 问题，并且大多数时候，计算涉及超出 int、float、double 等的大量数字。

首先，我知道我应该寻找更有效的计算方法，以避免出现大数问题。我听说过 Bignum 库。

但是，出于学术兴趣，我想知道如何编写自己的解决方案来解决这个问题。

有哪位高手可以帮帮我吗？（我的语言是C）

我正在使用 F# Interactive，并添加了 FSharp.PowerPack.dll 的引用。

当我尝试将 BigNum 转换为以下代码时，

错误出来了

“System.MissingMethodException：找不到方法：'Double System.Numerics.BigInteger.ToDouble(System.Numerics.BigInteger)'。在 Microsoft.FSharp.Math.BigNum.ToDouble(BigNum n)”

如果我想进行“BigNum to int”和“BigNum to double”这样的转换，我该怎么办？非常感谢。