Python：需要高整数精度的解决方案（生成素数）

Question

目前，我尝试根据 NIST（附录 B3.2.1）的 FIPS186-4 中所示的算法实现 generate_random_prime()- 函数，请参阅 here。

但是第 4.4 步似乎有一个大问题（如果 p < sqrt(2)*(2**((nlen/2)-1)），因为 Python 中的精度.

为了显示我的代码的相关部分和问题，请看这个例子：

import os
from decimal import Decimal
import math

for i in range(100):
    nlen = 2048 #my key-size should be 2048bit
    p = int.from_bytes(os.urandom(int(2048/2/8)), byteorder = "little") #see Ann1 and Ann2

    print(p < Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2))) - 1)

Ann1: 2048/2/8 因为字节 Ann2：我知道 os.urandom 不是最好的生成器 - 我稍后会使用经过批准的生成器...在测试阶段它应该是可以接受的我认为...

结果始终是 "True" - 因此算法永远不会离开步骤 4.4。

我认为问题是Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2))) - 1)，因为这样的结果是Decimal('2.542322012307292741109308792E+308')。通过 int(Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2))) - 1)) 转换为 int，结果将是

254232201230729274110930879200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

四舍五入了！ - 这是总是 True 结果的原因吗？我认为在这种情况下，永远不可能获得小于 Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2))) - 1)

的 p

我该如何解决这个问题？

__ 编辑：发现一个错误： Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2))) - 1) 应该是 Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2-1))))，所以这个结果应该是 Decimal('1.271161006153646370554654396E+308') 而不是 Decimal('2.542322012307292741109308791E+308')

Answer 1

你不断地在浮点数、整数和 Decimal 之间转换。放弃对 float 的所有使用；这包括不使用产生 float 值的函数，例如 math.sqrt().

坚持使用 Decimal 个对象，只将最终值转换为整数：

int(Decimal(2).sqrt() * 2 ** ((nlen // 2) - 1))

注意 // 的使用，使用整数除法，而不是真正的除法（再次产生浮点数）。

Python：需要高整数精度的解决方案（生成素数）

Python: Solution for high int-precision needed (generate primes)

python

math

int

primes

decimal