सोलोवी-स्ट्रैसेन एल्गोरिथम

सोलोवी - स्ट्रैसेन टेस्ट

रॉबर्ट कोकिला और वोल्कर स्ट्रैसन ने एक संख्या की सादगी के लिए एक संभाव्य परीक्षण एल्गोरिथ्म विकसित किया जो जैकोबी प्रतीक का उपयोग करता है। संख्या को यौगिक या संभवत: प्रधान के रूप में परिभाषित करता है। यौगिक के रूप में कारमाइकल नंबर को पहचानता है।
तो, पहले आपको आवश्यक अवधारणाओं को पेश करना होगा।
द्विघात कटौती । यदि p अभाज्य है और 0 <a <p है, तो एक द्विघात अवशिष्ट modulo p है यदि x का मान है
x2 = (mod p)।
आदेश में एक द्विघात अवशेष modulo n होने के लिए, यह होना चाहिए एक द्विघात अवशेष modulo n के सभी प्रमुख भाजक। उदाहरण के लिए, यदि n = 7, तो द्विघात अवशेष 1, 2 और 4 हैं।
12 = 1 = 1 आधुनिक 7,
22 = 4 = 4 मॉड 7,
32 = 9 = 2 मॉड 7,
42 = 16 = 2 मॉड 7,
52 = 25 = 1 मॉड 7,
62 = 36 = 1 मॉड 7।
इसके विपरीत, निम्नलिखित समीकरणों में कोई x मान नहीं हैं जो उन्हें संतुष्ट करते हैं।
x2 = 3 mod 7,
x2 = 5 mod 7,
x2 = 6 आधुनिक 7।
तो, संख्या 3, 5 और 6 द्विघात अवशेष 7 हैं।
यदि संख्या पी विषम है, तो वास्तव में हैं (पी - 1) / 2 द्विघात अवशेष modulo p और कई द्विघात अवशेष modulo p। यदि n दो primes p और q का गुणनफल है, तो वास्तव में (p - 1) (q - 1) / 4 द्विघात अवशिष्ट modulo n हैं।
लीजेंड्रे और जैकोबी प्रतीकों का उपयोग करके primes और द्विघात अवशेषों के बीच संबंध स्थापित किया गया है।
लेजेंड्रे प्रतीक , जिसे L (a, p) के रूप में दर्शाया गया है, एक फंक्शन है जिसे परिभाषित किया जाता है यदि a कोई पूर्णांक है और p एक अभाज्य संख्या है जो 2. से अधिक है। लिजेंड्रे प्रतीक 0, 1 और -1 मान ले सकता है।
एल (ए, पी) = 0 यदि पी द्वारा विभाज्य है।
एल (ए, पी) = 1 अगर एक द्विघात अवशिष्ट मॉडुलो पी है,
एल (ए, पी) = -1 अगर एक द्विघात गैर-अवशेष मॉडुलो पी है।
संपीडित, ये तथ्य इस तरह लिखे गए हैं:
एल (ए, पी) = ए ^ ((पी - 1) / 2) मॉड पी।

पौराणिक प्रतीक गणना एल्गोरिथ्म।

1. यदि a = 1 है, तो L (a, p) = 1 है।
2. यदि संख्या एक समान है, तो L (a, p) = L (a / 2, p) * ((- 1) ^ ((p ^ 2-1) / 8))।
3. यदि संख्या विषम और a = = 1 है, तो L (a, p) = L (p mod a, a) * ((- 1) ^ ((a - 1) * (p - 1) / 4 ))।
जैकोबी प्रतीक , जिसे जे (ए, एन) के रूप में दर्शाया गया है, समग्र मॉड्यूल के लिए लीजेंड प्रतीक का सामान्यीकरण है। यह एक पूर्णांक और विषम पूर्णांक n के लिए परिभाषित एक फ़ंक्शन है। जैकोबी प्रतीक 0, 1, और -1 का मान ले सकता है।
जैकोबी प्रतीक को निम्नानुसार सेट किया जा सकता है।
1. जैकोबी प्रतीक केवल विषम संख्या n के लिए परिभाषित किया गया है।
2. जे (0, एन) = 0।
3. यदि n अभाज्य है, तो J (0, n) = 0 यदि n से विभाज्य है।
4. यदि n एक अभाज्य है, तो J (0, n) = 1, यदि a द्विघात अवशिष्ट modulo n है।
5. यदि n एक अभाज्य है, तो J (0, n) = –1, यदि a द्विघात गैर-अवशेष मोड्यूलर n है।
6. यदि n एक संयुक्त संख्या है, तो J (a, n) = J (a, p1) * ... * J (a, pm), जहाँ p1, ..., pm n का मुख्य कारक है।

जैकोबी प्रतीक की गणना के लिए एल्गोरिथ्म।

1. जे (1, एन) = 1।
2. जे (* * बी, एन) = जे (ए, एन) * जे (बी, एन)।
3. J (2, n) = 1 यदि (n ^ 2 - 1) / 8 सम है, और –1 अन्यथा।
4. जे (ए, एन) = जे ((एक एम एम), एन)।
5. जे (ए, बी 1 * बी 2) = जे (ए, बी 1) जे (ए, बी 2)।
6. यदि gcd (a, b) = 1 और, इसके अलावा, संख्या a और b विषम हैं, तो
6.1। J (a, b) = J (b, a) अगर (a - 1) * (b - 1) / 4 एक सम संख्या है।
6.2। J (a, b) =J (b, a) यदि (a - 1) * (b - 1) / 4 विषम संख्या है।
यदि n एक अभाज्य है, तो जैकोबी प्रतीक लेजेंड्रे प्रतीक के बराबर है।
जैकोबी प्रतीक का उपयोग यह जांचने के लिए नहीं किया जा सकता है कि संख्या एक द्विघात अवशेषों modulo n है (मामले के लिए छोड़कर जब संख्या n प्रमुख है)। यदि J (a, n) = 1 और n एक संयुक्त संख्या है, तो संख्या हमेशा एक द्विघात अवशेष नहीं होती है:
जे (7, 143) = जे (7, 11) * जे (7, 13) = (-1) * (- 1) = 1,
हालाँकि कोई पूर्णांक x नहीं है जैसे कि x2 mod 7 (mod 143)।

द सोलोवी - स्ट्रैसेन एल्गोरिथम

1. पी से कम एक यादृच्छिक संख्या का चयन करें।
2. यदि gcd (a, p)! = 1 है, तो संख्या p समग्र है और परीक्षण जारी रखा जा सकता है।
3. गणना जे = ए ^ ((पी - 1) / 2) मॉड पी।
4. जैकोबी प्रतीक J (a, p) की गणना करें।
5. यदि j! = J (a, p), तो संख्या p निश्चित रूप से अभाज्य नहीं है।
6. यदि j = J (a, p), तो संभावना है कि संख्या p अभाज्य नहीं है 50% से अधिक नहीं है।
वह संख्या, जो स्पष्ट रूप से इंगित नहीं करती है कि संख्या p अभाज्य नहीं है, एक गवाह कहलाता है। यदि पी एक समग्र संख्या है, तो संभावना है कि एक यादृच्छिक संख्या एक गवाह है कम से कम 50%। संभावना है कि एक मिश्रित संख्या t परीक्षण पास करती है 1 / (2 ^ t)।