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

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

सरल विधियाँ

सरलतम प्रधानता परीक्षण ट्रायल विभाजन है: एक इनपुट संख्या दी गई है, 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 के लिए कम से कम आधा a{{'}एन का पता लगाएं's समग्रता, इसलिए k दोहराव त्रुटि संभावना को अधिकतम 2 तक कम कर देता है^-k, जिसे k बढ़ाकर मनमाने ढंग से छोटा किया जा सकता है।

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

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

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

फर्मेट प्रधानता परीक्षण

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

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

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

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

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

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

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

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

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

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

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

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

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

बैली-पीएसडब्ल्यू प्रीमैलिटी टेस्ट

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

अन्य परीक्षण

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

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

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

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

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

जटिलता

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

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

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

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

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

संख्या-सैद्धांतिक तरीके

कोई संख्या अभाज्य है या नहीं, इसके परीक्षण के लिए कुछ संख्या-सैद्धांतिक विधियाँ मौजूद हैं, जैसे कि लुकास प्रधानता परीक्षण और प्रोथ की प्रमेय | प्रोथ की परीक्षा। इन परीक्षणों में आम तौर पर 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).