Алгоритм AKS Primes в Python

Ответ 1

Быстрый ответ: нет, тест AKS - это не самый быстрый способ проверить простоту. Есть гораздо более быстрые тесты на примитивность, которые либо предполагают (обобщенную) гипотезу Римана, либо/или рандомизируют. (Например, Miller-Rabin быстро и просто реализовать.) Настоящий прорыв статьи был теоретическим, доказывая, что существует детерминированный алгоритм полиномиального времени для проверки примитивности, без предположения GRH или других недоказанных гипотез.

Тем не менее, если вы хотите понять и реализовать его, короткая статья Скотта Ааронсона может помочь. Он не затрагивает всех деталей, но вы можете начать со страницы 10 из 12, и это дает достаточно.:-) Существует также список реализаций (в основном на С++).

Кроме того, для оптимизации и улучшения (на несколько порядков) вы можете посмотреть этот отчет или (более старый) отчет Crandall и Papadopoulos или (еще более старый) отчет Дэниела Дж. Бернстайна. Все они имеют довольно подробный псевдокод, который хорошо поддается реализации.

Ответ 2

Да, посмотрите AKS test for primes на rosettacode.org

def expand_x_1(p):
    ex = [1]
    for i in range(p):
        ex.append(ex[-1] * -(p-i) / (i+1))
    return ex[::-1]

def aks_test(p):
    if p < 2: return False
    ex = expand_x_1(p)
    ex[0] += 1
    return not any(mult % p for mult in ex[0:-1])
    print('# p: (x-1)^p for small p')
    for p in range(12):
        print('%3i: %s' % (p, ' '.join('%+i%s' % (e, ('x^%i' % n) if n else '')
                                   for n,e in enumerate(expand_x_1(p)))))

print('\n# small primes using the aks test')
print([p for p in range(101) if aks_test(p)])

а выход:

# p: (x-1)^p for small p
  0: +1
  1: -1 +1x^1
  2: +1 -2x^1 +1x^2
  3: -1 +3x^1 -3x^2 +1x^3
  4: +1 -4x^1 +6x^2 -4x^3 +1x^4
  5: -1 +5x^1 -10x^2 +10x^3 -5x^4 +1x^5
  6: +1 -6x^1 +15x^2 -20x^3 +15x^4 -6x^5 +1x^6
  7: -1 +7x^1 -21x^2 +35x^3 -35x^4 +21x^5 -7x^6 +1x^7
  8: +1 -8x^1 +28x^2 -56x^3 +70x^4 -56x^5 +28x^6 -8x^7 +1x^8
  9: -1 +9x^1 -36x^2 +84x^3 -126x^4 +126x^5 -84x^6 +36x^7 -9x^8 +1x^9
 10: +1 -10x^1 +45x^2 -120x^3 +210x^4 -252x^5 +210x^6 -120x^7 +45x^8 -10x^9 +1x^10
 11: -1 +11x^1 -55x^2 +165x^3 -330x^4 +462x^5 -462x^6 +330x^7 -165x^8 +55x^9 -11x^10 +1x^11

# small primes using the aks test
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]