खनन

वीडियो - फ़र्मट प्राइमिलिटी टेस्ट

एक त्वरित रूपरेखा यह और क्यों काम करता है ब्रिट क्रूज़ द्वारा निर्मित

TRANSCRIPT

हमारा लक्ष्य ऐसे कई निर्देशों को परिभाषित करना है, जो यह साबित कर सकते हैं कि कुछ इनपुट पूर्णांक समग्र है या फिर इसे प्रधानमंत्री के रूप में पहचानता है - कुछ बहुत ही उच्च सटीकता के साथ, जिसे हम परिभाषित कर सकते हैं और ऐसा करने में सक्षम होना चाहिए, जिसका अर्थ है कि यह किसी भी मशीन पर गणना करने के लिए तेज़ होना चाहिए, और यहां तक ​​कि अगर इनपुट का आकार बढ़ता है - जो कि हमारी इनपुट पूर्णांक n है - यह अभी भी तेज़ होना चाहिए

और अब तक, हमने सीखा है कि, निम्नतम स्तर पर, इसके लिए कुछ ज्ञात पैटर्न की आवश्यकता है कि सभी प्राइम का पालन करें और बहुत कम कंपोजिट का पालन करें। हालांकि, पिछले वीडियो में, हमने फ़र्मट के छोटे प्रमेय का दृश्य प्रदर्शन किया था। और यह हमें बहुत रोचक नियम प्रदान करता है कुछ प्रमुख संख्या, 'पी' और कुछ अन्य पूर्णांक 'ए' को देखते हुए, जो पी से कम है, हमें पता है, अब, पी पी को पायन की शक्ति को विभाजित करता है।

हम इसे एक ^ पी = एक आधुनिक पी के रूप में लिखते हैं। और यही वह तरीका है जिसे आप सामान्य रूप से देखते हैं। अब क्योंकि ए और पी कोई सामान्य कारक नहीं साझा करते हैं - क्योंकि पी प्रधान है - हम रद्द करने के कानून का उपयोग कर सकते हैं - और आप कभी-कभी इसे ^ (पी -1) = 1 आधुनिक पी के रूप में लिखा जाएगा। और याद रखो, हम केवल ऐसा कर सकते हैं क्योंकि ए और पी का सबसे बड़ा आम भाजक 1 के बराबर है। और यहां, मैंने सिर्फ एक डेमो स्थापित किया है, इसलिए हम पहले, केवल इस समीकरण को कार्यवाही में देख सकते हैं, और साथ सहज महसूस कर सकते हैं यह।

अब नोटिस करें, अगर मैं पी के लिए इनपुट इनपुट करता हूं, तो आउटपुट हमेशा 1 होता है, चाहे जो भी मैं चुनता हूं। यदि हम पी के लिए एक समग्र संख्या इनपुट करते हैं, तो हम देखते हैं कि यह आमतौर पर 1 नहीं है। और किसी भी समय यह समीकरण कुछ ऐसी चीज़ बनाता है जो 1 नहीं है, हमारे पास 'समग्र साक्ष्य है। 'यह अब सबूत है कि पी हमने चुना है प्रधानमंत्री नहीं हो सकता। और यह इस परीक्षा का सार है और किसी भी गहराई से पहले, चलो बस वापस कदम और इस परीक्षण के लिए रूपरेखा का निर्माण, इस पद्धति का उपयोग करके मैंने आपको दिखाया।

तो हमारा परीक्षण [राज्यों] हमें कुछ पूर्णांक के साथ प्रदान किया गया है - चलो इसे 'पी' कहते हैं- इनपुट के रूप में। इसके बाद, हम एक यादृच्छिक पूर्णांक उत्पन्न करते हैं, 'a', जो p से कम है और अब हम पूछ सकते हैं, "क्या ए और पी 1 का सबसे बड़ा आम भाजक है? "यदि नहीं - यदि एक और पी का सबसे बड़ा आम भाजक 1 से अधिक है, तो वे एक सामान्य कारक साझा करते हैं, और हमने सिद्ध किया है कि पी संमिश्र है - क्योंकि एक कारक मौजूद है।

और हम रोक सकते हैं और बाहर निकल सकते हैं और हमारा एल्गोरिथ्म 'समग्र होगा 'हालांकि, यदि' हां, 'और हम एक महत्वपूर्ण सवाल पूछ सकते हैं, "क्या पी कम से कम एक मॉड पी 1 के बराबर है? "यदि नहीं, तो हमारे पास एक गवाह है कि पी समग्र है हम रुक सकते हैं और कहते हैं, "हाँ। हो गया था। पी समग्र है "अन्यथा, यदि 'हां' - यदि हमारे समीकरण 1 का उत्पादन करता है - तो यह सही होगा, सही है? मैंने निर्देशों की इस श्रृंखला को कोडित किया है और बाईं तरफ हमारे पास फर्मीट टेस्ट है, और दायीं तरफ, मुझे यह वर्तमान परीक्षण डिवीजन परीक्षण में है।

