Verhuff एल्गोरिथ्म एक मनमाने ढंग से संख्या प्रणाली के लिए

कभी-कभी किसी व्यक्ति द्वारा किए गए आकस्मिक त्रुटियों से पहचानकर्ता स्ट्रिंग की रक्षा के लिए एक कार्य उत्पन्न होता है। उदाहरण के लिए, भुगतान कार्ड संख्या। ऐसा करने के लिए, एक विशेष तरीके से गणना किए गए चेक अंक को लाइन में जोड़ा जाता है, और जब कोई व्यक्ति इस नंबर में प्रवेश करता है, तो आप डेटाबेस तक पहुंच के बिना एक प्रारंभिक त्रुटि जांच कर सकते हैं। सबसे आसान विकल्प 10 से सभी अंकों के योग को विभाजित करने के शेष को जोड़ना है, जिस स्थिति में किसी एक अंक की विकृति (नियंत्रण एक सहित) का पता लगाना आसान होगा, और इस तरह की रेखा परीक्षण को पास नहीं करेगी। लेकिन कुछ अन्य त्रुटियां जैसे कि एक चेकसम याद आती हैं, उदाहरण के लिए, स्थानों में दो अंकों का एक क्रमांकन, और यह भी एक उचित त्रुटि है।

बैंक कार्ड नंबरों की सुरक्षा के लिए, थोड़ा अधिक जटिल एल्गोरिथ्म, चंद्रमा एल्गोरिदम, चुना गया था। इसमें एक संशोधन जोड़ा गया था: समयावधि में खड़े होने वाले आंकड़े संक्षेप से पहले 2 से गुणा किए जाते हैं (और यदि यह नौ से अधिक हो जाता है, तो 9 घटाया जाता है)। यह आपको किसी भी अंक को विकृत करने के अलावा पकड़ने की अनुमति देता है, सबसे (हालांकि सभी नहीं) आसन्न अंकों के क्रमपरिवर्तन।

क्या ऐसे एल्गोरिदम हैं जो आसन्न अंकों के किसी भी क्रमपरिवर्तन का पता लगा सकते हैं (किसी एक अंक को विकृत करने के अलावा)? हां, वे मौजूद हैं, हालांकि किसी कारण से वे बहुत आम नहीं हैं। यह वेधांश एल्गोरिथ्म है जो कि डायहड्रल समूहों पर आधारित है, और डैम एल्गोरिथ्म , जो कि डैम क्वासिग्रुप्स पर आधारित है। यह डरावना लगता है, लेकिन वास्तव में कुछ भी जटिल नहीं है (उन लोगों के लिए जो "समूह" की अवधारणा से परिचित हैं)।

एक गणितज्ञ और मूर्तिकार (तस्वीर में उनकी मूर्तियों में से एक) जैकबस वेरहोफ़ ने डायहेड्रल समूहों के आधार पर एक एल्गोरिथ्म का प्रस्ताव रखा। एक डायहड्राल समूह एक नियमित एन-गॉन के समरूपता का एक समूह है, जिसमें घुमाव और अक्षीय समरूपता दोनों शामिल हैं। ऐसा समूह सराहनीय नहीं है: यदि एक नियमित बहुभुज को लंबवत लंबवत पहले सममित रूप से प्रदर्शित किया जाता है और फिर घुमाया जाता है, तो ज्यादातर मामलों में यह वैसा नहीं होगा जैसा कि आप पहले घुमाते हैं और फिर प्रदर्शित करते हैं। और इसलिए, जब क्रमिक रूप से डायहड्रल समूह के संचालन का उपयोग करके मूल स्ट्रिंग के अंकों को "गुणा" किया जाता है, अर्थात। क्रमिक रूप से नियमित एन-गॉन पर रोटेशन और सममित मैपिंग संचालन को लागू करने से, हमें अधिकांश क्रमपरिवर्तन से सुरक्षा मिलती है। बहुमत से, लेकिन फिर भी हर किसी से नहीं। वेरखफ ने इस एल्गोरिथ्म को बेहतर बनाने का सुझाव दिया, और प्रत्येक अंक को एक विशेष तालिका के अनुसार दूसरे के साथ बदलने के लिए लाइन में अंकों के स्थान पर निर्भर करता है। तालिका को क्रमिक रूप से पिछले परिणाम पर लागू करके एक क्रमचय से प्राप्त किया जाता है, और 8 ऐसे अनुप्रयोगों के बाद हम मूल क्रम में आते हैं, इसलिए आप तालिका 8x10 का निर्माण कर सकते हैं और वहां से मान ले सकते हैं। इनमें से कुछ क्रमपरिवर्तन हमें स्रोत स्ट्रिंग के निकटवर्ती अंकों के क्रम में सभी 100% संभावित त्रुटियों को निर्धारित करने की अनुमति देते हैं, अर्थात्, यह चेक अंक खोजने की समस्या का एक पूर्ण और सही समाधान है जो इन दो प्रकार की त्रुटियों से बचाता है। जाहिरा तौर पर, वेरखफ ने यादृच्छिक चयन द्वारा एक सफल क्रमांकन पाया, उनमें से काफी कुछ हैं।

