जैकोबी प्रतीक: Difference between revisions

Latest revision as of 16:19, 25 July 2023

k n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	1
3	0	1	−1
5	0	1	−1	−1	1
7	0	1	1	−1	1	−1	−1
9	0	1	1	0	1	1	0	1	1
11	0	1	−1	1	1	1	−1	−1	−1	1	−1
13	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1
15	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1
17	−0	−1	1	−1	−1	−1	−1	−1	1	−1	−1	−1	−1	1	−1	1	1

जैकोबी प्रतीक (k/n) विभिन्न k (शीर्ष के साथ) और n (बाईं ओर) के लिए। केवल 0 ≤ k < n दिखाया गया है, क्योंकि नियम (2) के कारण किसी भी अन्य k को मॉड्यूलो n से कम किया जा सकता है। द्विघात अवशेषों को पीले रंग में हाइलाइट किया गया है - ध्यान दें कि −1 के जैकोबी प्रतीक के साथ कोई भी प्रविष्टि द्विघात अवशेष नहीं है और यदि k एक द्विघात अवशेष सापेक्ष a सहअभाज्य n है, तब (k/n) = 1, किन्तु सभी प्रविष्टियाँ 1 के जैकोबी प्रतीक के साथ नहीं (देखें)। n = 9 और n = 15 पंक्तियाँ) द्विघात अवशेष हैं। इस प्रकार यह भी ध्यान दें कि जब n या k एक वर्ग होता है, तब सभी मान अऋणात्मक होते हैं।

'जैकोबी प्रतीक' लीजेंड्रे प्रतीक का सामान्यीकरण है। वर्ष 1837 में जैकोबी द्वारा प्रस्तुत,^[1] यह मॉड्यूलर अंकगणित और संख्या सिद्धांत की अन्य शाखाओं में सैद्धांतिक रुचि रखता है, किन्तु इसका मुख्य उपयोग कम्प्यूटेशनल संख्या सिद्धांत, विशेष रूप से प्रारंभिक परीक्षण और पूर्णांक गुणनखंडन में है; इस प्रकार यह बदले में क्रिप्टोग्राफी में महत्वपूर्ण हैं।

परिभाषा

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

\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{\alpha _{1}}\left({\frac {a}{p_{2}}}\right)^{\alpha _{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{\alpha _{k}},

कहाँ

n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}

n का अभाज्य गुणनखंडन है।

इस प्रकार लीजेंड्रे प्रतीक (a/p) को सभी पूर्णांकों a और सभी विषम अभाज्य संख्याओं p के लिए परिभाषित किया गया है

\left({\frac {a}{p}}\right)=\left\{{\begin{array}{rl}0&{\text{if }}a\equiv 0{\pmod {p}},\\1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x\colon \;a\equiv x^{2}{\pmod {p}},\\-1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and there is no such }}x.\end{array}}\right.

खाली उत्पाद के लिए सामान्य परिपाटी का पालन करते हुए, (a/1)=1.

जब निचला तर्क एक विषम अभाज्य होता है, तब जैकोबी प्रतीक लीजेंड्रे प्रतीक के सामान्तर होता है।

मूल्यों की तालिका

निम्नलिखित जैकोबी प्रतीक के मूल्यों की एक तालिका है (k/n) n ≤ 59, k ≤ 30, n विषम के साथ।

