Python secrets.randbits 一旦增加到 16 以上就永远需要

Question

我一直在尝试在 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)

抱歉，如果这太复杂了，我可以尝试对其进行编辑以重写所有内容。

Python密码学

Answer 1

好消息：这与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 位幂 - 结果将达到数十亿位十进制数字），然后才进行模运算。