आदिमता परीक्षण

प्राइमलिटी टेस्ट यह निर्धारित करने के लिए एक कलन विधि है कि कोई इनपुट संख्या अभाज्य संख्या है या नहीं। गणित के अन्य क्षेत्रों में इसका उपयोग क्रिप्टोग्राफी के लिए किया जाता है। पूर्णांक गुणनखंडन के विपरीत, प्रारंभिक परीक्षण आम तौर पर अभाज्य कारक नहीं देते हैं, केवल यह बताते हैं कि इनपुट संख्या अभाज्य है या नहीं। गुणनखंडन को एक कम्प्यूटेशनल रूप से कठिन समस्या माना जाता है, जबकि प्रारंभिक परीक्षण तुलनात्मक रूप से आसान है (इसकी रन-टाइम जटिलता इनपुट के आकार में बहुपद समय है)। कुछ प्रारंभिक परीक्षण साबित करते हैं कि एक संख्या अभाज्य है, जबकि अन्य जैसे मिलर-राबिन प्रारंभिक परीक्षण|मिलर-राबिन साबित करते हैं कि एक संख्या भाज्य संख्या है। इसलिए, बाद वाले को प्रारंभिक परीक्षणों के बजाय अधिक सटीक रूप से समग्रता परीक्षण कहा जा सकता है।

सरल विधियाँ

सबसे सरल प्रारंभिक परीक्षण परीक्षण प्रभाग है: एक इनपुट संख्या दी गई है, एन, जांचें कि क्या यह 2 और के बीच किसी अभाज्य संख्या से समान रूप से विभाज्य है √n (अर्थात विभाजन से कोई शेष नहीं बचता)। यदि हां, तो n भाज्य संख्या है। अन्यथा, यह प्रधान है.^[1] वास्तव में, किसी भी भाजक के लिए $p>{\sqrt {n}}$ , कोई अन्य भाजक होना चाहिए $n/p<{\sqrt {n}}$ , और इसलिए इससे छोटे भाजक की तलाश है √n काफी है।

उदाहरण के लिए, संख्या 100 पर विचार करें, जो इन संख्याओं से समान रूप से विभाज्य है:

2, 4, 5, 10, 20, 25, 50

ध्यान दें कि सबसे बड़ा कारक, 50, 100 का आधा है। यह सभी n के लिए सच है: सभी विभाजक n/2 से कम या उसके बराबर हैं।

जब n/2 तक के सभी संभावित भाजक का परीक्षण किया जाता है, तो कुछ कारकों को दो बार खोजा जाएगा। इसे देखने के लिए, विभाजकों की सूची को उत्पादों की सूची के रूप में फिर से लिखें, प्रत्येक 100 के बराबर है:

2 \times 50, 4 \times 25, 5 \times 20, 10 \times 10, 20 \times 5, 25 \times 4, 50 \times 2

ध्यान दें कि 10× 10 से आगे के उत्पाद केवल उन संख्याओं को दोहराते हैं जो पहले के उत्पादों में दिखाई देते थे, केवल क्रमविनिमेयता। उदाहरण के लिए, 5 × 20 और 20 × 5 विपरीत क्रम में समान संख्याओं से बने होते हैं। यह सभी n के लिए सत्य है: n के सभी अद्वितीय भाजक इससे कम या उसके बराबर संख्याएँ हैं √n, इसलिए हमें उससे आगे की खोज करने की आवश्यकता नहीं है।^[1] (इस उदाहरण में, √n = √100=10.)

2 से बड़ी सभी सम संख्याओं को भी हटाया जा सकता है: यदि एक सम संख्या n को विभाजित कर सकती है, तो 2 भी कर सकता है।

एक उदाहरण 17 की प्रारंभिकता का परीक्षण करने के लिए परीक्षण प्रभाग का उपयोग करना है। हमें केवल विभाजकों के लिए परीक्षण की आवश्यकता है √n, यानी पूर्णांक से कम या उसके बराबर $\scriptstyle {\sqrt {17}}\approx 4.12$ , अर्थात् 2, 3, और 4। 4 को छोड़ा जा सकता है क्योंकि यह एक सम संख्या है: यदि 4, 17 को समान रूप से विभाजित कर सकता है, तो 2 भी करेगा, और 2 पहले से ही सूची में है। इससे 2 और 3 बचते हैं। इनमें से प्रत्येक संख्या से 17 को विभाजित करें, और हम पाते हैं कि कोई भी 17 को समान रूप से विभाजित नहीं करता है - दोनों विभाजन शेषफल छोड़ते हैं। तो, 17 अभाज्य है।

इस पद्धति में और भी सुधार हो सकता है। ध्यान दें कि 3 से बड़े सभी अभाज्य अभाज्य इसी प्रकार के हैं $6 k \pm 1$ , जहां k 0 से बड़ा कोई पूर्णांक है। ऐसा इसलिए है क्योंकि सभी पूर्णांकों को इस प्रकार व्यक्त किया जा सकता है $(6 k + i)$ , जहां i = −1, 0, 1, 2, 3, या 4. ध्यान दें कि 2 विभाजित होता है $(6 k + 0), (6 k + 2), and (6 k + 4)$ और 3 भाग $(6 k + 3)$ . तो, एक अधिक कुशल तरीका यह जांचना है कि क्या n 2 या 3 से विभाज्य है, फिर फॉर्म की सभी संख्याओं की जांच करना $\scriptstyle 6k\ \pm \ 1\leq {\sqrt {n}}$ . यह अब तक के सभी नंबरों के परीक्षण से 3 गुना तेज है √n.

