जैकोबी प्रतीक

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 में कार्ल गुस्ताव जैकब जैकोबी द्वारा प्रस्तुत, यह मॉड्यूलर अंकगणित और संख्या सिद्धांत की अन्य शाखाओं में सैद्धांतिक रुचि रखता है, लेकिन इसका मुख्य उपयोग कम्प्यूटेशनल संख्या सिद्धांत, विशेष रूप से प्रारंभिक परीक्षण और पूर्णांक गुणनखंडन में है; ये बदले में क्रिप्टोग्राफी में महत्वपूर्ण हैं।

परिभाषा

किसी पूर्णांक 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

गुण

निम्नलिखित तथ्य, यहां तक ​​कि पारस्परिकता कानून, जैकोबी प्रतीक की परिभाषा और लीजेंड्रे प्रतीक के संबंधित गुणों से सीधे तौर पर निकाले गए हैं। जैकोबी प्रतीक को केवल तभी परिभाषित किया जाता है जब ऊपरी तर्क (अंश) एक पूर्णांक होता है और निचला तर्क (हर) एक सकारात्मक विषम पूर्णांक होता है।

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

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.

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

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

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

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

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

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

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

1. नियम 2 का उपयोग करके अंश मॉड्यूल को हर से कम करें।
2. नियम 9 का उपयोग करके कोई भी सम अंश निकालें।
3. यदि अंश 1 है, तो नियम 3 और 4 1 का परिणाम देते हैं। यदि अंश और हर सहअभाज्य नहीं हैं, तो नियम 3 0 का परिणाम देता है।
4. अन्यथा, अंश और हर अब विषम धनात्मक सहअभाज्य पूर्णांक हैं, इसलिए हम नियम 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}}$

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

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

एक और तरीके से जैकोबी और लेजेंड्रे प्रतीक भिन्न हैं। यदि यूलर के मानदंड सूत्र का उपयोग समग्र संख्या मॉड्यूलो में किया जाता है, तो परिणाम जैकोबी प्रतीक का मान हो भी सकता है और नहीं भी, और वास्तव में -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 में न बदल दे)।

यह भी देखें

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

टिप्पणियाँ

संदर्भ

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