k n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
1	−1	1	1	−1	1	1	1	1	−1	1	1	1	1	1	1	−1	1	1	1	1	1	1	1	1	−1	1	1	1	1	1
3	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
5	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0
7	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1
9	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0
11	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1
13	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1
15	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0
17	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	1	0	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1
19	1	−1	−1	1	1	1	1	−1	1	−1	1	−1	−1	−1	−1	1	1	−1	0	1	−1	−1	1	1	1	1	−1	1	−1	1
21	1	−1	0	1	1	0	0	−1	0	−1	−1	0	−1	0	0	1	1	0	−1	1	0	1	−1	0	1	1	0	0	−1	0
23	1	1	1	1	−1	1	−1	1	1	−1	−1	1	1	−1	−1	1	−1	1	−1	−1	−1	−1	0	1	1	1	1	−1	1	−1
25	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0
27	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
29	1	−1	−1	1	1	1	1	−1	1	−1	−1	−1	1	−1	−1	1	−1	−1	−1	1	−1	1	1	1	1	−1	−1	1	0	1
31	1	1	−1	1	1	−1	1	1	1	1	−1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	1	−1	−1	1	−1	−1
33	1	1	0	1	−1	0	−1	1	0	−1	0	0	−1	−1	0	1	1	0	−1	−1	0	0	−1	0	1	−1	0	−1	1	0
35	1	−1	1	1	0	−1	0	−1	1	0	1	1	1	0	0	1	1	−1	−1	0	0	−1	−1	−1	0	−1	1	0	1	0
37	1	−1	1	1	−1	−1	1	−1	1	1	1	1	−1	−1	−1	1	−1	−1	−1	−1	1	−1	−1	−1	1	1	1	1	−1	1
39	1	1	0	1	1	0	−1	1	0	1	1	0	0	−1	0	1	−1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0
41	1	1	−1	1	1	−1	−1	1	1	1	−1	−1	−1	−1	−1	1	−1	1	−1	1	1	−1	1	−1	1	−1	−1	−1	−1	−1
43	1	−1	−1	1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	1	−1	−1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1
45	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0
47	1	1	1	1	−1	1	1	1	1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	1	−1	−1	1	1	−1	1	1	−1	−1
49	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1
51	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	1	0	1	0	0	1	1	0	−1	1	0	1	−1	0	−1	1	0
53	1	−1	−1	1	−1	1	1	−1	1	1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1	−1	1	1	−1	−1	1	1	−1
55	1	1	−1	1	0	−1	1	1	1	0	0	−1	1	1	0	1	1	1	−1	0	−1	0	−1	−1	0	1	−1	1	−1	0
57	1	1	0	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	−1	0	0	−1	0	−1	−1	0	1	−1	0	1	1	0
59	1	−1	1	1	1	−1	1	−1	1	−1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	−1	−1	1	1	1	1	1	−1

गुण

निम्नलिखित तथ्य, यहां तक कि पारस्परिकता नियम, जैकोबी प्रतीक की परिभाषा और लीजेंड्रे प्रतीक के संबंधित गुणों से सामान्यतः निकाले गए हैं।^[2]

जैकोबी प्रतीक को केवल तभी परिभाषित किया जाता है जब ऊपरी तर्क ("अंश") एक पूर्णांक होता है और निचला तर्क ("हर") एक धनात्मक विषम पूर्णांक होता है।

1. यदि n (एक विषम) अभाज्य है, तब जैकोबी प्रतीक (an) संबंधित लीजेंड्रे प्रतीक के सामान्तर है (और उसी के समान लिखा गया है)।

2. तथापि a ≡ b (mod n), तब

\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)=\left({\frac {a\pm m\cdot n}{n}}\right)

3.

\left({\frac {a}{n}}\right)={\begin{cases}0&{\text{if }}\gcd(a,n)\neq 1,\\\pm 1&{\text{if }}\gcd(a,n)=1.\end{cases}}

यदि शीर्ष या निचला तर्क तय हो गया है, तब जैकोबी प्रतीक शेष तर्क में पूरी तरह से गुणक कार्य है:

4.