क्या ऐसे समूह मौजूद हैं जो अतिरिक्त संशोधनों के बिना आसन्न अंकों के किसी भी क्रमपरिवर्तन को खोजने की अनुमति देते हैं, जो लंबे समय से खुला है। और पहले से ही XXI सदी में, 2004 में, जर्मन गणितज्ञ माइकल डैम ने इस तरह के समूहों के अस्तित्व को साबित कर दिया, उन्हें कमजोर रूप से पूरी तरह से सममित विरोधी कजिनग्रुप कहा जाता है। मुझे पूरी तरह से पता नहीं है कि उन्हें कैसे बनाया जाए, जो लोग इसे प्रकाशित करके स्वयं ऐसा करने की कोशिश कर सकते हैं। और यद्यपि यह त्वरित रूप से देखने के दौरान इतना जटिल नहीं लगता (यह भी अजीब है कि प्रश्न इतने लंबे समय तक खुला रहा है), व्यावहारिक कार्यान्वयन के लिए एक आसान तरीका है: तैयार-किए गए तालिकाओं का उपयोग करें।

अब अगले और मुख्य प्रश्न पर चलते हैं: मुझे क्या करना चाहिए अगर मैं दशमलव अंकों की एक स्ट्रिंग की रक्षा नहीं करना चाहता, लेकिन मनमाने अक्षरों की एक स्ट्रिंग, उदाहरण के लिए, हेक्साडेसिमल या बेस 64 या बेस 58? यही है, समस्या को हल करने के लिए दशमलव संख्या प्रणाली के विशेष मामले में नहीं, बल्कि सामान्य रूप में।

चंद्रमा एल्गोरिदम इस मामले को बिना किसी समस्या के फैलाता है, लेकिन यह इतना दिलचस्प नहीं है, क्योंकि इसमें पड़ोसी अंकों के सभी क्रमचय नहीं मिलते हैं। मनमाने आकार के एंटीसिमेट्रिक कैसिग्रुप के निर्माण की विधि पूरी तरह से स्पष्ट नहीं है। वेरहफ़ एल्गोरिथ्म के लिए, आकार एन का एक विकेन्द्री समूह निर्माण करना आसान है, लेकिन आपको अभी भी एक क्रमचय तालिका की आवश्यकता है, जो यह भी स्पष्ट नहीं है कि इसे कहाँ प्राप्त करना है (और यह भी स्पष्ट नहीं है कि यह मौजूद है)। यह अंतिम प्रश्न का अध्ययन है, और मैंने शुरू किया।

Googling ने N = 64 के लिए अलग-अलग प्रयासों और "काफी अच्छे" समाधानों (यानी लगभग सभी क्रमपरिवर्तन का पता लगाने) के उपयोग के अलावा कुछ नहीं प्राप्त किया।

शायद मैं वांछित क्रमचय को खोजने के लिए सभी कोशिश किए गए और परीक्षण किए गए तरीकों का वर्णन नहीं करूंगा, जो एक परिणाम नहीं देते थे। मैंने एक विशेष समस्या को हल करने की कोशिश की: बेस 64 और बेस 58 के लिए एक क्रमचय को खोजने के लिए, जो पड़ोसी अंकों के क्रम को बदलने के खिलाफ सुरक्षा देता है। मैं केवल यह कह सकता हूं कि विभिन्न अनुकूलन विकल्पों के साथ यादृच्छिक या अनुक्रमिक खोज द्वारा इस तरह के क्रमचय को खोजने का प्रयास विफल रहा है। लेकिन अंत में, मुझे किसी भी एन के लिए एक सामान्य समाधान मिला।

क्रमांकन इस प्रकार है:

0, N-1 .. N/2+1, 1 .. N/2

उदाहरण के लिए, N = 10 के लिए यह होगा:

0, 9, 8, 7, 6, 1, 2, 3, 4, 5

इस क्रमचय में एक और उल्लेखनीय संपत्ति है: इसमें हमेशा 12 की अवधि (एन> = 8) होती है, जो आपको 12xN तालिका बनाने और वहां से एक अंक लेने की अनुमति देती है।

बेस 58 के लिए वेरहफ एल्गोरिथ्म के प्रस्तावित विस्तार के कार्यान्वयन का एक उदाहरण है (सख्ती से बोलना, यह वेरखफ का एल्गोरिदम नहीं है, लेकिन इसका सामान्यीकरण है)। पूर्ण परिवाद नहीं है, लेकिन सिर्फ एक उपयोगिता है, इसलिए बोलना, अवधारणा का प्रमाण।

यह प्रमाण कि इस क्रमचय में आवश्यक संपत्ति है, और इसकी अवधि 12 है, मैं कुछ समय बाद प्रदान करूंगा। यहां इसे फिट करने के लिए मार्जिन में बहुत कम जगह है।