7

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

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

4

8 回答 8

16

关于任意精度算术

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

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

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

也可以看看

关于整数环上的数学

寻找模乘逆或模幂是密码学领域中常见的数学/算法任务。

您可能希望在此处使用的一种身份如下：

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

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

但是你如何找到y = 2 55 (mod 7)？好吧，一种天真的方法是线性应用该过程并首先尝试找到z = 2 54 (mod 7) 等等。这是一个线性取幂，但您可以通过执行例如通过平方取幂来做得更好。

也就是说，如果你说 2 8，你可以将它平方立即得到 2 16。然后，您可以将其平方以立即得到 2 32。

概括

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

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

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

于 2010-08-22T14:04:56.320 回答
4 
2**56 == 2**(28+28) == 2**28 * 2**28 == (2**28)**2
2**28 == 2**(14+14) == 2**14 * 2**14 == (2**14)**2
2**14 == 2**(7+7) == 2**7 * 2**7 == (2**7)**2
2**7 == 2**(3+3 +1) == 2**3 * 2**3 * 2 == (2**3)**2 * 2
2**3 == 2**(1+1 +1) == 2**1 * 2**1 * 2 == (2**1)**2 * 2

2**56 == (2**28)**2 == ((2**14)**2)**2 == (((2**7)**2)**2)**2
== (((2*(2**3)**2)**2)**2)**2 == (((2*(2*(2**1)**2)**2)**2)**2)**2

2**56 %7
== (((2*(2*(2**1)**2)**2)**2)**2)**2 %7
== (((2*(2*(2**1 %7)**2 %7)**2 %7)**2 %7)**2 %7)**2 %7
== (((2*(2*(2)**2 %7)**2 %7)**2 %7)**2 %7)**2 %7
== (((2*(2*4 %7)**2 %7)**2 %7)**2 %7)**2 %7
== (((2*(1)**2 %7)**2 %7)**2 %7)**2 %7
== (((2 %7)**2 %7)**2 %7)**2 %7
== ((2**2 %7)**2 %7)**2 %7
== ((4)**2 %7)**2 %7
== (16 %7)**2 %7
== (2)**2 %7
== 4 %7
== 4

so (2**56) % 7 == 4

您会注意到我们从未处理过任何大数字（实际上最大的是 56）。

此外：

2**224 %7 == (2**56)**4 %7 == (4*4*4*4) %7 ==
((16%7) * (16%7)) %7 == (2*2) %7 == 4 %7 == 4

因此还有2**896 %7 = 4, 等等（因为896 = 4 * 224, where 224 = 4 * 56）。

于 2011-02-08T00:46:43.037 回答
2

模幂算法用于这种操作。这篇维基百科文章讲述了它是如何完成的： http ://en.wikipedia.org/wiki/Modular_exponentiation

于 2010-08-22T14:04:33.110 回答
2

一般来说，如果你知道你的数字会变得非常大，你会使用像 GMP（Gnu Multi-Precision）这样的库来处理数学。如果你的手上有 2^32 个手指，它会做你在纸上做的事情。

于 2010-08-22T14:29:46.727 回答
0

哪个系统？哪种架构？

一般来说，在 32 位架构上，您会得到溢出结果。一些语言具有内置的、任意大的数字类型，可以处理这些计算。这方面的例子是BigDecimalJava 和 Python 中的内置long ints。

于 2010-08-22T14:04:11.003 回答
0

一个使用 (a * b) mod c = ((a mod c) * (b mod c)) mod c。这意味着你基本上可以做到

  1. 从 x=1 开始
  2. 做 x = (x*2)%7 56 次
于 2010-08-22T14:10:27.760 回答
0

我认为您的术语有点混乱。

32 位操作系统或 32 位体系结构是将机器地址限制为 32 位的一种。对于 32 位架构而言，具有对 64 位整数和/或 64 位浮点数进行运算的算术指令并不罕见。

因此，具有 32 位架构（并运行 32 位操作系统）的机器很可能会使用 64 位算术并将结果作为 64 位long或long long使用 2 个连续的 32 位字存储在内存中。

于 2010-08-22T14:55:04.500 回答
0

也添加到其他答案中，这些答案很好地解释了 32 int 和模乘逆以及什么不是

我将解释什么是 32 位 CPU

32 bit大多数人都知道的 CPU，与地址总线大小有关，这是可用的地址数量，例如在 x86（您的常见桌面 CPU [AMD，Intel]）处理器上，它允许2^32地址空间字节，或者4GB这是通常在可寻址硬件和 RAM 之间进行拆分，因此实际实现64 bit处理器的原因是因为我们也越来越接近4GBRAM 限制

作为旁注，这以前发生在 CPU 为 16 位时

于 2010-08-22T15:05:12.870 回答