\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right),\quad {\text{so }}\left({\frac {a^{2}}{n}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.

5.

\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right),\quad {\text{so }}\left({\frac {a}{n^{2}}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.

द्विघात पारस्परिकता का नियम: यदि m और n विषम धनात्मक सहअभाज्य पूर्णांक हैं, तब

6.

\left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{{\tfrac {m-1}{2}}\cdot {\tfrac {n-1}{2}}}={\begin{cases}1&{\text{if }}n\equiv 1{\pmod {4}}{\text{ or }}m\equiv 1{\pmod {4}},\\-1&{\text{if }}n\equiv m\equiv 3{\pmod {4}}\end{cases}}

और इसके पूरक

7.

\left({\frac {-1}{n}}\right)=(-1)^{\tfrac {n-1}{2}}={\begin{cases}1&{\text{if }}n\equiv 1{\pmod {4}},\\-1&{\text{if }}n\equiv 3{\pmod {4}},\end{cases}}

,

और $\left({\frac {1}{n}}\right)=\left({\frac {n}{1}}\right)=1$

8.

\left({\frac {2}{n}}\right)=(-1)^{\tfrac {n^{2}-1}{8}}={\begin{cases}1&{\text{if }}n\equiv 1,7{\pmod {8}},\\-1&{\text{if }}n\equiv 3,5{\pmod {8}}.\end{cases}}

गुण 4 और 8 का संयोजन देता है:

9.

\left({\frac {2a}{n}}\right)=\left({\frac {2}{n}}\right)\left({\frac {a}{n}}\right)={\begin{cases}\left({\frac {a}{n}}\right)&{\text{if }}n\equiv 1,7{\pmod {8}},\\{-\left({\frac {a}{n}}\right)}&{\text{if }}n\equiv 3,5{\pmod {8}}.\end{cases}}

लीजेंड्रे प्रतीक की तरह:

तथापि (a/n) = −1 तब a एक द्विघात गैरअवशेष मॉड्यूलो n है।

यदि a एक द्विघात अवशेष मॉड्यूलो n है और सबसे बड़ा सामान्य भाजक (a,n) = 1 है, तब (a/n)=1.

किन्तु, लीजेंड्रे प्रतीक के विपरीत:

तथापि (an) = 1 तब a द्विघात अवशेष मॉड्यूलो n हो भी सकता है और नहीं भी।

ऐसा इसलिए है क्योंकि a को एक द्विघात अवशेष मॉड्यूल n होने के लिए, n के प्रत्येक अभाज्य कारक को एक द्विघात अवशेष मॉड्यूलो होना चाहिए। चूँकि, जैकोबी प्रतीक एक के सामान्तर है यदि, उदाहरण के लिए, ए एक गैर-अवशेष मॉड्यूलो है जो एन के दो प्रमुख कारक हैं।

चूँकि जैकोबी प्रतीक की व्याख्या वर्गों और गैर-वर्गों के संदर्भ में समान रूप से नहीं की जा सकती है, इसे ज़ोलोटारेव के लेम्मा द्वारा क्रमपरिवर्तन के संकेत के रूप में समान रूप से व्याख्या किया जा सकता है।

इस प्रकार जैकोबी प्रतीक (a/n) मापांक n के लिए एक डिरिचलेट वर्ण है।

जैकोबी प्रतीक की गणना

उपरोक्त सूत्र एक कुशल की ओर ले जाते हैं O(log a log b)^[3] जैकोबी प्रतीक की गणना के लिए एल्गोरिदम, दो संख्याओं की जीसीडी खोजने के लिए यूक्लिडियन एल्गोरिथ्म के अनुरूप। (नियम 2 के आलोक में यह आश्चर्यजनक नहीं होना चाहिए।)

नियम 2 का उपयोग करके अंश मॉड्यूल को हर से कम करें।
नियम 9 का उपयोग करके कोई भी सम अंश निकालें।
यदि अंश 1 है, तब नियम 3 और 4 1 का परिणाम देते हैं। यदि अंश और हर सहअभाज्य नहीं हैं, तब नियम 3 0 का परिणाम देता है।
अन्यथा, अंश और हर अभी विषम धनात्मक सहअभाज्य पूर्णांक हैं, इसलिए हम नियम 6 का उपयोग करके प्रतीक को पलट सकते हैं, फिर चरण 1 पर लौट सकते हैं।

लुआ (प्रोग्रामिंग भाषा) में कार्यान्वयन

function jacobi(n, k)
  assert(k > 0 and k % 2 == 1)
  n = n % k
  t = 1
  while n ~= 0 do
    while n % 2 == 0 do
      n = n / 2
      r = k % 8
      if r == 3 or r == 5 then
        t = -t
      end
    end
    n, k = k, n
    if n % 4 == 3 and k % 4 == 3 then
      t = -t
    end
    n = n % k
  end
  if k == 1 then
    return t
  else
    return 0
  end
end

C++ में कार्यान्वयन

<सिंटैक्सहाइलाइट लैंग= सी++ >

// a/n को (a,n) के रूप में दर्शाया गया है इंट जैकोबी(इंट ए, इंट एन) {

   ज़ोर (n > 0 && n%2 == 1);
   //स्टेप 1
   ए = ए % एन;
   पूर्णांक टी = 1;
   पूर्णांक आर;
   //चरण 3
   जबकि (ए != 0) {
       //चरण दो
       जबकि (a % 2 == 0) {
           ए /= 2;
           आर = एन % 8;
           यदि (आर == 3 || आर == 5) {
               टी = -टी;
           }
       }
       //चरण 4
       आर = एन;
       एन = ए;
       ए = आर;
       यदि (a % 4 == 3 && n % 4 == 3) {
           टी = -टी;
       }
       ए = ए % एन;
   }
   यदि (एन == 1) {
       वापसी टी;
   }
   अन्य {
       वापसी 0;
   }

}

</सिंटैक्सहाइलाइट>

गणना का उदाहरण

लीजेंड्रे प्रतीक (a/p) केवल विषम अभाज्य संख्याओं p के लिए परिभाषित है। इस प्रकार यह जैकोबी प्रतीक के समान नियमों का पालन करता है (अर्थात, पारस्परिकता और इसके लिए पूरक सूत्र) (−1/p) और (2/p) और अंश की गुणात्मकता।)

समस्या: यह देखते हुए कि 9907 अभाज्य है, गणना करें (1001/9907).

लेजेंड्रे प्रतीक का उपयोग करना

{\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {7}{9907}}\right)\left({\frac {11}{9907}}\right)\left({\frac {13}{9907}}\right).\\\left({\frac {7}{9907}}\right)&=-\left({\frac {9907}{7}}\right)=-\left({\frac {2}{7}}\right)=-1.\\\left({\frac {11}{9907}}\right)&=-\left({\frac {9907}{11}}\right)=-\left({\frac {7}{11}}\right)=\left({\frac {11}{7}}\right)=\left({\frac {4}{7}}\right)=1.\\\left({\frac {13}{9907}}\right)&=\left({\frac {9907}{13}}\right)=\left({\frac {1}{13}}\right)=1.\\\left({\frac {1001}{9907}}\right)&=-1.\end{aligned}}

