Python 中 AKS 算法的多项式部分

Question

我需要有关 AKS 算法的多项式部分的一些帮助。

我在网上读了很多描述。 我已经进行了完美的功率测试，并且我认为我的 get_r() 函数是正确的。 我不知道如何去做这部分算法：

For a = 1 to square-root(totient(r) * log(n)):
if (X+a)^n != X^n+a (mod X^r − 1,n), output composite

（另请参阅维基百科文章AKS 素性测试，了解算法的声明。）

下面是我编写的用于实现 miller-rabin 测试的程序和我的（未完成的）aks 代码的链接。

如果有人可以解释数学或给我一些伪代码，我应该没问题。 谢谢

aks.py 米勒.py

Answer 1

我在我的博客中详细描述了 AKS。我在手机上输入此内容，因此您必须自己搜索。