algorithm - 32 位操作系统如何执行 2^56 模 7？

Question

如果系统是密码学中的 32 位操作系统，系统如何执行 2^56 模 7？

它是如何存储在内存中的？

Answer 1

关于任意精度算术

32 位操作系统不限制您拥有超过该大小的自定义类型。您的应用程序可以采用两个 32 位字并将其视为一个 64 位数字。大多数编程语言甚至有一个“双字”整数类型来简化问题。

您可以进一步扩展该概念以创建仅受有限内存量限制的任意精度整数数据类型。本质上，您有一个单词数组，并且您将 N 位数字存储在该数组单词的位中。

它是一个 32 位操作系统这一事实本身并不限制您可以进行的数值计算。例如，Java long 是 64 位整数类型，无论它在何处运行。对于任意精度，java.math.BigInteger提高赌注并提供“无限字长”抽象。是的，即使在 32 位操作系统中也可以使用此“功能”(因为这从一开始就不是限制因素)。

另见

• Wikipediia/Arbitrary-precision arithmetic
• GNU MP BigNum library

---

论整数环上的数学

发现 modular multiplicative inverse或 modular exponentiation是密码学领域中常见的数学/算法任务。

您可能想在此处使用的一个标识如下:

A * B (mod M) == (A (mod M)) * (B (mod M)) (mod M)

要找到 x = 2⁵⁶ (mod 7)，您不必必须先计算并存储 2⁵⁶。如果你有 y = 2⁵⁵ (mod 7) -- 一个介于 0..6 之间的数字 -- 你可以找到 x = y * 2(模 7)。

但是如何找到 y = 2⁵⁵ (mod 7)？好吧，一种天真的方法是线性应用该过程并首先尝试找到 z = 2⁵⁴ (mod 7) 等等。这是一个线性求幂，但您可以通过执行例如exponentiation by squaring .

也就是说，如果你说 2⁸，你可以将它平方立即得到 2¹⁶。然后，您可以将其平方立即得到 2³²。

---

总结

有许多适用于密码学的复杂数学算法，它是否在 32 位或 64 位操作系统上运行的程序中实现并不直接相关。只要有足够的可用内存，计算机就能够执行任意精度的运算。

正是因为任意精度算法是一种有用的抽象，许多高性能库都可用，因此您可以在预先存在的框架之上构建您的应用程序，而不必从头开始构建。

一些高级语言甚至内置了任意精度的算术。例如，Python 在语言级别提供任意精度的 int 和 long。