时间戳

首页 > 解决方案 > Python secrets.randbits 一旦增加到 16 以上就永远

python - Python secrets.randbits 一旦增加到 16 以上就永远

问题描述

我一直在尝试在 python 脚本中实现Fermat 测试以生成一个大素数，我希望在大素数上使用它，它可以快速且几乎完美地用于 16 位生成，但如果我将它设置为 32它根本不运行。

对于快速上下文，Fermat 测试应该运行 x 次试验（在我的代码中设置为 5 以便我可以查看它是否有效，但在使用中我可能会将其设置为更高约 20 或其他值）以测试是否数字是否为素数。所以我使用 secrets.randbits 生成大量数字，然后用 Fermat 测试检查它们是否是素数，如果不是，我选择一个不同的素数并再次运行它，直到找到一个。

将位设置为 16 时，代码运行速度很快，在测试的日志中打印许多不同的数字，然后发现它们是复合的并选择不同的，但是一旦设置为 32，则什么都不会打印，我真的不知道为什么。secrets.randbits 是否仅对增加的位起作用/花费的时间呈指数增长，因为在 16 位时程序几乎可以立即运行，但在 32 位时似乎根本不起作用。

这是我的代码：

import secrets 
import math

def fermat_test(n): # this is the correct algorithm from the video and it works set at 16 bits
    for x in range(1, 5): # to run 5 trials
        if (pow(secrets.randbelow(n - 1) + 1, (n - 1)) % n) != 1: 
            return False
    return True

bits = 16 # changing this to 32 the program will seemingly idle, not printing anything to console
rand = secrets.randbits(bits)
while (not fermat_test(rand)): # while the number is not prime
    print(rand) # prints the number being checked
    rand = secrets.randbits(bits)
print(rand)

抱歉，如果这太令人费解了，我可以尝试对其进行编辑以改写所有内容。

标签： pythoncryptography

解决方案

好消息：这与secrets. 改变这个：

        if (pow(secrets.randbelow(n - 1) + 1, (n - 1)) % n) != 1:

对此：

        if pow(secrets.randbelow(n - 1) + 1, (n - 1), n) != 1:

3 参数pow()非常有效地计算模幂。相反，您编写的内容创建了一个巨大的整数（您基本上是将 32 位整数提高到 32 位幂 - 结果将变成数十亿个十进制数字），然后才进行模数运算。

推荐阅读