जैकोबी प्रतीक का उपयोग करना

{\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {9907}{1001}}\right)=\left({\frac {898}{1001}}\right)=\left({\frac {2}{1001}}\right)\left({\frac {449}{1001}}\right)=\left({\frac {449}{1001}}\right)\\&=\left({\frac {1001}{449}}\right)=\left({\frac {103}{449}}\right)=\left({\frac {449}{103}}\right)=\left({\frac {37}{103}}\right)=\left({\frac {103}{37}}\right)\\&=\left({\frac {29}{37}}\right)=\left({\frac {37}{29}}\right)=\left({\frac {8}{29}}\right)=\left({\frac {2}{29}}\right)^{3}=-1.\end{aligned}}

दोनों गणनाओं के मध्य अंतर यह है कि जब लीजेंड्रे प्रतीक का उपयोग किया जाता है तब प्रतीक को फ़्लिप करने से पहले अंश को अभाज्य शक्तियों में विभाजित करना पड़ता है। इस प्रकार इससे जैकोबी प्रतीक का उपयोग करने की तुलना में लीजेंड्रे प्रतीक का उपयोग करने वाली गणना अधिक धीमी हो जाती है, क्योंकि पूर्णांकों के गुणनखंडन के लिए कोई ज्ञात बहुपद-समय एल्गोरिदम नहीं है।^[4] इस प्रकार वास्तव में, यही कारण है कि जैकोबी ने प्रतीक प्रस्तुत किया गया हैं।

प्राथमिकता परीक्षण

एक और तरीके से जैकोबी और लेजेंड्रे प्रतीक भिन्न हैं। इस प्रकार यदि यूलर के मानदंड सूत्र का उपयोग समग्र संख्या मॉड्यूलो में किया जाता है, तब परिणाम जैकोबी प्रतीक का मान हो भी सकता है और नहीं भी, और वास्तव में -1 या 1 भी नहीं हो सकता है। उदाहरण के लिए,

{\begin{aligned}\left({\frac {19}{45}}\right)&=1&&{\text{ and }}&19^{\frac {45-1}{2}}&\equiv 1{\pmod {45}}.\\\left({\frac {8}{21}}\right)&=-1&&{\text{ but }}&8^{\frac {21-1}{2}}&\equiv 1{\pmod {21}}.\\\left({\frac {5}{21}}\right)&=1&&{\text{ but }}&5^{\frac {21-1}{2}}&\equiv 16{\pmod {21}}.\end{aligned}}

