फर्मेट और मिलर-राबिन सादगी परीक्षण

हाब्रोव्स्क नागरिकों को सलाम! आज हम उपयोगी सामग्री साझा करना जारी रखते हैं, जिसका एक अनुवाद विशेष रूप से "डेवलपर्स के लिए एल्गोरिदम" पाठ्यक्रम के छात्रों के लिए तैयार किया गया था।



कुछ संख्या n को देखते हुए, कैसे समझें कि यह संख्या अभाज्य है? मान लीजिए कि n शुरू में विषम है, क्योंकि अन्यथा कार्य काफी सरल है।

सबसे स्पष्ट विचार n सभी विभाजकों को देखना होगा, लेकिन अभी तक मुख्य समस्या एक कुशल एल्गोरिदम को ढूंढना है।

---

फार्म टेस्ट

फ़र्मेट के प्रमेय के अनुसार , यदि n एक अभाज्य है, तो किसी भी निम्नलिखित समानता के लिए: a n−1 =1 (mod n) । यहाँ से हम संख्या की सादगी की जाँच के लिए Fermat परीक्षण नियम को प्राप्त कर सकते हैं: एक यादृच्छिक a ∈ {1, ..., n−1} और जांचें कि समानता a n−1 =1 (mod n) रखती है। यदि समानता का सम्मान नहीं किया जाता है, तो सबसे अधिक संभावना n समग्र है।

फिर भी, यदि n सरल नहीं है, तो भी समानता की स्थिति को पूरा किया जा सकता है। उदाहरण के लिए, n = 561 = 3 × 11 × 17 । चीनी शेष प्रमेय के अनुसार :

Z 561 = Z 3 × Z 11 × Z 17

, जहां प्रत्येक where Z a ₅₆₁ निम्नलिखित से मेल खाता है:

(x,y,z) ∈ Z ∗ 3 ×Z ∗ 11 11×Z ∗ 17 .

फ़र्मेट के प्रमेय द्वारा, x 2 =1 , y 10 =1 , z 16 =1 । चूंकि 2, 10, और 16 सभी 560 भाजक हैं, इसका मतलब है कि (x,y,z) 560 = (1, 1, 1) , दूसरे शब्दों a 560 = 1 किसी भी a ∈ Z ∗ 561 a 560 = 1 a ∈ Z ∗ 561 लिए a 560 = 1 ।

इससे कोई फर्क नहीं पड़ता कि हम किसे चुनते हैं, 561 हमेशा फ़र्मेट टेस्ट पास करेगा, इस तथ्य के बावजूद कि यह समग्र है, जब तक कि एक n साथ पारस्परिक रूप से सरल है। ऐसी संख्याओं को कारमाइकल नंबर कहा जाता है और यह पता चलता है कि उनमें से अनंत संख्या में हैं।

यदि a , n साथ मैथुन नहीं करता है, तो वह Fermat परीक्षण पास नहीं करता है, लेकिन इस मामले में हम परीक्षणों को मना कर सकते हैं और n के विभाजकों की खोज जारी रख सकते हैं, GCD ( a, n ) की गणना कर सकते हैं।

मिलर-राबिन टेस्ट

हम यह कहकर परीक्षण में सुधार कर सकते हैं कि n अभाज्य है यदि और केवल यदि समाधान x 2 = 1 (mod n) x = ±1 by x = ±1 ।

इस प्रकार, यदि n फ़र्मेट टेस्ट पास करता है, अर्थात a n−1 = 1 , तो हम यह भी जाँचते हैं कि a (n−1)/2 = ±1 , a (n−1)/2 = ±1 , चूंकि a (n−1)/2 1 का वर्गमूल है।

दुर्भाग्य से, संख्याएं, उदाहरण के लिए, 1729 - तीसरा कारमाइकल नंबर अभी भी इस बेहतर परीक्षण को मूर्ख बना सकता है। क्या होगा अगर हम पुनरावृति? यही है, जब तक यह संभव है, हम घातांक को आधे से कम कर देंगे, जब तक कि हम 1 के अलावा किसी अन्य संख्या तक नहीं पहुंचते। यदि हम अंत में -1 के अलावा किसी और चीज में मिलते हैं, तो n समग्र होगा।

अधिक औपचारिक रूप से, 2 ^एस 2 की सबसे बड़ी शक्ति है, जो n-1 से विभाज्य है, अर्थात कुछ विषम संख्या q लिए n−1=2 S q q । अनुक्रम से प्रत्येक संख्या

a n−1 = a (2^S)q , a (2^S-1)q , ..., aq ।

यह अनुक्रम के पिछले सदस्य का वर्गमूल है।

फिर यदि n एक अभाज्य संख्या है, तो अनुक्रम 1 से शुरू होना चाहिए और प्रत्येक बाद की संख्या भी 1 होनी चाहिए, या अनुक्रम का पहला सदस्य 1 के बराबर नहीं हो सकता है, लेकिन फिर यह -1 है।

मिलर-राबिन परीक्षण एक यादृच्छिक a∈ Z n । a∈ Z n लेता है। यदि उपरोक्त अनुक्रम 1 से शुरू नहीं होता है, या यदि अनुक्रम का पहला सदस्य 1 या -1 नहीं है, तो n सरल नहीं है।

यह पता चला है कि कार्मिकेल संख्या सहित किसी भी मिश्रित n , मिलर-राबिन परीक्षण पास करने की संभावना लगभग 1/4 है। (औसतन, बहुत कम।) इस प्रकार, संभावना है कि n कई परीक्षण रन पास करेगा तेजी से घट जाती है।

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

जब परीक्षण फॉर्म pq की संख्याओं पर लागू होता है, जहाँ p और q बड़े अपराध होते हैं, तो वे लगभग सभी मामलों में मिलर-राबिन परीक्षण को पास नहीं करते हैं, क्योंकि अनुक्रम 1 से शुरू नहीं होता है। इसलिए, हम RSA को नहीं तोड़ पाएंगे।

व्यवहार में, मिलर-राबिन परीक्षण निम्नानुसार लागू किया गया है:

1. n को देखते हुए, हमें कुछ विषम q लिए ऐसा s n – 1 = 2 S q खोजना होगा।
2. एक यादृच्छिक a ∈ {1,...,n−1}
3. यदि एक ^q = 1 है, तो n परीक्षण पास करता है और हम निष्पादन को रोकते हैं।
4. i= 0, ... , s−1 लिए, समानता को सत्यापित करें a (2^i)q = −1 । यदि समानता रखती है, तो n परीक्षा पास करता है (निष्पादन रोकें)।
5. यदि उपरोक्त शर्तों में से कोई भी पूरा नहीं हुआ है, तो n समग्र है।

मिलर-राबिन परीक्षण करने से पहले, छोटे अपराधों में कुछ अधिक तुच्छ विभाजनों को अंजाम देना सार्थक है।

कड़ाई से बोलते हुए, ये परीक्षण इस बात के लिए परीक्षण हैं कि क्या एक संख्या को समग्र माना जाता है, क्योंकि वे वास्तव में साबित नहीं करते हैं कि जाँच की जा रही संख्या प्रमुख है, लेकिन वे निश्चित रूप से साबित करते हैं कि यह समग्र हो सकता है।

सादगी (अग्रवाल, कयाल और सक्सेना ) को निर्धारित करने के लिए अभी भी बहुपद समय में नियतात्मक एल्गोरिदम काम कर रहे हैं, लेकिन आज उन्हें अव्यवहारिक माना जाता है।