如何使用大质数计算大数的模？

Question

如何使用大质数计算大数的模？

cryptographyprimesmodulus

3

我在软件环境中使用椭圆曲线密码学。我想查询如何有效地实现大数取模操作，并考虑到大质数的情况。例如：（192位数）mod（192位Mersenne素数）

如果您有任何技巧或算法，将非常有帮助，因为我正在使用资源受限的传感器节点。

- aviian7

通常情况下，您不仅仅有一个要对其应用mod p的n位数字。模运算必须集成到加法、乘法和指数运算中。 - Artjom B.

是的，抱歉我指的是'n'的二进制长度必须为192位。 - aviian7

相关问题：靠近2的幂次方的质数有哪些计算优势？和NaCL Poly1305实现如何进行模乘法？ - CodesInChaos

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fgrieu · Accepted Answer

在所提出的问题中，不存在192位梅森素数。

对于一个192位整数x在另一个192位质数p下的模归约实现非常简单：当x<p时，结果是x，否则结果是x-p。

也许问题实际上是关于对某个更大数量的192位质数

p 进行高效模块化约减，这种质数通常被选择为允许高效的模块化约减。例如，对于P-192，素数模数p 指定为6277101735386680763835789423207666416083908700390324961279，即fffffffffffffffffffffffffffffffeffffffffffffffff_h 或2¹⁹²-2⁶⁴-1。这个p非常接近(2³²)⁶，因此在使用2³²作为基数时，估算模p的模块化约减商位数就像在基数10中通过999899进行学校式欧几里得除法时估算新数字一样容易：大部分时间，剩余被除数的最左边数字就是商的新数字。