प्रधानता परीक्षण

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

सरल तरीके

सबसे सरल प्रारंभिक परीक्षण ट्रायल विभाजन है: एक इनपुट संख्या दी गई है, n, जांचें कि क्या यह 2 और √n के बीच किसी भी अभाज्य संख्या से समान रूप से विभाज्य है (यानी कि विभाजन कोई शेष नहीं छोड़ता है)। यदि ऐसा है, तो n भाज्य है, नहीं तो अभाज्य है। वास्तव में, किसी भी भाजक $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 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2

ध्यान दें कि 10 × 10 के बाद के गुणनफल केवल दोहराए गए नंबर हैं जो पहले के गुणनफलो, कम्यूटेड में दिखाई देते थे। उदाहरण के लिए, 5 × 20 और 20 × 5 के विपरीत क्रम में समान संख्याएँ हैं। यह सभी n के लिए सही है: n के सभी अद्वितीय विभाजक √n से कम या उसके बराबर संख्याएँ हैं, इसलिए हमें उससे आगे की खोज करने की आवश्यकता नहीं है। (इस उदाहरण में, √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 से बड़ी सभी अभाज्य संख्याएँ 6k ± 1 के रूप की होती हैं, जहाँ k 0 से बड़ा कोई पूर्णांक है। ऐसा इसलिए है क्योंकि सभी पूर्णांकों को (6k + i) के रूप में व्यक्त किया जा सकता है, जहाँ i = -1, 0, 1, 2, 3, या 4 है। ध्यान दें कि 2 (6k + 0), (6k + 2), और (6k + 4) को विभाजित करता है और 3 (6k + 3) को विभाजित करता है। इसलिए, एक और भी सक्षम विधि यह जांचना है कि क्या n 2 या 3 से विभाज्य है, फिर $\scriptstyle 6k\ \pm \ 1\leq {\sqrt {n}}$ के रूप की सभी संख्याओं की जांच करना है। यह √n तक की सभी संख्याओं के परीक्षण से 3 गुना तेज है।

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

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

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

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

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

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

उदाहरण कोड

पायथन

निम्नलिखित पहले उल्लेखित सरल 6k ± 1 इष्टतमीकरण का उपयोग करते हुए पायथन में एक सरल प्रारंभिक परीक्षण है। नीचे वर्णित अधिक परिष्कृत विधियाँ बड़े n के लिए बहुत तेज़ हैं।

 from math import isqrt
def is_prime(n: int) -> bool:
    if n <= 3:
        return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    limit = isqrt(n)
    for i in range(5, limit+1, 6):
        if n % i == 0 or n % (i+2) == 0:
            return False
    return True

सी, सी++, सी# & डी 
उपरोक्त के समान इष्टतमीकरण का उपयोग करते हुए निम्नलिखित भाषाओं के C परिवार में एक प्राथमिक परीक्षण है।

bool IsPrime(int n)
{
    if (n == 2 || n == 3)
        return true;

    if (n <= 1 || n % 2 == 0 || n % 3 == 0)
        return false;

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

    return true;
}

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


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
}

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

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

• 2^p−1 ≡ 1 (mod p),
• f_p+1 ≡ 0 (mod p),

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

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

• 2^p−1 ≡ 1 (mod p),
• f(1)_p+1 ≡ 0 (mod p),

f(x)k x पर k-वां फिबोनैकी बहुपद है।

सेल्फ्रिज, कार्ल पोमेरेन्स और सैमुअल वैगस्टाफ मिलकर एक गणित्र उदाहरण के लिए $620 की उपस्थिति करते हैं। समस्या अभी भी 11 सितंबर, 2015 तक खुली है।

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

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

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

1. यादृच्छिकता से (रैन्डम्ली) एक संख्या चुनें।
2. a और दी गई संख्या n को सम्मिलित करते हुए समिका (चयनित परीक्षण के संगत) की जाँच करें। यदि समिका सही सिद्ध नहीं होती है, तो n एक संयुक्त (भाज्य) संख्या है और a संयुक्तता का प्रमाण है, और परीक्षण बंद हो जाता है।
3. आवश्यक सटीकता तक पहुंचने तक पहले चरण पर वापस जाएं।

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

फर्मेट प्रारंभिक परीक्षण

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

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

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

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

भले ही 341 = 11·31 भाज्य है। वास्तव में, 341 का सबसे छोटा स्यूडोप्राइम आधार 2 है (चित्र 1 देखें ).

केवल 21853 का स्यूडोप्राइम्स आधार 2 है जो 2.5×10¹⁰ हैं | (पृष्ठ 1005 देखें ) इसका अर्थ है कि, 2.5×10¹⁰ तक n के लिए, यदि 2ⁿ⁻¹ (सापेक्ष n) 1 के बराबर है, तो n अभाज्य है, जब तक कि n इन 21853 स्यूडोप्राइम्स में से एक न हो जाये।

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

मिलर-राबिन और सोलोवे-स्ट्रैसन प्रारंभिक परीक्षण

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