और वह वहां है क्योंकि हम जानते हैं कि यह परीक्षण हमेशा सही है। और, पहली नज़र में, ऐसा लगता है कि यह काम कर रहा है।हालांकि, मुझे एक समस्या मिली। मैंने संख्या 511 को मारा, और अब फर्मीट के परीक्षण से यह कह रहा है कि वह प्रधानमंत्री है, और परीक्षण डिवीजन परीक्षण मुझे बता रहा है कि यह समग्र है। 511 परीक्षण के परिप्रेक्ष्य से प्रमुख लगता है लेकिन ऐसा नहीं है। अब चलो, बस वापस हमारे समीकरण पर लौटें, और देखें कि क्या हुआ।

खैर, यह एक उदाहरण है जिसे हम 'छद्म-प्रधानमंत्री' कहते हैं 'यह एक संमिश्र संख्या है। लेकिन कुछ निश्चित हैं कि हम यह चुन सकते हैं कि होगा आउटपुट 1 होगा। यह फिर से गलत है तो इन्हें एक संमिश्र संख्या में परिणाम मिलता है - 1 को आउटपुट करना - हम 'बेवकूफ' कह सकते हैं 'क्योंकि वे सोचते हैं कि हम संख्या को प्रधानमंत्री मानते हैं। लेकिन ध्यान दें कि अगर हम अलग-अलग चुनाव करते हैं, तो हम बेवकूफों के बजाय कई संमिश्र गवाहों को ढूंढते हैं। इसलिए, हम शायद वापस कदम उठा सकते हैं और हम उसी तर्क को लागू करते हैं जो हमने विभाज्यता परीक्षण में उपयोग किया था, जहां हम प्रयोग को कुछ बार दोहराते हैं, और हर बार नया यादृच्छिक उत्पन्न करते हैं।

और उम्मीद है, हम हर बार मूर्ख नहीं उठाएंगे। अब यह सिद्ध हो चुका है कि मूर्खों की संख्या को समूह के कुल आकार में विभाजित करना होगा जिसे हम चुनते हैं। जिसका अर्थ है, अधिकतर, इस पूल के विकल्पों में से आधे या आधा तत्व, मूर्ख हो सकते हैं इसलिए, चूंकि किसी को बेतरतीब ढंग से चुना जाता है, एक समग्र साक्षी खोजने का मौका - जो कि हम चाहते हैं - कम से कम एक आधा है टी पुनरावृत्तियों के बाद, संभावना है कि कोई भी समग्र संख्या के साथ कोई गवाह नहीं मिलेगा सबसे अधिक 1 / (2 ^ टी) है

इसलिए 20 परीक्षणों के बाद, एक प्रधानमंत्री को गलत तरीके से आउटपुट करने की संभावना दस लाख में एक से अधिक है। तो यही मामला है कि हम यादृच्छिक किसी को पैदा करने में वास्तव में बदकिस्मत प्राप्त करते हैं। और हर बार, हम एक मूर्ख चुनते हैं यदि आप उस सिंक को दे सकते हैं, तो समझने में वास्तव में शक्तिशाली है। और यहां अब, हम अपनी परीक्षा में कार्रवाई देख सकते हैं, परीक्षण की बढ़ी हुई संख्या के साथ, यह पूरी तरह से काम कर रहा है

और, ध्यान दें कि सबसे खराब स्थिति में - जो हम जानते हैं कि जब हम प्राइम के साथ हमारे एल्गोरिदम प्रदान करते हैं - यह अधिकतम काम करने जा रहा है Fermat परीक्षण अधिक कुशल है तो परीक्षण विभाजन - विशेष रूप से क्योंकि कदम की संख्या इनपुट के साथ पैमाने नहीं है और यह एक महत्वपूर्ण अंतर है

हमने परीक्षणों की संख्या निर्धारित की है, और यही है हमें कभी भी हमारे एल्गोरिदम के बारे में चिंता करने की ज़रूरत नहीं है, जैसा कि हमने पहले किया था, लाखों और लाखों चलनेवालों के लिए। तो, मेरा मतलब है, यह बुद्धिमानी से लागू गणित है हम एक ऐसे पैटर्न को ले रहे हैं जो किसी की खोज की गई है, और हम एक विशाल मात्रा में कम्प्यूटेशनल चक्रों की बचत कर रहे हैं। हालांकि, एक छोटी सी दोष है - या त्रुटि - इस प्रणाली में क्या आप इसे ढूँढ सकते है?