आगे सामान्यीकरण करते हुए, c# (प्राकृतिक संख्याओं के लिए प्राइमोरियल#परिभाषा) से बड़े सभी अभाज्य संख्याएं c# · k + i के रूप में होती हैं, i < c# के लिए, जहां c और k पूर्णांक हैं और i उन संख्याओं का प्रतिनिधित्व करता है जो c# के सहअभाज्य हैं। उदाहरण के लिए, चलो $c = 6$ . तब $c # = 2 \cdot 3 \cdot 5 = 30$ . सभी पूर्णांक रूप के हैं $30 k + i$ मेरे लिए में $i = 0, 1, 2,...,29$ और k एक पूर्णांक है। हालाँकि, 2, 0, 2, 4,..., 28 को विभाजित करता है; 3 भाग 0, 3, 6, ..., 27; और 5, 0, 5, 10, ..., 25 को विभाजित करता है। अतः 30 से बड़ी सभी अभाज्य संख्याएँ इस प्रकार की होती हैं $30 k + i$ के लिए $i = 1, 7, 11, 13, 17, 19, 23, 29$ (अर्थात के लिए $i < 30$ ऐसा है कि $gcd (i,30) = 1$ ). ध्यान दें कि यदि i और 30 सहअभाज्य नहीं होते, तो $30 k + i$ 30 के अभाज्य भाजक, अर्थात् 2, 3, या 5 से विभाज्य होगा, और इसलिए अभाज्य नहीं होगा। नकारात्मक i की अनुमति देने की पिछली विधि से मिलान करने के लिए, प्रत्येक i को 1 से c#-1 तक जांचने के बजाय (क्योंकि 0 और c# हमेशा सम होते हैं), प्रत्येक i को 1 से जांचें c#/2, जो मानों की सूची होगी जैसे कि सभी पूर्णांक फॉर्म के हों $c # k \pm i$ . इस उदाहरण में, $30 k \pm i$ के लिए $i = 1, 7, 11, 13$ . ध्यान दें कि इस सूची में हमेशा 1 और c से बड़े लेकिन छोटे अभाज्य संख्याओं का समूह शामिल होगा c#/2. उपरोक्त शर्तों को पूरा करने वाली सभी संख्याएँ अभाज्य नहीं हैं। उदाहरण के लिए, 437 c=7, c#=210, k=2, i=17 के लिए c#k + i के रूप का है। हालाँकि, 437 19*23 के बराबर एक भाज्य संख्या है। इसीलिए दिए गए फॉर्म की संख्याओं को अभी भी प्रारंभिकता के लिए परीक्षण करने की आवश्यकता है।

जैसा $c \to \infty$ , मानों की संख्या $c # k + i$ एक निश्चित सीमा को कम कर सकता है, और इसलिए n का परीक्षण करने का समय कम हो जाता है। इस विधि के लिए, c से कम सभी अभाज्य संख्याओं द्वारा विभाज्यता की जाँच करना भी आवश्यक है। पूर्ववर्ती के समान अवलोकनों को एराटोस्थनीज़ की छलनी देते हुए पुनरावर्तन लागू किया जा सकता है।

इन तरीकों (और नीचे उल्लिखित अन्य सभी तरीकों) को तेज़ करने का एक तरीका एक निश्चित सीमा तक सभी अभाज्य संख्याओं की एक सूची को पूर्व-गणना करना और संग्रहीत करना है, जैसे कि 200 तक के सभी अभाज्य। (ऐसी सूची की गणना इसके साथ की जा सकती है) एराटोस्थनीज़ की छलनी या एक एल्गोरिथ्म द्वारा जो सभी ज्ञात अभाज्य संख्याओं के विरुद्ध प्रत्येक वृद्धिशील एम का परीक्षण करता है √m). फिर, एक गंभीर विधि के साथ प्रारंभिकता के लिए n का परीक्षण करने से पहले, n को पहले सूची से किसी भी अभाज्य द्वारा विभाज्यता के लिए जांचा जा सकता है। यदि यह उन संख्याओं में से किसी से विभाज्य है तो यह समग्र है, और किसी भी अन्य परीक्षण को छोड़ा जा सकता है।

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

(p-1)!\equiv -1{\pmod {p}}\,

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

उदाहरण कोड

पायथन

निम्नलिखित सरल का उपयोग करके पायथन (प्रोग्रामिंग भाषा) में एक सरल मौलिकता परीक्षण है $6 k \pm 1$ अनुकूलन पहले उल्लेखित है। नीचे वर्णित अधिक परिष्कृत विधियाँ बड़े n.<सिंटैक्सहाइलाइट lang= Python3 > के लिए बहुत तेज़ हैं गणित आयात से isqrt def is_prime(n: int) -> बूल:

   यदि n <= 3:
       वापसी n > 1
   यदि n % 2 == 0 या n % 3 == 0:
       विवरण झूठा है
   सीमा = isqrt(n)
   श्रेणी में i के लिए (5, सीमा+1, 6):
       यदि n % i == 0 या n % (i+2) == 0:
           विवरण झूठा है
   सच लौटाओ

</वाक्यविन्यास हाइलाइट>

सी, सी++, सी# और डी