इसलिए यदि यह अज्ञात है कि कोई संख्या n अभाज्य है या भाज्य है, तब हम एक यादृच्छिक संख्या a चुन सकते हैं, जैकोबी प्रतीक की गणना कर सकते हैं (a/n) और इसकी तुलना यूलर के सूत्र से करें; यदि वह मॉड्यूलो एन में भिन्न हैं, तब एन समग्र है; यदि उनके पास a के अनेक भिन्न-भिन्न मानों के लिए समान अवशेष मॉड्यूल n है, तब n "संभवतः अभाज्य" है।

यह संभाव्य सोलोवे-स्ट्रैसेन प्राइमलिटी परीक्षण और बैली-पीएसडब्ल्यू प्राइमलिटी टेस्ट और मिलर-राबिन प्राइमलिटी टेस्ट जैसे परिशोधन का आधार है।

इस प्रकार अप्रत्यक्ष उपयोग के रूप में, इसे लुकास-लेहमर प्राइमैलिटी टेस्ट के निष्पादन के समय एक त्रुटि पता लगाने की दिनचर्या के रूप में उपयोग करना संभव है, इस प्रकार जिसे आधुनिक कंप्यूटर हार्डवेयर पर भी मेर्सन संख्याओं को संसाधित करते समय पूरा होने में अनेक सप्ताह लग सकते हैं। ${\begin{aligned}2^{82,589,933}-1\end{aligned}}$ (दिसंबर 2018 तक सबसे बड़ा ज्ञात मेर्सन प्राइम)। नाममात्र के स्थितियोंमें, जैकोबी प्रतीक:

${\begin{aligned}\left({\frac {s_{i}-2}{M_{p}}}\right)&=-1&i\neq 0\end{aligned}}$

यह अंतिम अवशेष के लिए भी प्रयुक्त होता है ${\begin{aligned}s_{p-2}\end{aligned}}$ और इसलिए इसे संभावित वैधता के सत्यापन के रूप में उपयोग किया जा सकता है। चूँकि, यदि हार्डवेयर में कोई त्रुटि होती है, तब 50% संभावना है कि परिणाम इसके अतिरिक्त 0 या 1 हो जाएगा और पश्चात् की शर्तों के साथ नहीं बदलेगा। ${\begin{aligned}s\end{aligned}}$ (जब तक कि कोई अन्य त्रुटि न हो और इसे वापस -1 में न बदल दे)।

यह भी देखें

क्रोनकर प्रतीक, सभी पूर्णांकों के लिए जैकोबी प्रतीक का सामान्यीकरण।
शक्ति अवशेष प्रतीक, उच्च शक्तियों अवशेषों के लिए जैकोबी प्रतीक का एक सामान्यीकरण।

