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

Несколько лет назад было доказано, что PRIMES находится в P. Существуют ли какие-либо алгоритмы, реализующие их тест на первичность в Python? Я хотел запустить некоторые тесты с наивным генератором и убедиться, насколько быстро это происходит. Я бы сам реализовал это, но я еще недостаточно разбираюсь в этой статье.

  • CKAN Install: paster error
  • Какие допустимые варианты использования для утверждения `assert` python?
  • Использование Pandas для pd.read_excel () для нескольких листов одной и той же книги
  • Отправка строки через сокет (python)
  • Как добавить двунаправленные многоточие в django admin?
  • Ошибка при попытке перегрузить оператор «/»
  • Разделение словаря / списка внутри столбца Pandas в отдельные столбцы
  • Python: использование 4 пробелов для отступа. Зачем?
  • 2 Solutions collect form web for “Алгоритм AKS Primes в Python”

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

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

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

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

    def expand_x_1(p): ex = [1] for i in range(p): ex.append(ex[-1] * -(pi) / (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] 
    Python - лучший язык программирования в мире.