उपरोक्त के समान अनुकूलन का उपयोग करते हुए निम्नलिखित भाषाओं के सी (प्रोग्रामिंग भाषा) परिवार में एक प्रारंभिक परीक्षण है। <सिंटैक्सहाइलाइट लैंग = सी# > बूल इज़प्राइम(int n) {

   यदि (n == 2 || n == 3)
       वापसी सच;

   यदि (n <= 1 || n % 2 == 0 || n % 3 == 0)
       विवरण झूठा है;

   के लिए (int i = 5; i * i <= n; i += 6)
   {
       यदि (n % i == 0 || n % (i + 2) == 0)
           विवरण झूठा है;
   }

   वापसी सच;

} </वाक्यविन्यास हाइलाइट>

जावा

उपरोक्त के समान अनुकूलन का उपयोग करके निम्नलिखित जावा (प्रोग्रामिंग भाषा) में एक प्रारंभिक परीक्षण है।

import java.util.*;

public static boolean isPrime(int n){
    
    if (n <= 1)
        return false;
        
    if (n == 2 || n == 3)
        return true;
        
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    
    for (int i = 5; i <= Math.sqrt(n); i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
    }

जावास्क्रिप्ट

उपरोक्त के समान अनुकूलन का उपयोग करके निम्नलिखित जावास्क्रिप्ट में एक प्रारंभिक परीक्षण है।

function isPrime(num) {
  if (num == 2 || num == 3)
    return true;
  if (num <= 1 || num % 2 == 0 || num % 3 == 0)
    return false;  
  for (let i = 5; i * i <= num ; i+=6)
    if (num % i == 0 || num % (i + 2) == 0)
      return false;
  return true;
}

आर

उपरोक्त के समान अनुकूलन का उपयोग करके आर (प्रोग्रामिंग भाषा) में निम्नलिखित एक प्रारंभिक परीक्षण है।

is.prime <- function(number) {
  if (number <= 1) {
    return (FALSE)
  } else if (number <= 3) {
    return (TRUE)
  }

  if (number %% 2 == 0 || number %% 3 == 0) {
    return (FALSE)
  }

  i <- 5
  while (i*i <= number) {
    if (number %% i == 0 || number %% (i+2) == 0) {
      return (FALSE)
    }
    i = i + 6
  }
  return (TRUE)
}

डार्ट

उपरोक्त के समान अनुकूलन का उपयोग करके निम्नलिखित डार्ट (प्रोग्रामिंग_भाषा) में एक प्रारंभिक परीक्षण है।

checkIfPrimeNumber(number) {
  if (number == 2 || number == 3) {
    return 'true';
  } else if (number <= 1 || number % 2 == 0 || number % 3 == 0) {
    return 'false';
  }
  for (int i = 5; i * i <= number; i += 6) {
    if (number % i == 0 || number % (i + 2) == 0) {
      return 'false';
    }
  }
  return 'true';
}

फ़्री पास्कल <स्पैन क्लास = एंकर आईडी = फ्रीपास्कल >

उपरोक्त के समान अनुकूलन का उपयोग करके फ्री पास्कल में निम्नलिखित एक प्रारंभिक परीक्षण है।

function IsPrime(N:Integer):Boolean;
var
   I:Integer;
begin
   if ((N = 2) or (N = 3)) then Exit(True);
   if ((N <= 1) or (N mod 2 = 0) or (N mod 3 = 0)) then Exit(False);
   I := 5;
   while (I * I <= N) do
   begin
      if ((N mod I = 0) or (N mod (I+2) = 0)) then Exit(False);
      Inc(I, 6);
   end;
   Exit(True);
end;

गो<स्पैन क्लास= एंकर आईडी= गोलांग >

उपरोक्त के समान अनुकूलन का उपयोग करके गोलांग में निम्नलिखित एक प्रारंभिक परीक्षण है।

func IsPrime(num int) bool {
	if num > 1 && num <= 3 {
		return true
	}
	if num <= 1 || num%2 == 0 || num%3 == 0 {
		return false
	}

	for i := 5; i*i <= num; i += 6 {
		if num%i == 0 || num%(i+2) == 0 {
			return false
		}
	}
	return true
}

अनुमानी परीक्षण

ये ऐसे परीक्षण हैं जो व्यवहार में अच्छा काम करते प्रतीत होते हैं, लेकिन अप्रमाणित हैं और इसलिए, तकनीकी रूप से, बिल्कुल भी एल्गोरिदम नहीं हैं। फ़र्मेट परीक्षण और फाइबोनैचि परीक्षण सरल उदाहरण हैं, और संयुक्त होने पर वे बहुत प्रभावी होते हैं। जॉन सेल्फ्रिज ने अनुमान लगाया है कि यदि पी एक विषम संख्या है, और पी ≡ ±2 (मॉड 5), तो पी अभाज्य होगा यदि निम्नलिखित दोनों मान्य हों:

2^p−1 ≡ 1 (mod p),
एफ_p+1 ≡ 0 (मॉड पी),

जहां च_kk-वें फाइबोनैचि संख्या है। पहली शर्त आधार 2 का उपयोग करके फ़र्मेट प्राइमैलिटी परीक्षण है।

सामान्य तौर पर, यदि p ≡ a (mod x²+4), जहां a एक द्विघात गैर-अवशेष (mod x) है²+4) तो यदि निम्नलिखित स्थितियाँ लागू होती हैं तो p अभाज्य होना चाहिए:

2^p−1 ≡ 1 (mod p),
च(1)_p+1 ≡ 0 (मॉड पी),

च (एक्स)_k x पर k-वें फाइबोनैचि बहुपद है।

