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

Question

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

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

Answer 1

关于任意精度算术

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

您可以进一步扩展该概念,以创建仅受有限内存量限制的任意精度积分数据类型.基本上你有一个单词数组,你将N位数存储在这个数组的单词中.

它是一个32位操作系统的事实本身并不限制你可以做的数值计算.long例如,Java 是64位整数类型,无论它在哪里运行.对于任意精度,java.math.BigInteger提高ante并提供"无限字大小"抽象.是的,即使在32位操作系统中也可以使用这个"功能"(因为这绝不是一个限制因素).

也可以看看

• 维基百科/任意精度算术
• GNU MP BigNum库

关于整数环的数学

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

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

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(mod 7).

但你如何找到y = 2 ⁵⁵(mod 7)？好吧,一种天真的方法是线性地应用该过程并首先尝试找到z = 2 ⁵⁴(mod 7)等等.这是一个线性求幂,但你可以通过平方求幂来做得更好.

也就是说,如果你有说2 ⁸,你能够勇敢地正视它得到则会立即2 ¹⁶.然后你可以将其平方以立即获得2 ³².

摘要

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

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

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