↑ Jacobi, C. G. J. (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie". Bericht Ak. Wiss. Berlin: 127–136.
↑ Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10
↑ Cohen, pp. 29–31
↑ The number field sieve, the fastest known algorithm, requires
$O\left(e^{(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}{\big (}C+o(1){\big )}}\right)$
operations to factor n. See Cohen, p. 495

संदर्भ

कोहेन, हेनरी (1993). कम्प्यूटेशनल बीजगणितीय संख्या सिद्धांत में एक पाठ्यक्रम. बर्लिन: स्प्रिंगर. ISBN 3-540-55640-0.
आयरलैंड, केनेथ; रोजेन, माइकल (1990). आधुनिक संख्या सिद्धांत का एक शास्त्रीय परिचय (दूसरा संस्करण). न्यूयॉर्क: स्प्रिंगर. ISBN 0-387-97329-X.
लेमरमेयर, फ्रांज (2000). पारस्परिकता कानून: यूलर से ईसेनस्टीन तक. बर्लिन: स्प्रिंगर. ISBN 3-540-66957-4.
शालित, जेफरी (दिसंबर 1990). "जैकोबी प्रतीक की गणना के लिए तीन एल्गोरिदम के सबसे खराब मामले पर". प्रतीकात्मक संगणना का जर्नल. 10 (6): 593–61. doi:10.1016/S0747-7171(08)80160-5. कंप्यूटर विज्ञान तकनीकी रिपोर्ट PCS-TR89-140. {{cite journal}}: Check date values in: |date= (help); Invalid |doi-access=मुक्त (help)
वले, ब्रिजित; लेमी, चार्ली (अक्टूबर 1998). जैकोबी प्रतीक की गणना के लिए तीन एल्गोरिदम का औसत-केस विश्लेषण (Technical report). CiteSeerX 10.1.1.32.3425. {{cite tech report}}: Check date values in: |date= (help)
Eikenberry, Shawna Meyer; Sorenson, Jonathan P. (October 1998). "Efficient Algorithms for Computing the Jacobi Symbol" (PDF). Journal of Symbolic Computation. 26 (4): 509–523. CiteSeerX 10.1.1.44.2423. doi:10.1006/jsco.1998.0226.

बाहरी संबंध

Calculate Jacobi symbol shows the steps of the calculation.

[1] Jacobi, C. G. J. (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie". Bericht Ak. Wiss. Berlin: 127–136.

[2] Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10

[3] Cohen, pp. 29–31

[4] The number field sieve, the fastest known algorithm, requires
$O\left(e^{(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}{\big (}C+o(1){\big )}}\right)$
operations to factor n. See Cohen, p. 495

[1]

[2]

[3]

[4]

@@ Line 58: / Line 58: @@
 जब निचला तर्क एक विषम अभाज्य होता है, तब जैकोबी प्रतीक लीजेंड्रे प्रतीक के सामान्तर होता है।
-==मूल्यों की तालिका==
+=='''मूल्यों की तालिका'''==
 निम्नलिखित जैकोबी प्रतीक के मूल्यों की एक तालिका है {{big|(}}{{sfrac|''k''|''n''}}{{big|)}} n ≤ 59, k ≤ 30, n विषम के साथ।
@@ Line 1,055: / Line 1,055: @@
 |style="background:#ccffff"|−1
 |}
-==गुण==
+=='''गुण'''==
 निम्नलिखित तथ्य, यहां तक कि पारस्परिकता नियम, जैकोबी प्रतीक की परिभाषा और लीजेंड्रे प्रतीक के संबंधित गुणों से सामान्यतः निकाले गए हैं।<ref>Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10</ref>
@@ Line 1,121: / Line 1,121: @@
 इस प्रकार जैकोबी प्रतीक {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} मापांक n के लिए एक डिरिचलेट वर्ण है।
-== जैकोबी प्रतीक की गणना ==
+== '''जैकोबी प्रतीक की गणना''' ==
 उपरोक्त सूत्र एक कुशल की ओर ले जाते हैं {{nowrap|[[Big O notation|''O'']](log ''a'' log ''b'')}}<ref>Cohen, pp. 29–31</ref> जैकोबी प्रतीक की गणना के लिए एल्गोरिदम, दो संख्याओं की जीसीडी खोजने के लिए [[यूक्लिडियन एल्गोरिथ्म]] के अनुरूप। (नियम 2 के आलोक में यह आश्चर्यजनक नहीं होना चाहिए।)
@@ Line 1,197: / Line 1,197: @@
 </सिंटैक्सहाइलाइट>
-==गणना का उदाहरण==
+=='''गणना का उदाहरण'''==
 लीजेंड्रे प्रतीक {{big|(}}{{sfrac|''a''|''p''}}{{big|)}} केवल विषम अभाज्य संख्याओं p के लिए परिभाषित है। इस प्रकार यह जैकोबी प्रतीक के समान नियमों का पालन करता है (अर्थात, पारस्परिकता और इसके लिए पूरक सूत्र) {{big|(}}{{sfrac|−1|''p''}}{{big|)}} और {{big|(}}{{sfrac|2|''p''}}{{big|)}} और अंश की गुणात्मकता।)
@@ Line 1,261: / Line 1,261: @@
 \left(\frac{ 5}{21}\right) &= 1  &&\text{ but } &  5^\frac{21-1}{2} &\equiv 16\pmod{21}.
 \end{align}</math>
