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

Revision as of 23:34, 12 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 एक द्विघात अवशेष modulo 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

संदर्भ

Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. ISBN 3-540-55640-0.
Ireland, Kenneth; Rosen, Michael (1990). A Classical Introduction to Modern Number Theory (Second edition). New York: Springer. ISBN 0-387-97329-X.
Lemmermeyer, Franz (2000). Reciprocity Laws: from Euler to Eisenstein. Berlin: Springer. ISBN 3-540-66957-4.
Shallit, Jeffrey (December 1990). "On the Worst Case of Three Algorithms for Computing the Jacobi Symbol". Journal of Symbolic Computation. 10 (6): 593–61. doi:10.1016/S0747-7171(08)80160-5. Computer science technical report PCS-TR89-140.
Vallée, Brigitte; Lemée, Charly (October 1998). Average-case analyses of three algorithms for computing the Jacobi symbol (Technical report). CiteSeerX 10.1.1.32.3425.
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 33: / Line 33: @@
 |}
 <div क्लास= थंबकैप्शन >
-'''जैकोबी प्रतीक''' {{big|(}}{{sfrac|''k''|''n''}}{{big|)}} विभिन्न k (शीर्ष के साथ) और n (बाईं ओर) के लिए। केवल {{nowrap|0 ≤ ''k'' < ''n''}} दिखाया गया है, क्योंकि नियम (2) के कारण किसी भी अन्य k को मॉड्यूलो n से कम किया जा सकता है। [[द्विघात अवशेष]]ों को पीले रंग में हाइलाइट किया गया है - ध्यान दें कि −1 के जैकोबी प्रतीक के साथ कोई भी प्रविष्टि द्विघात अवशेष नहीं है, और यदि k एक द्विघात अवशेष modulo a सहअभाज्य n है, तो {{nowrap|1={{big|(}}{{sfrac|''k''|''n''}}{{big|)}} = 1}}, लेकिन सभी प्रविष्टियाँ 1 के जैकोबी प्रतीक के साथ नहीं (देखें)। {{nowrap|1=''n'' = 9}} और {{nowrap|1=''n'' = 15}} पंक्तियाँ) द्विघात अवशेष हैं। यह भी ध्यान दें कि जब n या k एक वर्ग होता है, तो सभी मान अऋणात्मक होते हैं।
+'''जैकोबी प्रतीक''' {{big|(}}{{sfrac|''k''|''n''}}{{big|)}} विभिन्न k (शीर्ष के साथ) और n (बाईं ओर) के लिए। केवल {{nowrap|0 ≤ ''k'' < ''n''}} दिखाया गया है, क्योंकि नियम (2) के कारण किसी भी अन्य k को मॉड्यूलो n से कम किया जा सकता है। [[द्विघात अवशेष]]ों को पीले रंग में हाइलाइट किया गया है - ध्यान दें कि −1 के जैकोबी प्रतीक के साथ कोई भी प्रविष्टि द्विघात अवशेष नहीं है, और यदि k एक द्विघात अवशेष modulo a सहअभाज्य n है, तब {{nowrap|1={{big|(}}{{sfrac|''k''|''n''}}{{big|)}} = 1}}, किन्तु सभी प्रविष्टियाँ 1 के जैकोबी प्रतीक के साथ नहीं (देखें)। {{nowrap|1=''n'' = 9}} और {{nowrap|1=''n'' = 15}} पंक्तियाँ) द्विघात अवशेष हैं। यह भी ध्यान दें कि जब n या k एक वर्ग होता है, तब सभी मान अऋणात्मक होते हैं।
 </div>
 </div>
 </div>
