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

Question

目前，我试图根据NIST的FIPS186-4（附录B3.2.1）所示的算法实现generate_random_prime（）-函数，请参见here。你知道吗

但是step4.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，因为字节 我知道乌兰多姆不是最好的发电机-我以后会用一个批准的。。。对于测试阶段，我认为应该可以接受。。。你知道吗

结果总是“真的”——因此算法永远不会离开步骤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

它被包围了！-这就是为什么结果总是正确的吗？我认为在这种情况下，p永远不可能小于Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2))) - 1)

我怎样才能解决这个问题？你知道吗

你知道吗__ 编辑：发现错误： 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))

注意使用//，使用整数除法，而不是真除法（再次生成浮点）。你知道吗