-इसलिए यदि यह अज्ञात है कि कोई संख्या n अभाज्य है या भाज्य है, तब हम एक यादृच्छिक संख्या a चुन सकते हैं, जैकोबी प्रतीक की गणना कर सकते हैं {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} और इसकी तुलना यूलर के सूत्र से करें; यदि वह मॉड्यूलो एन में भिन्न हैं, तब एन समग्र है; यदि उनके पास a के अनेक भिन्न-भिन्न मानों के लिए समान अवशेष मॉड्यूल n है, तब n संभवतः अभाज्य है।
+इसलिए यदि यह अज्ञात है कि कोई संख्या n अभाज्य है या भाज्य है, तब हम एक यादृच्छिक संख्या a चुन सकते हैं, जैकोबी प्रतीक की गणना कर सकते हैं {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} और इसकी तुलना यूलर के सूत्र से करें; यदि वह मॉड्यूलो एन में भिन्न हैं, तब एन समग्र है; यदि उनके पास a के अनेक भिन्न-भिन्न मानों के लिए समान अवशेष मॉड्यूल n है, तब n '''"संभवतः अभाज्य"''' है।
 यह संभाव्य सोलोवे-स्ट्रैसेन प्राइमलिटी परीक्षण और बैली-पीएसडब्ल्यू प्राइमलिटी टेस्ट और मिलर-राबिन प्राइमलिटी टेस्ट जैसे परिशोधन का आधार है।
-इस प्रकार अप्रत्यक्ष उपयोग के रूप में, इसे लुकास-लेहमर प्राइमैलिटी टेस्ट के निष्पादन के समय एक त्रुटि पता लगाने की दिनचर्या के रूप में उपयोग करना संभव है, इस प्रकार जिसे आधुनिक कंप्यूटर हार्डवेयर पर भी [[मेर्सन संख्या]] को संसाधित करते समय पूरा होने में अनेक सप्ताह लग सकते हैं। <math>\begin{align}2^{82,589,933} - 1\end{align}</math> (दिसंबर 2018 तक सबसे बड़ा ज्ञात मेर्सन प्राइम)। नाममात्र के स्थितियोंमें, जैकोबी प्रतीक:
+इस प्रकार अप्रत्यक्ष उपयोग के रूप में, इसे लुकास-लेहमर प्राइमैलिटी टेस्ट के निष्पादन के समय एक त्रुटि पता लगाने की दिनचर्या के रूप में उपयोग करना संभव है, इस प्रकार जिसे आधुनिक कंप्यूटर हार्डवेयर पर भी [[मेर्सन संख्या|मेर्सन संख्याओं]] को संसाधित करते समय पूरा होने में अनेक सप्ताह लग सकते हैं। <math>\begin{align}2^{82,589,933} - 1\end{align}</math> (दिसंबर 2018 तक सबसे बड़ा ज्ञात मेर्सन प्राइम)। नाममात्र के स्थितियोंमें, जैकोबी प्रतीक:
 <math>\begin{align}\left(\frac{s_i - 2}{M_p}\right) &= -1 & i \ne 0\end{align}</math>
-यह अंतिम अवशेष के लिए भी प्रयुक्त होता है <math>\begin{align}s_{p-2}\end{align}</math> और इसलिए इसे संभावित वैधता के सत्यापन के रूप में उपयोग किया जा सकता है। चूँकि, यदि हार्डवेयर में कोई त्रुटि होती है, तब 50% संभावना है कि परिणाम इसके अतिरिक्त 0 या 1 हो जाएगा, और पश्चात् की शर्तों के साथ नहीं बदलेगा। <math>\begin{align}s\end{align}</math> (जब तक कि कोई अन्य त्रुटि न हो और इसे वापस -1 में न बदल दे)।
+यह अंतिम अवशेष के लिए भी प्रयुक्त होता है <math>\begin{align}s_{p-2}\end{align}</math> और इसलिए इसे संभावित वैधता के सत्यापन के रूप में उपयोग किया जा सकता है। चूँकि, यदि हार्डवेयर में कोई त्रुटि होती है, तब 50% संभावना है कि परिणाम इसके अतिरिक्त 0 या 1 हो जाएगा और पश्चात् की शर्तों के साथ नहीं बदलेगा। <math>\begin{align}s\end{align}</math> (जब तक कि कोई अन्य त्रुटि न हो और इसे वापस -1 में न बदल दे)।
 ==यह भी देखें==
@@ Line 1,279: / Line 1,280: @@
 {{reflist}}
