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 primality testも参照してください。)
以下は、ミラー-ラビン テストを実装するために私が書いたプログラムと、(未完成の) aks コードへのリンクです。
誰かが数学を説明したり、疑似コードを少し教えてくれたりできれば、大丈夫です。ありがとう