सेल्फ्रिज, कार्ल पोमेरेन्स और सैमुअल वैगस्टाफ मिलकर एक प्रति-उदाहरण के लिए $620 की पेशकश करते हैं।^[2]

संभाव्य परीक्षण

यादृच्छिक एल्गोरिदम अनुमानों की तुलना में अधिक कठोर हैं क्योंकि वे एक समग्र संख्या द्वारा मूर्ख बनाए जाने की संभावना पर सिद्ध सीमाएं प्रदान करते हैं। कई लोकप्रिय प्रारंभिक परीक्षण संभाव्य परीक्षण हैं। ये परीक्षण, परीक्षण की गई संख्या n के अलावा, कुछ अन्य संख्याओं का उपयोग करते हैं जिन्हें कुछ नमूना स्थान से यादृच्छिक रूप से चुना जाता है; सामान्य यादृच्छिक प्रारंभिक परीक्षण कभी भी अभाज्य संख्या को समग्र के रूप में रिपोर्ट नहीं करते हैं, लेकिन किसी भाज्य संख्या को अभाज्य के रूप में रिपोर्ट किया जाना संभव है। ए के कई स्वतंत्र रूप से चुने गए मानों के साथ परीक्षण को दोहराकर त्रुटि की संभावना को कम किया जा सकता है; आमतौर पर उपयोग किए जाने वाले दो परीक्षणों के लिए, किसी भी समग्र एन के लिए कम से कम आधा ए's पता लगाएं n's समग्रता, इसलिए k पुनरावृत्ति त्रुटि संभावना को अधिकतम 2 तक कम कर देती है^−k, जिसे k बढ़ाकर मनमाने ढंग से छोटा किया जा सकता है।

यादृच्छिक मौलिकता परीक्षणों की मूल संरचना इस प्रकार है:

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

एक या अधिक पुनरावृत्तियों के बाद, यदि n एक भाज्य संख्या नहीं पाया जाता है, तो इसे संभावित अभाज्य घोषित किया जा सकता है।

फ़र्मेट प्राइमैलिटी परीक्षण

सबसे सरल संभाव्य प्रारंभिक परीक्षण फ़र्मेट प्राइमलिटी परीक्षण (वास्तव में एक समग्रता परीक्षण) है। यह इस प्रकार काम करता है:

एक पूर्णांक n दिया गया है, कुछ पूर्णांक को n से सहअभाज्य चुनें और a की गणना करेंⁿ^{− 1}मॉड्यूलर अंकगणित n. यदि परिणाम 1 से भिन्न है, तो n समग्र है। यदि यह 1 है, तो n अभाज्य हो सकता है।

यदि एक^एन⁻¹ (modulo n) 1 है लेकिन n अभाज्य नहीं है, तो n को a कहा जाता है आधार के लिए स्यूडोप्राइम ए। व्यवहार में, हम देखते हैं कि, यदि ए^एन⁻¹ (मॉड्यूलो एन) 1 है, तो n आमतौर पर अभाज्य है। लेकिन यहाँ एक प्रति उदाहरण है: यदि n = 341 और a = 2, तो

2^{340}\equiv 1{\pmod {341}}

यद्यपि 341 = 11·31 संयुक्त है। वास्तव में, 341 सबसे छोटा छद्म अभाज्य आधार 2 है (चित्र 1 देखें)। ^[3]).

केवल 21853 स्यूडोप्राइम बेस 2 हैं जो 2.5 से कम हैं×10¹⁰ (पेज 1005 देखें ^[3]). इसका मतलब यह है कि, 2.5 तक n के लिए×10¹⁰, यदि 2ⁿ⁻¹ (मॉड्यूलो n) 1 के बराबर है, तो n अभाज्य है, जब तक कि n इन 21853 छद्म अभाजों में से एक न हो।

कुछ मिश्रित संख्याओं (कारमाइकल संख्याओं) में यह गुण होता है कि aⁿ^{− 1} प्रत्येक a के लिए 1 (modulo n) है जो n का सहअभाज्य है। सबसे छोटा उदाहरण n = 561 = 3·11·17 है, जिसके लिए a⁵⁶⁰561 के सभी सहअभाज्य के लिए 1 (मॉड्यूलो 561) है। फिर भी, यदि संख्याओं की तीव्र स्क्रीनिंग की आवश्यकता होती है, तो फ़र्मेट परीक्षण का उपयोग अक्सर किया जाता है, उदाहरण के लिए आरएसए (एल्गोरिदम) के प्रमुख पीढ़ी चरण में।

मिलर-राबिन और सोलोवे-स्ट्रैसन प्राइमैलिटी टेस्ट

मिलर-राबिन प्राइमलिटी टेस्ट और सोलोवे-स्ट्रैसेन प्राइमलिटी टेस्ट अधिक परिष्कृत वेरिएंट हैं, जो सभी कंपोजिट का पता लगाते हैं (एक बार फिर, इसका मतलब है: प्रत्येक समग्र संख्या एन के लिए, कम से कम 3/4 (मिलर-राबिन) या 1/2 (सोलोवे) -स्ट्रैसेन) संख्याओं के ए एन की समग्रता के गवाह हैं)। ये समग्रता परीक्षण भी हैं।

मिलर-राबिन प्राइमैलिटी परीक्षण इस प्रकार काम करता है: एक पूर्णांक n दिया गया है, कुछ धनात्मक पूर्णांक a <<n चुनें। चलो 2^sd = n − 1, जहां d विषम है। अगर

