AKS برايم الخوارزمية في بيثون

Question

وقبل بضع سنوات، وقد ثبت أن يعبي في P . هل هناك أي خوارزميات تنفيذ على بريماليتي اختبار في بيثون؟ كنت أرغب في تشغيل بعض المعايير مع مولد السذاجة وأرى بنفسي مدى سرعة هو عليه. فما استقاموا لكم فاستقيموا تنفيذ ذلك بنفسي، لكنني لا أفهم هذه الورقة بما فيه الكفاية حتى الآن للقيام بذلك.

Answer 1

والجواب السريع: لا، اختبار AKS ليس هو أسرع وسيلة لاختبار بريماليتي. هناك كثير <م> كثير الاختبارات أسرع بريماليتي إما أن تحمل (معمم) فرضية ريمان و / أو العشوائية. (على سبيل المثال ميلر رابين عبارة سريعة وبسيطة لتنفيذ). وانفراج حقيقي من ورقة كانت النظرية، مما يثبت أن <م> القطعية في الوقت متعدد الحدود خوارزمية توجد لاختبار بريماليتي دون افتراض GRH أو غيرها من التخمينات غير مؤكدة.

وقال إنه إذا أردت أن تفهم وتنفيذه، سكوت أرونسون وباختصار المقالة قد تساعد. فإنه لا يذهب إلى كل التفاصيل، ولكن يمكنك أن تبدأ في الصفحة 10 من 12، وأنه يعطي بما فيه الكفاية. :-) وهناك أيضا من تطبيقات (ومعظمها في C ++) هنا.

وأيضا، لتحسين والتحسينات (من قبل عدة أوامر من حجم)، قد ترغب في النظر في <لأ href = "http://www.southerington.com/souther/projects/aks/RP-3_report.pdf" السمة rel = "noreferrer"> هذا التقرير أو (فوق) كراندال و تقرير بابادوبولوس أو (كبار السن لا يزال) تقرير دانيال J برنشتاين . كل منهم مفصلة إلى حد ما شبه التعليمات البرمجية التي يفسح المجال بشكل جيد لتنفيذها.

Answer 2

نعم، يذهب للبحث في AKS اختبار لصفحة يعبي على 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]