Computing Mod Without Mod
Computing Mod Without Mod
复制标题
没有 Mod 的计算 Mod
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
R. Ko
中科院分区：
文献类型：
--
作者：
M. Will;R. Ko
加密算法被设计成在不知道秘密或密钥的情况下很难被破解。为了实现这一点，算法要求密钥很大，有些算法的推荐大小为2048位或更多。然而，大多数现代处理器一次只支持64位的计算。因此，大数字的标准操作实现起来更加复杂。有效地实现一个特别具有挑战性的操作是模块化简化。本文提出了一种求解大模运算的高效算法；与当前的方法相比，它有几个优点，因为它支持使用可变大小的查找表，具有良好的空间和时间局部性，允许数据流，并且只需要基本的处理器指令。我们提出的算法在理论上与广泛使用的模块化算法进行了比较，然后与最先进的GNU多精度（GMP）大数库进行了实际比较。
Encryption algorithms are designed to be difficult to break without knowledge of the secrets or keys. To achieve this, the algorithms require the keys to be large, with some algorithms having a recommend size of 2048-bits or more. However most modern processors only support computation on 64-bits at a time. Therefore standard operations with large numbers are more complicated to implement. One operation that is particularly challenging to implement efficiently is modular reduction. In this paper we propose a highly-efficient algorithm for solving large modulo operations; it has several advantages over current approaches as it supports the use of a variable sized lookup table, has good spatial and temporal locality allowing data to be streamed, and only requires basic processor instructions. Our proposed algorithm is theoretically compared to widely used modular algorithms, before practically compared against the state-of-the-art GNU Multiple Precision (GMP) large number library.