a^{d}\not \equiv \pm 1{\pmod {n}}

और

a^{2^{r}d}\not \equiv -1{\pmod {n}}

सभी के लिए

0\leq r\leq s-1,

तब n समग्र है और a समग्रता का साक्षी है। अन्यथा, n अभाज्य हो भी सकता है और नहीं भी। मिलर-राबिन परीक्षण एक मजबूत स्यूडोप्राइम परीक्षण है (पीएसडब्ल्यू देखें)।^[3]पृष्ठ 1004)।

सोलोवे-स्ट्रैसेन प्राइमैलिटी परीक्षण एक और समानता का उपयोग करता है: एक विषम संख्या n को देखते हुए, कुछ पूर्णांक a < n चुनें, यदि

a^{(n-1)/2}\not \equiv \left({\frac {a}{n}}\right){\pmod {n}}

, कहाँ

\left({\frac {a}{n}}\right)

जैकोबी प्रतीक है,

तब n समग्र है और a समग्रता का साक्षी है। अन्यथा, n अभाज्य हो भी सकता है और नहीं भी। सोलोवे-स्ट्रैसेन परीक्षण एक यूलर स्यूडोप्राइम परीक्षण है (पीएसडब्ल्यू देखें)।^[3]पृष्ठ 1003)।

के प्रत्येक व्यक्तिगत मान के लिए, सोलोवे-स्ट्रैसेन परीक्षण मिलर-राबिन परीक्षण से कमजोर है। उदाहरण के लिए, यदि n = 1905 और a = 2, तो मिलर-राबिन परीक्षण से पता चलता है कि n समग्र है, लेकिन सोलोवे-स्ट्रैसन परीक्षण से पता नहीं चलता है। ऐसा इसलिए है क्योंकि 1905 एक यूलर है स्यूडोप्राइम बेस 2 लेकिन मजबूत स्यूडोप्राइम बेस 2 नहीं (यह पीएसडब्ल्यू के चित्र 1 में दिखाया गया है)^[3]).

फ्रोबेनियस प्राइमलिटी परीक्षण

मिलर-राबिन और सोलोवे-स्ट्रैसेन प्राइमलिटी परीक्षण सरल हैं और अन्य सामान्य प्राइमैलिटी परीक्षणों की तुलना में बहुत तेज़ हैं। कुछ मामलों में दक्षता में और सुधार करने का एक तरीका फ्रोबेनियस स्यूडोप्राइम है; इस परीक्षण के एक राउंड में मिलर-राबिन के एक राउंड से लगभग तीन गुना अधिक समय लगता है, लेकिन मिलर-राबिन के सात राउंड के बराबर संभावना प्राप्त होती है।

फ्रोबेनियस परीक्षण लुकास स्यूडोप्राइम परीक्षण का सामान्यीकरण है।

बेली-पीएसडब्ल्यू प्रारंभिक परीक्षण

बैली-पीएसडब्ल्यू प्राइमलिटी टेस्ट एक संभाव्य प्राइमलिटी टेस्ट है जो लुकास स्यूडोप्राइम टेस्ट के साथ फ़र्मेट या मिलर-राबिन टेस्ट को जोड़ता है ताकि प्राइमलिटी टेस्ट प्राप्त किया जा सके जिसका कोई ज्ञात प्रति-उदाहरण नहीं है। अर्थात्, कोई ज्ञात समग्र n नहीं है जिसके लिए यह परीक्षण रिपोर्ट करता है कि n संभवतः अभाज्य है।^[4]^[5] यह दिखाया गया है कि n के लिए कोई प्रति उदाहरण नहीं हैं $<2^{64}$ .

अन्य परीक्षण

लियोनार्ड एडलमैन और मिंग-देह हुआंग ने एलिप्टिक वक्र प्राइमलिटी सिद्ध करने का एक त्रुटि रहित (लेकिन अपेक्षित बहुपद-समय) संस्करण प्रस्तुत किया। अन्य संभाव्य परीक्षणों के विपरीत, यह एल्गोरिदम एक प्राइमलिटी प्रमाणपत्र तैयार करता है, और इस प्रकार इसका उपयोग यह साबित करने के लिए किया जा सकता है कि कोई संख्या अभाज्य है।^[6] व्यवहार में एल्गोरिदम अत्यधिक धीमा है।

यदि एक कंप्यूटर जितना उपलब्ध होते, तो शास्त्रीय कंप्यूटरों का उपयोग करने की तुलना में बिग ओ नोटेशन का परीक्षण किया जा सकता था। शोर के एल्गोरिथ्म का एक संयोजन, एक पूर्णांक गुणनखंडन विधिपॉकलिंगटन प्राइमैलिटी टेस्ट परीक्षण के साथ समस्या को हल कर सकता है $O((\log n)^{3}(\log \log n)^{2}\log \log \log n)$ .^[7]

तेज़ नियतात्मक परीक्षण