मिलर-राबिन प्रारंभिक परीक्षण निम्नानुसार काम करता है: एक पूर्णांक 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 अभाज्य हो भी सकता है और नहीं भी सकता है । मिलर-राबिन परीक्षण एक महत्वपूर्ण संभाव्य परीक्षण है| (देखें PSWपृष्ठ 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 अभाज्य हो भी सकता है और नहीं भी सकता है । सोलोवे-स्ट्रैसन परीक्षण एक यूलर संभाव्य परीक्षण है| (देखें PSWपृष्ठ 1003)

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

फ्रोबेनियस प्रारंभिक परीक्षण

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

फ्रोबेनियस परीक्षण लुकास संभाव्य प्रधान परीक्षण का एक सामान्यीकरण है।

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

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

अन्य परीक्षण

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

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

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

20 वीं शताब्दी की शुरुआत के करीब, यह दिखाया गया था कि फर्मेट के छोटे प्रमेय का एक परिणाम प्रारंभिकता के परीक्षण के लिए उपयोग किया जा सकता है। इसका परिणाम पॉकलिंगटन प्रारंभिक परीक्षण में हुआ है। हालाँकि, इस परीक्षण के लिए n − 1 के आंशिक गुणन की आवश्यकता होती है, सबसे खराब स्थिति में चलने का समय अभी भी काफी धीमा था। सरल विधियों की तुलना में पहला नियतात्मक प्रारंभिक परीक्षण साइक्लोटॉमी परीक्षण था; इसका रनटाइम O((log n)^{c log log log n}) सिद्ध हो सकता है, जहां n प्रारंभिकता के लिए परीक्षण की जाने वाली संख्या है और c, n से स्वतंत्र है। और भी कई सुधार किए गए, लेकिन कोई भी बहुपद रनिंग टाइम सिद्ध नहीं हो सका। (ध्यान दें कि चलने का समय इनपुट के आकार के संदर्भ में मापा जाता है, जो इस स्थिति में ~ log n है, जो संख्या n का निरूपण करने के लिए आवश्यक बिट्स की संख्या है।) यदि विश्लेषणात्मक संख्या सिद्धांत पर कुछ अनुमानित कथन सही हैं, तो दीर्घवृत्तीय वक्र प्रारंभिक परीक्षण O((log n)6) में चलने के लिए सिद्ध किया जा सकता है। इसी तरह, सामान्यीकृत रीमैन परिकल्पना के तहत, नियतात्मक मिलर-राबिन का परीक्षण, जो संभाव्य मिलर-राबिन परीक्षण का आधार बनाता है, को Õ((log n)⁴) में रन के लिए सिद्ध किया जा सकता है| अभ्यास में, यह एल्गोरिथम संख्याओं के आकार के लिए अन्य दो की तुलना में मध्यम है, जिनको बिल्कुल भी पार किया जा सकता है। क्योंकि इन दो विधियों का कार्यान्वयन कठिन है और प्रोग्रामन त्रुटियों का संकट उत्पन्न करता है, निष्क्रिय लेकिन सरल परीक्षणों को अक्सर प्राथमिकता दी जाती है।

2002 में, मनिंद्र अग्रवाल, नीरज कयाल और नितिन सक्सेना द्वारा पहली सिद्ध बिना शर्त नियतात्मक बहुपद समय परीक्षण का आविष्कार किया गया था। AKS प्रारंभिक परीक्षण Õ((log n)¹²) में रन है (उनके पेपर के प्रकाशित संशोधन में Õ((log n)^7.5) में सुधार हुआ है),जिसे आगे Õ((log n)⁶) तक घटाया जा सकता है ) यदि सोफी जर्मेन अनुमान सत्य है। इसके बाद में, लेनस्ट्रा और पोमेरेन्स ने परीक्षण का एक संस्करण प्रस्तुत किया जो बिना शर्त Õ((log n)⁶) समय में चलता है।

अग्रवाल, कयाल और सक्सेना अपने एल्गोरिदम का एक प्रकार प्रस्तावित करते हैं अग्रवाल का अनुमानित कथन सत्य होने पर Õ((log n)³) में चलेगा; हालाँकि, हेंड्रिक लेनस्ट्रा और कार्ल पोमेरेन्स द्वारा एक अनुमानी तर्क से पता चलता है कि यह शायद गलत है।अग्रवाल के अनुमानित कथन का एक संशोधित संस्करण, अग्रवाल-पोपोविक अनुमान, अभी भी सच हो सकता है।

जटिलता

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

1975 में, वॉन प्रैट ने दिखाया कि बहुपद समय में जांचने योग्य प्रारंभिकता के लिए एक प्रमाण पत्र उपस्थित था, और इस प्रकार PRIMES NP और ${\mathsf {NP\cap coNP}}$ में था | विवरण के लिए प्रारंभिक प्रमाण पत्र देखें।

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

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

अभ्यास में इसकी सुवाह्यता के कारण, बहुपद-समय एल्गोरिदम रीमैन परिकल्पना मानते हैं, और इसी तरह के अन्य प्रमाण, यह लंबे समय से संदिग्ध था लेकिन सिद्ध नहीं हुआ कि बहुपद समय में प्राथमिकता को हल किया जा सकता है। AKS प्रीमैलिटी टेस्ट के अस्तित्व ने आखिरकार इस लंबे समय से चले आ रहे सवाल को सुलझा दिया और PRIMES को P में रखा दिया। हालाँकि, PRIMES को P-पूर्ण नहीं माना जाता है, और यह ज्ञात नहीं है कि यह P के अंदर स्थित वर्गों जैसे NC या L में स्थित है या नहीं है। यह ज्ञात है कि PRIMES AC⁰ में नहीं है|^।

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

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

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

स्रोत

• 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).