-संदर्भ
+== संदर्भ ==
 *{{cite book
-   | last1 = Cohen  | first1 = Henri
+   | last1 = कोहेन  | first1 = हेनरी
-   | title = A Course in Computational Algebraic Number Theory
+   | title = कम्प्यूटेशनल बीजगणितीय संख्या सिद्धांत में एक पाठ्यक्रम
-   | publisher = [[Springer Science+Business Media|Springer]]
+   | publisher = [[स्प्रिंगर साइंस+बिजनेस मीडिया|स्प्रिंगर]]
-   | location = Berlin
+   | location = बर्लिन
    | date = 1993
    | isbn = 3-540-55640-0}}
 *{{cite book
-   | last1 = Ireland  | first1 = Kenneth
+   | last1 = आयरलैंड  | first1 = केनेथ
-   | last2 = Rosen  | first2 = Michael
+   | last2 = रोजेन  | first2 = माइकल
-   | title = A Classical Introduction to Modern Number Theory (Second edition)
+   | title = आधुनिक संख्या सिद्धांत का एक शास्त्रीय परिचय (दूसरा संस्करण)
-   | publisher = [[Springer Science+Business Media|Springer]]
+   | publisher = [[स्प्रिंगर साइंस+बिजनेस मीडिया|स्प्रिंगर]]
-   | location = New York
+   | location = न्यूयॉर्क
    | date = 1990
    | isbn = 0-387-97329-X}}
 *{{cite book
-   | last1 = Lemmermeyer  | first1 = Franz
+   | last1 = लेमरमेयर  | first1 = फ्रांज
-   | title = Reciprocity Laws: from Euler to Eisenstein
+   | title = पारस्परिकता कानून: यूलर से ईसेनस्टीन तक
-   | publisher = [[Springer Science+Business Media|Springer]]
+   | publisher = [[स्प्रिंगर साइंस+बिजनेस मीडिया|स्प्रिंगर]]
-   | location = Berlin
+   | location = बर्लिन
    | date = 2000
    | isbn = 3-540-66957-4}}
 *{{cite journal
-   | title = On the Worst Case of Three Algorithms for Computing the Jacobi Symbol
+   | title = जैकोबी प्रतीक की गणना के लिए तीन एल्गोरिदम के सबसे खराब मामले पर
-   | first = Jeffrey | last = Shallit | author-link = Jeffrey Shallit
+   | first = जेफरी | last = शालित | author-link = जेफरी शैलिट
-   | journal = Journal of Symbolic Computation
+   | journal = प्रतीकात्मक संगणना का जर्नल
-   | date = December 1990 | volume = 10 | issue = 6 | pages = 593-61
+   | date = दिसंबर 1990 | volume = 10 | issue = 6 | pages = 593-61
    | url = https://digitalcommons.dartmouth.edu/cs_tr/42/
-   | doi = 10.1016/S0747-7171(08)80160-5 | id = Computer science technical report PCS-TR89-140
+   | doi = 10.1016/S0747-7171(08)80160-5 | id = कंप्यूटर विज्ञान तकनीकी रिपोर्ट PCS-TR89-140
-| doi-access = free}}
+| doi-access = मुक्त}}
 *{{cite techreport
-   | title = Average-case analyses of three algorithms for computing the Jacobi symbol
+   | title = जैकोबी प्रतीक की गणना के लिए तीन एल्गोरिदम का औसत-केस विश्लेषण
-   | first1 = Brigitte | last1 = Vallée | author-link1=Brigitte Vallée
+   | first1 = ब्रिजित | last1 = वले | author-link1=ब्रिगिट वैली
-   | first2 = Charly | last2 = Lemée
+   | first2 = चार्ली | last2 = लेमी
-   | date = October 1998
+   | date = अक्टूबर 1998
    | citeseerx = 10.1.1.32.3425
    | url = https://vallee.users.greyc.fr/Publications/jacobi.ps
@@ Line 1,329: / Line 1,330: @@
 == बाहरी संबंध ==
 * [http://math.fau.edu/richman/jacobi.htm Calculate Jacobi symbol] shows the steps of the calculation.
-[[Category: मॉड्यूलर अंकगणित]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 errors]]
 [[Category:Created On 07/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:मॉड्यूलर अंकगणित]]

Anonymous

Search

जैकोबी प्रतीक: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 16:19, 25 July 2023

Contents

परिभाषा

मूल्यों की तालिका

गुण