में एकेएस प्राइम्स एल्गोरिदम कुछ साल पहले, यह साबित हुआ था कि PRIMES is in P। क्या Python में their primality test लागू करने वाले कोई भी एल्गोरिदम हैं? मैं एक बेवकूफ जनरेटर के साथ कुछ बेंचमार्क चलाने के लिए चाहता था और खुद को देखता हूं कि यह कितनी तेज़ है। मैं इसे स्वयं लागू कर दूंगा, लेकिन मुझे ऐसा करने के लिए पर्याप्त कागज़ को समझ में नहीं आता है।पायथन
त्वरित उत्तर: नहीं, एकेएस परीक्षण प्राथमिकता का परीक्षण करने का सबसे तेज़ तरीका नहीं है। बहुत सारे अधिक तेज प्रारंभिक परीक्षण हैं जो या तो (सामान्यीकृत) रिमेंन परिकल्पना मानते हैं और/या यादृच्छिक होते हैं। (उदा। Miller-Rabin लागू करने के लिए तेज़ और सरल है।) पेपर की वास्तविक सफलता सैद्धांतिक थी, यह साबित कर रही थी कि निर्धारक बहुपद परीक्षण समय के लिए बहुपद परीक्षण समय के लिए मौजूद है, जीआरएच या अन्य अप्रत्याशित अनुमानों को ग्रहण किए बिना।
उस ने कहा, यदि आप इसे समझना और कार्यान्वित करना चाहते हैं, तो Scott Aaronson's short article मदद कर सकता है। यह सभी विवरणों में नहीं जाता है, लेकिन आप 12 में से 10 पृष्ठ पर शुरू कर सकते हैं, और यह पर्याप्त प्रदान करता है। :-) यहां list of implementations (ज्यादातर सी ++ में) भी है।
इसके अलावा, अनुकूलन और सुधार (परिमाण के कई आदेशों द्वारा) के लिए, आप this report, या (पुराने) Crandall and Papadopoulos's report, या (पुराने अभी भी) Daniel J Bernstein's report को देखने के लिए चाहते हो सकता है। उनमें से सभी में काफी विस्तृत छद्म कोड है जो कार्यान्वयन के लिए खुद को अच्छी तरह से उधार देता है।
अपडेट: गणित का एक और अच्छा प्रदर्शन, टेरेन्स ताओ द्वारा, यहां: http://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/ – ShreevatsaR
एकेएस-टेस्ट सबसे तेज़ नहीं है रास्ता, लेकिन यह प्राइम्स के लिए पहला मूर्ख-प्रमाण परीक्षण है। – Progo
@Progo: अधिक सटीक, यह पहला परीक्षण है जिसे हम * साबित कर सकते हैं * मूर्ख-प्रमाण * और * बहुपद समय है। ऐसे कई परीक्षण हैं जिन्हें हम दृढ़ता से मानते हैं * वास्तव में पूरी तरह से मूर्ख-प्रमाण हैं (उदाहरण के लिए, उन्हें रिमैन हाइपोथिसिस जैसे दृढ़ विश्वास वाले अनुमानों को साबित करना संभव है), और ऐसे अन्य परीक्षण भी हैं जिन्हें हम साबित कर सकते हैं * साबित * पूरी तरह से हैं मूर्ख-प्रमाण, और जो लगभग हमेशा तेजी से दौड़ते हैं, लेकिन जिसे हम * साबित नहीं कर सकते * बहुपद समय हैं। एकेएस की सफलता दोनों ही कर रही थी। – ShreevatsaR
हाँ, AKS test for primes पेज को देखने जाना
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)])
rosettacode.org पर और आउटपुट है:
# 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]
यह एकेएस एल्गोरिदम नहीं है; यह एक ** घातीय-समय ** एल्गोरिदम है जो एकेएस एल्गोरिदम के पीछे प्राथमिक विचार लागू करता है जिसमें कोई भी विचार नहीं है जो इसे बहुपद बनाता है। – ShreevatsaR
अक्स महान सैद्धांतिक महत्व का है लेकिन इसके प्रदर्शन भयानक है (मिलर-राबिन ज्यादा है बेहतर)। पाइथन में लागू कई प्रारंभिक परीक्षण हैं। – jfs