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

(有关algorithm的声明，请参阅维基百科文章AKS primality test。)

下面是我为实现miller-rabin测试和我的(未完成) aks代码而编写的程序的链接。

如果有人能解释数学或者给我一点伪代码，我应该没问题。谢谢

aks.py miller.py

Answer 1

我在my blog上详细介绍了AKS。我正在我的手机上输入这个，所以你必须自己搜索它。