-'जैकोबी प्रतीक' लीजेंड्रे प्रतीक का सामान्यीकरण है। 1837 में [[कार्ल गुस्ताव जैकब जैकोबी]] द्वारा प्रस्तुत,<ref>{{cite journal|first=C. G. J.|last=Jacobi|title=Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie|journal=Bericht Ak. Wiss. Berlin|date=1837|page=127–136}}</ref> यह [[मॉड्यूलर अंकगणित]] और [[संख्या सिद्धांत]] की अन्य शाखाओं में सैद्धांतिक रुचि रखता है, लेकिन इसका मुख्य उपयोग [[कम्प्यूटेशनल संख्या सिद्धांत]], विशेष रूप से [[प्रारंभिक परीक्षण]] और [[पूर्णांक गुणनखंडन]] में है; ये बदले में [[क्रिप्टोग्राफी]] में महत्वपूर्ण हैं।
+'जैकोबी प्रतीक' लीजेंड्रे प्रतीक का सामान्यीकरण है। 1837 में [[कार्ल गुस्ताव जैकब जैकोबी]] द्वारा प्रस्तुत,<ref>{{cite journal|first=C. G. J.|last=Jacobi|title=Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie|journal=Bericht Ak. Wiss. Berlin|date=1837|page=127–136}}</ref> यह [[मॉड्यूलर अंकगणित]] और [[संख्या सिद्धांत]] की अन्य शाखाओं में सैद्धांतिक रुचि रखता है, किन्तु इसका मुख्य उपयोग [[कम्प्यूटेशनल संख्या सिद्धांत]], विशेष रूप से [[प्रारंभिक परीक्षण]] और [[पूर्णांक गुणनखंडन]] में है; यह बदले में [[क्रिप्टोग्राफी]] में महत्वपूर्ण हैं।
 ==परिभाषा==
@@ Line 56: / Line 56: @@
 खाली उत्पाद के लिए सामान्य परिपाटी का पालन करते हुए, {{big|(}}{{sfrac|''a''|1}}{{big|)}}=1.
-जब निचला तर्क एक विषम अभाज्य होता है, तो जैकोबी प्रतीक लीजेंड्रे प्रतीक के बराबर होता है।
+जब निचला तर्क एक विषम अभाज्य होता है, तब जैकोबी प्रतीक लीजेंड्रे प्रतीक के सामान्तर होता है।
 ==मूल्यों की तालिका==
@@ Line 1,057: / Line 1,057: @@
 ==गुण==
-निम्नलिखित तथ्य, यहां तक कि पारस्परिकता कानून, जैकोबी प्रतीक की परिभाषा और लीजेंड्रे प्रतीक के संबंधित गुणों से सीधे तौर पर निकाले गए हैं।<ref>Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10</ref>
+निम्नलिखित तथ्य, यहां तक कि पारस्परिकता नियम, जैकोबी प्रतीक की परिभाषा और लीजेंड्रे प्रतीक के संबंधित गुणों से सीधे तौर पर निकाले गए हैं।<ref>Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10</ref>
-जैकोबी प्रतीक को केवल तभी परिभाषित किया जाता है जब ऊपरी तर्क (अंश) एक पूर्णांक होता है और निचला तर्क (हर) एक सकारात्मक विषम पूर्णांक होता है।
+जैकोबी प्रतीक को केवल तभी परिभाषित किया जाता है जब ऊपरी तर्क (अंश) एक पूर्णांक होता है और निचला तर्क (हर) एक धनात्मक विषम पूर्णांक होता है।
-:1. यदि n (एक विषम) अभाज्य है, तो जैकोबी प्रतीक {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} संबंधित लीजेंड्रे प्रतीक के बराबर है (और उसी के समान लिखा गया है)।
+:1. यदि n (एक विषम) अभाज्य है, तब जैकोबी प्रतीक {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} संबंधित लीजेंड्रे प्रतीक के सामान्तर है (और उसी के समान लिखा गया है)।
-:2. अगर {{nowrap|''a'' ≡ ''b'' &nbsp;(mod ''n'')}}, तब <math>\left(\frac{a}{n}\right) = \left(\frac{b}{n}\right)  = \left(\frac{a \pm m \cdot n}{n}\right)</math>
+:2. तथापि {{nowrap|''a'' ≡ ''b'' &nbsp;(mod ''n'')}}, तब <math>\left(\frac{a}{n}\right) = \left(\frac{b}{n}\right)  = \left(\frac{a \pm m \cdot n}{n}\right)</math>
 :3. <math>\left(\frac{a}{n}\right) =
 \begin{cases}