20वीं सदी की शुरुआत में, यह दिखाया गया कि फ़र्मेट के छोटे प्रमेय के परिणाम का उपयोग आदिमता के परीक्षण के लिए किया जा सकता है।^[8] इसके परिणामस्वरूप पॉकलिंगटन प्राइमैलिटी परीक्षण हुआ।^[9] हालाँकि, चूँकि इस परीक्षण के लिए n - 1 के आंशिक गुणनखंडन की आवश्यकता होती है, इसलिए सबसे खराब स्थिति में भी चलने का समय काफी धीमा था। पहला नियतात्मक एल्गोरिथ्म प्राइमैलिटी परीक्षण, जो भोली-भाली विधियों की तुलना में काफी तेज़ था, एडलमैन-पोमेरेन्स-रुमली प्राइमैलिटी टेस्ट था; इसका रनटाइम बिग ओ नोटेशन साबित हो सकता है((लॉग एन)^{सी लॉग लॉग लॉग एन}), जहां एन प्रारंभिकता के परीक्षण के लिए संख्या है और सी एन से एक स्थिर स्वतंत्र है। कई और सुधार किए गए, लेकिन किसी में भी बहुपद के चलने का समय साबित नहीं हो सका। (ध्यान दें कि चलने का समय इनपुट के आकार के संदर्भ में मापा जाता है, जो इस मामले में ~ लॉग एन है, जो कि संख्या एन का प्रतिनिधित्व करने के लिए आवश्यक बिट्स की संख्या है।) एलिप्टिक वक्र प्राइमलिटी को चलाने के लिए सिद्ध किया जा सकता है ओ((लॉग एन)⁶), यदि विश्लेषणात्मक संख्या सिद्धांत पर कुछ अनुमान सत्य हैं।^[which?] इसी तरह, सामान्यीकृत रीमैन परिकल्पना के तहत, नियतात्मक मिलर-राबिन प्राइमैलिटी टेस्ट#नियतात्मक वेरिएंट|मिलर का परीक्षण, जो संभाव्य मिलर-राबिन परीक्षण का आधार बनता है, को बड़े ओ नोटेशन में चलने के लिए साबित किया जा सकता है#बैचमैन के लिए एक्सटेंशन- लैंडौ नोटेशन|Õ((लॉग एन)⁴).^[10] व्यवहार में, यह एल्गोरिदम उन संख्याओं के आकार के लिए अन्य दो की तुलना में धीमा है जिनसे बिल्कुल भी निपटा जा सकता है। चूँकि इन दोनों विधियों का कार्यान्वयन कठिन है और प्रोग्रामिंग त्रुटियों का खतरा पैदा करता है, इसलिए धीमे लेकिन सरल परीक्षणों को अक्सर प्राथमिकता दी जाती है।

2002 में, प्रारंभिकता के लिए पहला सिद्ध बिना शर्त नियतात्मक बहुपद समय परीक्षण का आविष्कार मनिंद्र अग्रवाल, -नीरज कयाल और नितिन सक्सैना द्वारा किया गया था। AKS प्रारंभिक परीक्षण Õ((लॉग एन) में चलता है¹²) (Õ((लॉग एन) में सुधार)^7.5)^[11] उनके पेपर के प्रकाशित संशोधन में), जिसे आगे घटाकर Õ((लॉग एन) किया जा सकता है)⁶) यदि सोफी जर्मेन प्राइम सत्य है।^[12] इसके बाद, लेनस्ट्रा और पोमेरेन्स ने परीक्षण का एक संस्करण प्रस्तुत किया जो समय Õ((लॉग एन) में चलता है⁶) बिना शर्त.^[13] अग्रवाल, कायल और सक्सेना अपने एल्गोरिदम का एक प्रकार सुझाते हैं जो Õ((लॉग एन) में चलेगा)³) यदि अग्रवाल का अनुमान सत्य है; हालाँकि, हेंड्रिक लेनस्ट्रा और कार्ल पोमेरेन्स के एक अनुमानी तर्क से पता चलता है कि यह संभवतः गलत है।^[11]अग्रवाल के अनुमान का एक संशोधित संस्करण, अग्रवाल-पोपोविच अनुमान,^[14] अभी भी सच हो सकता है.

जटिलता

कम्प्यूटेशनल जटिलता सिद्धांत में, अभाज्य संख्याओं के अनुरूप औपचारिक भाषा को PRIMES के रूप में दर्शाया जाता है। यह दिखाना आसान है कि प्राइम्स सह-एनपी में है: इसका पूरक कंपोजिट एनपी में है क्योंकि कोई भी किसी कारक का गैर-निर्धारणात्मक अनुमान लगाकर समग्रता का निर्णय कर सकता है।

1975 में, वॉन प्रैट ने दिखाया कि आदिमता के लिए एक प्रमाण पत्र मौजूद था जिसे बहुपद समय में जांचा जा सकता था, और इस प्रकार प्राइम्स एनपी (जटिलता) में था, और इसलिए ${\mathsf {NP\cap coNP}}$ . विवरण के लिए मौलिकता प्रमाणपत्र देखें।

सोलोवे-स्ट्रैसेन और मिलर-राबिन एल्गोरिदम की बाद की खोज ने PRIMES को RP (जटिलता) में डाल दिया। 1992 में, एडलमैन-हुआंग एल्गोरिदम^[6]जटिलता को ZPP (जटिलता) तक कम कर दिया| ${\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}$ , जिसने प्रैट के परिणाम को प्रतिस्थापित कर दिया।

1983 के एडलमैन-पोमेरेन्स-रुमली प्राइमैलिटी परीक्षण ने प्राइम्स को QP (अर्ध-बहुपद समय) में डाल दिया, जिसे ऊपर उल्लिखित वर्गों के साथ तुलनीय नहीं माना जाता है।

