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

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

सरल तरीके

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

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

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

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

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

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

उदाहरण कोड

अजगर

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

 के लिए बहुत तेज़ हैं
गणित आयात से isqrt
def is_prime (n: int) -> बूल:
    अगर एन <= 3:
        रिटर्न एन> 1
    अगर एन% 2 == 0 या एन% 3 == 0:
        विवरण झूठा है
    सीमा = isqrt (एन)
    मैं सीमा में (5, सीमा + 1, 6) के लिए:
        अगर n% i == 0 या n% (i+2) == 0:
            विवरण झूठा है
    सच लौटाओ
</वाक्यविन्यास हाइलाइट>

==== सी, सी ++, सी # और डी ====
उपरोक्त के समान अनुकूलन का उपयोग करते हुए भाषाओं के C (प्रोग्रामिंग भाषा) परिवार में निम्नलिखित एक प्राथमिक परीक्षण है।
<वाक्यविन्यास प्रकाश लैंग = सी #>
बूल इसप्राइम (इंट एन)
{
    अगर (एन == 2 || एन == 3)
        वापसी सच;

    अगर (एन <= 1 || एन% 2 == 0 || एन% 3 == 0)
        विवरण झूठा है;

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

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

==== जावा ====
उपरोक्त के समान अनुकूलन का उपयोग करते हुए निम्नलिखित [[जावा (प्रोग्रामिंग भाषा)]] में एक प्राथमिक परीक्षण है।<syntaxhighlight lang="java">
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;
}

आर

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

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
}

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

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

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

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

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

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

च (एक्स)_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).