@@ Line 1,069: / Line 1,069: @@
 \end{cases}
 </math>
-यदि शीर्ष या निचला तर्क तय हो गया है, तो जैकोबी प्रतीक शेष तर्क में [[पूरी तरह से गुणक कार्य]] है:
+यदि शीर्ष या निचला तर्क तय हो गया है, तब जैकोबी प्रतीक शेष तर्क में [[पूरी तरह से गुणक कार्य]] है:
 :4. <math>\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.</math>
 :5. <math>\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.</math>
-[[द्विघात पारस्परिकता का नियम]]: यदि m और n विषम धनात्मक सहअभाज्य पूर्णांक हैं, तो
+[[द्विघात पारस्परिकता का नियम]]: यदि m और n विषम धनात्मक सहअभाज्य पूर्णांक हैं, तब
 :6. <math>\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\tfrac{m-1}{2}\cdot\tfrac{n-1}{2}} =
@@ Line 1,106: / Line 1,106: @@
 लीजेंड्रे प्रतीक की तरह:
-*अगर {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} = −1 तो a एक द्विघात गैरअवशेष मॉड्यूलो n है।
+*तथापि {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} = −1 तब a एक द्विघात गैरअवशेष मॉड्यूलो n है।
-*यदि a एक द्विघात अवशेष मॉड्यूलो n है और सबसे बड़ा सामान्य भाजक (a,n) = 1 है, तो {{big|(}}{{sfrac|''a''|''n''}}{{big|)}}=1.
+*यदि a एक द्विघात अवशेष मॉड्यूलो n है और सबसे बड़ा सामान्य भाजक (a,n) = 1 है, तब {{big|(}}{{sfrac|''a''|''n''}}{{big|)}}=1.
-लेकिन, लीजेंड्रे प्रतीक के विपरीत:
+किन्तु, लीजेंड्रे प्रतीक के विपरीत:
-:अगर {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} = 1 तो a द्विघात अवशेष मॉड्यूलो n हो भी सकता है और नहीं भी।
+:तथापि {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} = 1 तब a द्विघात अवशेष मॉड्यूलो n हो भी सकता है और नहीं भी।
-ऐसा इसलिए है क्योंकि a को एक द्विघात अवशेष मॉड्यूल n होने के लिए, n के प्रत्येक अभाज्य कारक को एक द्विघात अवशेष मॉड्यूलो होना चाहिए। हालाँकि, जैकोबी प्रतीक एक के बराबर है यदि, उदाहरण के लिए, ए एक गैर-अवशेष मॉड्यूलो है जो एन के दो प्रमुख कारक हैं।
+ऐसा इसलिए है क्योंकि a को एक द्विघात अवशेष मॉड्यूल n होने के लिए, n के प्रत्येक अभाज्य कारक को एक द्विघात अवशेष मॉड्यूलो होना चाहिए। चूँकि, जैकोबी प्रतीक एक के सामान्तर है यदि, उदाहरण के लिए, ए एक गैर-अवशेष मॉड्यूलो है जो एन के दो प्रमुख कारक हैं।
-हालाँकि जैकोबी प्रतीक की व्याख्या वर्गों और गैर-वर्गों के संदर्भ में समान रूप से नहीं की जा सकती है, इसे ज़ोलोटारेव के लेम्मा द्वारा क्रमपरिवर्तन के संकेत के रूप में समान रूप से व्याख्या किया जा सकता है।
+चूँकि जैकोबी प्रतीक की व्याख्या वर्गों और गैर-वर्गों के संदर्भ में समान रूप से नहीं की जा सकती है, इसे ज़ोलोटारेव के लेम्मा द्वारा क्रमपरिवर्तन के संकेत के रूप में समान रूप से व्याख्या किया जा सकता है।
 जैकोबी प्रतीक {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} मापांक n के लिए एक डिरिचलेट वर्ण है।
@@ Line 1,126: / Line 1,126: @@
 # नियम 2 का उपयोग करके अंश मॉड्यूल को हर से कम करें।
 # नियम 9 का उपयोग करके कोई भी सम अंश निकालें।
