AKS素数性テストRosettaコードはどのように単純ですか？
最後までスキップして、別の質問を確認してください。
以下は、AKS素数性テストのPython実装です。
from sympy import *
def expand_x_1(n):
# This version uses a generator and thus less computations
c = 1
for i in range(n//2 + 1): # // means flooring after divide
c = c*(n - i)//(i + 1)
yield c
def aks(p):
if p==2:
return True
for i in expand_x_1(p):
if i % p:
# we stop without computing all possible solutions
return False
return True
for n in range(2, 10000):
primality = aks(n)
primality1 = isprime(n)
if primality != primality1:
print("Fails @", n) # Never prints
assert (0)
else:
print(primality)
彼らがアルゴリズムのはるかに詳細な擬似コード（多項式演算を含む）を取り、それをこの10行バージョンに変換した可能性はどのようにありますか？
上記は本当にAKS素数性テストですか？私はそれをから得ました：
https://rosettacode.org/wiki/AKS_test_for_primes#Python
入力を呼び出すようにします $n$ではなく $p$。
のコードはexpand_x_1(n)コンピューティングである必要があります。
$$c_0 = 1, c_i = \lfloor \dfrac{c_{i-1}(n-i)}{i + 1}\rfloor$$
どこ $c_i = $ インクルード $i$thは値をもたらしました。この値を使用する他のコードは、単に$c_i \neq 0 \pmod n$、その場合（trueの場合）False、compositeに戻ります。それ以外の場合はすべて$c_i$ の値 $i = 0..\lfloor \dfrac{n}{2} \rfloor + 1$ 我々は持っています $c_i = 0 \pmod n$、その後True返されます。
再帰とこのテストは、AKSアルゴリズムを構成するものとはまったく異なります。だから私は解析的整数論者が式を説明できることを望んでいた。
または、上記に答えられない場合は、次のようにします。
の式をどのように研究できますか $c_i$; あなたはそれが持っている再配置について考えることができますか？フロアなどがある再帰的なサブコール間で結合する分母など。
これは、この式に関して別の質問をする必要がないようにするためです。
たとえば、コードを次のように変更しました。
def expand_x_1(n):
c = 1
d = 1
for i in range(n//2 + 1):
d *= (i + 1)
c = c*(n - i)
yield c//d
したがって、実行しても失敗はないので、代数的に「分母を組み合わせることができる」、つまりフロアの基本的な特性に由来するアイデンティティが利用されているとある程度安全に推測できます。
他に何が言えるでしょうか。また、この式は多項式の算術とどのように関連していますか。
回答
ラベルを付けた番号 $c_i$ある二項係数は、 $\binom ni$; コードは$\binom ni \equiv 0 \pmod n$ すべてのために $0 < i \le \frac n2$。これはAKSアルゴリズムではありません。これは、AKSアルゴリズムを動機付けるために、ウィキペディアの記事にリストされている指数時間ブルートフォースアルゴリズムです。