व्यवहार में इसकी ट्रैक्टिबिलिटी, रीमैन परिकल्पना को मानने वाले बहुपद-समय एल्गोरिदम और इसी तरह के अन्य सबूतों के कारण, यह लंबे समय से संदेह था लेकिन साबित नहीं हुआ कि बहुपद समय में मौलिकता को हल किया जा सकता है। AKS प्रारंभिक परीक्षण के अस्तित्व ने आखिरकार लंबे समय से चले आ रहे इस प्रश्न का समाधान कर दिया और PRIMES को P (जटिलता) में डाल दिया। हालाँकि, PRIMES को P-पूर्ण नहीं माना जाता है, और यह ज्ञात नहीं है कि यह P के अंदर आने वाली कक्षाओं जैसे NC (जटिलता) या L (जटिलता) में स्थित है या नहीं। यह ज्ञात है कि PRIMES AC0|AC में नहीं है^{0</उप>।^[15]}

संख्या-सैद्धांतिक विधियाँ

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

लुकास परीक्षण इस तथ्य पर निर्भर करता है कि किसी संख्या a modulo n का गुणन क्रम किसी अभाज्य n के लिए n - 1 है जब a एक आदिम मूल modulo n है। यदि हम दिखा सकते हैं कि n के लिए a आदिम है, तो हम दिखा सकते हैं कि n अभाज्य है।

संदर्भ

↑ ^1.0 ^1.1 Riesel (1994) pp.2-3
↑ John Selfridge#Selfridge's conjecture about primality testing.
↑ ^3.0 ^3.1 ^3.2 ^3.3 ^3.4 Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·10⁹" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7.
↑ Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "लुकास स्यूडोप्राइम्स" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. MR 0583518.
↑ Robert Baillie; Andrew Fiori; Samuel S. Wagstaff, Jr. (July 2021). "बैली-पीएसडब्ल्यू प्राइमैलिटी टेस्ट को मजबूत करना". Mathematics of Computation. 90 (330): 1931–1955. arXiv:2006.14425. doi:10.1090/mcom/3616. S2CID 220055722.
↑ ^6.0 ^6.1 Adleman, Leonard M.; Huang, Ming-Deh (1992). परिमित क्षेत्र पर आदिमता परीक्षण और एबेलियन किस्में. Lecture notes in mathematics. Vol. 1512. Springer-Verlag. ISBN 3-540-55308-8.
↑ Chau, H. F.; Lo, H.-K. (1995). "क्वांटम फैक्टराइजेशन के माध्यम से प्राइमलिटी टेस्ट". arXiv:quant-ph/9508005.
↑ Pocklington, H. C. (1914). "फ़र्मेट के प्रमेय द्वारा बड़ी संख्याओं की अभाज्य या मिश्रित प्रकृति का निर्धारण". Cambr. Phil. Soc. Proc. 18: 29–30. JFM 45.1250.02.
↑ Weisstein, Eric W. "Pocklington's Theorem". MathWorld.
↑ Gary L. Miller (1976). "रीमैन की परिकल्पना और मौलिकता के लिए परीक्षण". Journal of Computer and System Sciences. 13 (3): 300–317. doi:10.1016/S0022-0000(76)80043-8.
↑ ^11.0 ^11.1 Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "प्राइम्स पी में है" (PDF). Annals of Mathematics. 160 (2): 781–793. doi:10.4007/annals.2004.160.781.
↑ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES P में है" (PDF). Annals of Mathematics. 160 (2): 781–793. doi:10.4007/annals.2004.160.781.
↑ Carl Pomerance & Hendrik W. Lenstra (July 20, 2005). "Primality testing with Gaussian periods" (PDF).
↑ Popovych, Roman (December 30, 2008). "अग्रवाल अनुमान पर एक नोट" (PDF).
↑ E. Allender, M. Saks, and I.E. Shparlinski, A lower bound for primality, J. Comp. Syst. Sci. 62 (2001), pp. 356–366.

स्रोत

Richard Crandall and Carl Pomerance (2005). अभाज्य संख्याएँ: एक कम्प्यूटेशनल परिप्रेक्ष्य (2nd ed.). Springer. ISBN 0-387-25282-7.अध्याय 3: अभाज्य संख्याओं और सम्मिश्रों को पहचानना, पृष्ठ 109-158। अध्याय 4: आदिमता सिद्ध करना, पृ. 159-190। धारा 7.6: अण्डाकार वक्र प्राइमैलिटी प्रूविंग (ईसीपीपी), पीपी 334-340।
Knuth, Donald (1997). "section 4.5.4". कंप्यूटर प्रोग्रामिंग की कला. Vol. 2: Seminumerical Algorithms (Third ed.). Addison–Wesley. pp. 391–396. ISBN 0-201-89684-2.
Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2001). "Section 31.8: Primality testing". एल्गोरिदम का परिचय (Second ed.). MIT Press and McGraw–Hill. pp. 887–896. ISBN 0-262-03293-7.
Papadimitriou, Christos H. (1993). "Section 10.2: Primality". अभिकलनात्मक जटिलता (1st ed.). Addison Wesley. pp. 222–227. ISBN 0-201-53082-1. Zbl 0833.68049.
Riesel, Hans (1994). गुणनखंडन के लिए अभाज्य संख्याएँ और कंप्यूटर विधियाँ. Progress in Mathematics. Vol. 126 (second ed.). Boston, MA: Birkhäuser. ISBN 0-8176-3743-5. Zbl 0821.11001.

बाहरी संबंध