-# यदि अंश 1 है, तो नियम 3 और 4 1 का परिणाम देते हैं। यदि अंश और हर सहअभाज्य नहीं हैं, तो नियम 3 0 का परिणाम देता है।
+# यदि अंश 1 है, तब नियम 3 और 4 1 का परिणाम देते हैं। यदि अंश और हर सहअभाज्य नहीं हैं, तब नियम 3 0 का परिणाम देता है।
-# अन्यथा, अंश और हर अब विषम धनात्मक सहअभाज्य पूर्णांक हैं, इसलिए हम नियम 6 का उपयोग करके प्रतीक को पलट सकते हैं, फिर चरण 1 पर लौट सकते हैं।
+# अन्यथा, अंश और हर अभी विषम धनात्मक सहअभाज्य पूर्णांक हैं, इसलिए हम नियम 6 का उपयोग करके प्रतीक को पलट सकते हैं, फिर चरण 1 पर लौट सकते हैं।
 ===[[लुआ (प्रोग्रामिंग भाषा)]] में कार्यान्वयन===
@@ Line 1,247: / Line 1,247: @@
   =-1.
 \end{align}</math>
-दोनों गणनाओं के बीच अंतर यह है कि जब लीजेंड्रे प्रतीक का उपयोग किया जाता है तो प्रतीक को फ़्लिप करने से पहले अंश को अभाज्य शक्तियों में विभाजित करना पड़ता है। इससे जैकोबी प्रतीक का उपयोग करने की तुलना में लीजेंड्रे प्रतीक का उपयोग करने वाली गणना काफी धीमी हो जाती है, क्योंकि पूर्णांकों के गुणनखंडन के लिए कोई ज्ञात बहुपद-समय एल्गोरिदम नहीं है।<ref>The [[number field sieve]], the fastest known algorithm, requires
+दोनों गणनाओं के मध्य अंतर यह है कि जब लीजेंड्रे प्रतीक का उपयोग किया जाता है तब प्रतीक को फ़्लिप करने से पहले अंश को अभाज्य शक्तियों में विभाजित करना पड़ता है। इससे जैकोबी प्रतीक का उपयोग करने की तुलना में लीजेंड्रे प्रतीक का उपयोग करने वाली गणना अधिक  धीमी हो जाती है, क्योंकि पूर्णांकों के गुणनखंडन के लिए कोई ज्ञात बहुपद-समय एल्गोरिदम नहीं है।<ref>The [[number field sieve]], the fastest known algorithm, requires
 :<math>O\left(e^{(\ln N)^\frac13(\ln\ln N)^\frac23\big(C+o(1)\big)}\right)</math>
-operations  to factor ''n''. See Cohen, p. 495</ref> वास्तव में, यही कारण है कि जैकोबी ने प्रतीक पेश किया।
+operations  to factor ''n''. See Cohen, p. 495</ref> वास्तव में, यही कारण है कि जैकोबी ने प्रतीक प्रस्तुत किया।
 ==प्राथमिकता परीक्षण==
-एक और तरीके से जैकोबी और लेजेंड्रे प्रतीक भिन्न हैं। यदि यूलर के मानदंड सूत्र का उपयोग समग्र संख्या मॉड्यूलो में किया जाता है, तो परिणाम जैकोबी प्रतीक का मान हो भी सकता है और नहीं भी, और वास्तव में -1 या 1 भी नहीं हो सकता है। उदाहरण के लिए,
+एक और तरीके से जैकोबी और लेजेंड्रे प्रतीक भिन्न हैं। यदि यूलर के मानदंड सूत्र का उपयोग समग्र संख्या मॉड्यूलो में किया जाता है, तब परिणाम जैकोबी प्रतीक का मान हो भी सकता है और नहीं भी, और वास्तव में -1 या 1 भी नहीं हो सकता है। उदाहरण के लिए,
 :<math>\begin{align}
@@ Line 1,260: / Line 1,260: @@
 \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 में न बदल दे)।
 ==यह भी देखें==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 23:34, 12 July 2023

Contents

परिभाषा

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

गुण