Solovay-Strassen (computacion.cs.cinvestav.mx) at archive.today (archived 2012-12-20) – Implementation of the Solovay-Strassen primality test in Maple
Distinguishing prime numbers from composite numbers, by D.J. Bernstein (cr.yp.to)
The Prime Pages (primes.utm.edu)
Lucas Primality Test with Factored N − 1 (MathPages.com) at the Library of Congress Web Archives (archived 2010-08-06)
PRIMABOINCA is a research project that uses Internet-connected computers to search for a counterexample to some conjectures. The first conjecture (Agrawal's conjecture) was the basis for the formulation of the first deterministic prime test algorithm in polynomial time (AKS algorithm).

[Riesel2-3-1] 1.0 ^1.1 Riesel (1994) pp.2-3

[2] John Selfridge#Selfridge's conjecture about primality testing.

[PSW-3] 3.0 ^3.1 ^3.2 ^3.3 ^3.4 Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·10⁹" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7.

[lpsp-4] Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "लुकास स्यूडोप्राइम्स" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. MR 0583518.

[bpsw2-5] Robert Baillie; Andrew Fiori; Samuel S. Wagstaff, Jr. (July 2021). "बैली-पीएसडब्ल्यू प्राइमैलिटी टेस्ट को मजबूत करना". Mathematics of Computation. 90 (330): 1931–1955. arXiv:2006.14425. doi:10.1090/mcom/3616. S2CID 220055722.

[AH92-6] 6.0 ^6.1 Adleman, Leonard M.; Huang, Ming-Deh (1992). परिमित क्षेत्र पर आदिमता परीक्षण और एबेलियन किस्में. Lecture notes in mathematics. Vol. 1512. Springer-Verlag. ISBN 3-540-55308-8.

[7] Chau, H. F.; Lo, H.-K. (1995). "क्वांटम फैक्टराइजेशन के माध्यम से प्राइमलिटी टेस्ट". arXiv:quant-ph/9508005.

[8] Pocklington, H. C. (1914). "फ़र्मेट के प्रमेय द्वारा बड़ी संख्याओं की अभाज्य या मिश्रित प्रकृति का निर्धारण". Cambr. Phil. Soc. Proc. 18: 29–30. JFM 45.1250.02.

[9] Weisstein, Eric W. "Pocklington's Theorem". MathWorld.

[10] Gary L. Miller (1976). "रीमैन की परिकल्पना और मौलिकता के लिए परीक्षण". Journal of Computer and System Sciences. 13 (3): 300–317. doi:10.1016/S0022-0000(76)80043-8.

[:0-11] 11.0 ^11.1 Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "प्राइम्स पी में है" (PDF). Annals of Mathematics. 160 (2): 781–793. doi:10.4007/annals.2004.160.781.

[AKS-12] Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES P में है" (PDF). Annals of Mathematics. 160 (2): 781–793. doi:10.4007/annals.2004.160.781.

[13] Carl Pomerance & Hendrik W. Lenstra (July 20, 2005). "Primality testing with Gaussian periods" (PDF).

[14] Popovych, Roman (December 30, 2008). "अग्रवाल अनुमान पर एक नोट" (PDF).

[15] E. Allender, M. Saks, and I.E. Shparlinski, A lower bound for primality, J. Comp. Syst. Sci. 62 (2001), pp. 356–366.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

v t e संख्या-सिद्धांत एल्गोरिथ्म
प्राइमैलिटी टेस्ट	AKS अप्रैल BAILLIE -PSW अण्डाकार वक्र पॉकलिंगटन Fermat लुकास लुकास -लेहमेर लुकास -लेहमेर -रेज़ल ' प्रोथ का प्रमेय पेपिन का द्विघात फ्रोबेनियस सोलोवे -स्ट्रासेन मिलर -रबिन
प्राइम-जनरेटिंग	एटकिन की छलनी एरातोस्टेनेस की छलनी प्रिचर्ड की छलनी सुंदरम की छलनी पहिया कारक
पूर्णांक कारक	निरंतर अंश कारक। निरंतर अंश (CFRAC) डिक्सन Lenstra अण्डाकार-वक्र कारक Euler's पोलार्ड्स आरएचओ P - 1 पी + 1 द्विघात छलनी (क्यूएस) सामान्य संख्या क्षेत्र छलनी (GNFS) विशेष संख्या क्षेत्र छलनी (SNFS) तर्कसंगत छलनी फर्माट शैंक्स स्क्वायर फॉर्म ट्रायल डिवीजन शोर
गुणा	प्राचीन मिस्र लंबा करत्सुबा टूम - कुक Schönhage - Strassen Für's
Euclidean डिवीजन	बाइनरी चंकिंग फूरियर Goldschmidt न्यूटन-रफसन लंबा छोटा SRT
असतत लघुगणक	बेबी-स्टेप विशाल-चरण पोलार्ड रो पोलार्ड कंगारू Pohlig -Hellman इंडेक्स कैलकुलस फ़ंक्शन फ़ील्ड छलनी
महत्तम सामान्य भाजक	बाइनरी Euclidean विस्तारित यूक्लिडियन लेहमर
मॉड्यूलर वर्गमूल	Cipolla पॉकलिंगटन तनेली -शंक Berlekamp कुनरथ
अन्य एल्गोरिदम	चक्रवाला कॉर्नचिया वर्ग द्वारा घातक पूर्णांक वर्गमूल पूर्णांक संबंध मॉड्यूलर घातांक मोंटगोमरी में कमी शूफ़ ट्रेचेनबर्ग सिस्टम
इटैलिक इंगित करता है कि एल्गोरिथ्म विशेष रूपों की संख्या के लिए है