वर्ग करके घातांक

गणित और कंप्यूटर प्रोग्रामिंग में, वर्ग द्वारा घातांक एक संख्या की बड़ी सकारात्मक पूर्णांक शक्तियों की तेजी से गणना के लिए एक सामान्य विधि है, या अधिक सामान्यतः एक अर्धसमूह के एक तत्व की, जैसे बहुपद या वर्ग मैट्रिक्स। कुछ वेरिएंट्स को आमतौर पर वर्ग-और-गुणा एल्गोरिदम या बाइनरी एक्सपोनेंटिएशन के रूप में संदर्भित किया जाता है। ये काफी सामान्य उपयोग के हो सकते हैं, उदाहरण के लिए मॉड्यूलर अंकगणित या मेट्रिसेस की शक्ति। semigroup ्स के लिए जिसके लिए एबेलियन समूह#नोटेशन का आमतौर पर उपयोग किया जाता है, जैसे क्रिप्टोग्राफी में उपयोग किए जाने वाले अण्डाकार वक्र, इस विधि को डबल-एंड-ऐड भी कहा जाता है।

मूल विधि

पुनरावर्ती संस्करण

विधि अवलोकन पर आधारित है कि, किसी भी पूर्णांक के लिए $n>0$ , किसी के पास:

x^{n}={\begin{cases}x\,(x^{2})^{(n-1)/2},&{\mbox{if }}n{\mbox{ is odd}}\\(x^{2})^{n/2},&{\mbox{if }}n{\mbox{ is even}}\end{cases}}

यदि घातांक शून्य है तो उत्तर 1 है और यदि घातांक ऋणात्मक है तो हम धनात्मक घातांक का उपयोग करके मान को फिर से लिखकर पिछले सूत्र का पुन: उपयोग कर सकते हैं। वह है,

x^{-n}=\left({\frac {1}{x}}\right)^{n}\,.

साथ में, इन्हें निम्नलिखित पुनरावर्तन (कंप्यूटर विज्ञान) के रूप में सीधे लागू किया जा सकता है:

 में: एक पूर्णांक x; एक पूर्णांक एन
 आउट: एक्स^एन
 
 exp_by_squaring (एक्स, एन)
   अगर एन <0 तो
      वापसी exp_by_squaring (1 / x, -n);
   वरना अगर n = 0 तब
      वापसी 1;
   अन्यथा यदि n तब भी है
      रिटर्न exp_by_squaring(x * x, n / 2);
   वरना अगर n विषम है तो
      वापसी x * exp_by_squaring (x * x, (n - 1) / 2);
 अंत समारोह

प्रत्येक पुनरावर्ती कॉल में, बाइनरी प्रतिनिधित्व के कम से कम महत्वपूर्ण अंक $n$ हटा दिया गया। यह इस प्रकार है कि पुनरावर्ती कॉल की संख्या है $\lceil \log _{2}n\rceil ,$ के बाइनरी प्रतिनिधित्व के अंश ्स की संख्या $n$ . तो यह एल्गोरिथ्म वर्गों की संख्या और गुणन की कम संख्या की गणना करता है, जो की संख्या के बराबर है $1$ के बाइनरी प्रतिनिधित्व में $n$ . संचालन की इस लॉगरिदमिक संख्या की तुलना उस तुच्छ एल्गोरिथम से की जानी चाहिए जिसकी आवश्यकता होती है $n - 1$ गुणन।

यह एल्गोरिदम टेल कॉल नहीं है | टेल-रिकर्सिव। इसका तात्पर्य यह है कि इसके लिए एक सहायक मेमोरी की आवश्यकता होती है जो रिकर्सिव कॉल की संख्या के लगभग आनुपातिक (या उच्चतर, यदि कोई डेटा के बढ़ते आकार को ध्यान में रखता है) है।

अगले खंड के एल्गोरिदम एक अलग दृष्टिकोण का उपयोग करते हैं, और परिणामी एल्गोरिदम को समान संख्या में संचालन की आवश्यकता होती है, लेकिन एक सहायक मेमोरी का उपयोग करें जो परिणाम को संग्रहीत करने के लिए आवश्यक मेमोरी के समान है।

निरंतर सहायक स्मृति के साथ

इस खंड में वर्णित वेरिएंट सूत्र पर आधारित हैं

yx^{n}={\begin{cases}(yx)\,(x^{2})^{(n-1)/2},&{\mbox{if }}n{\mbox{ is odd}}\\y\,(x^{2})^{n/2},&{\mbox{if }}n{\mbox{ is even}}.\end{cases}}

यदि कोई पुनरावर्ती रूप से इस सूत्र को लागू करता है, से शुरू करके $y = 1$ , अंततः एक घातांक के बराबर मिलता है $0$ , और फिर वांछित परिणाम बायाँ कारक है।

इसे पूंछ-पुनरावर्ती कार्य के रूप में कार्यान्वित किया जा सकता है:

  Function exp_by_squaring(x, n)
    return exp_by_squaring2(1, x, n)
  Function exp_by_squaring2(y, x, n)
    if n < 0 then return exp_by_squaring2(y, 1 / x, - n);
    else if n = 0 then return y;
    else if n is even then return exp_by_squaring2(y, x * x, n / 2);
    else if n is odd then return exp_by_squaring2(x * y, x * x, (n - 1) / 2).

एल्गोरिथम का पुनरावृत्ति संस्करण भी एक बाध्य सहायक स्थान का उपयोग करता है, और इसके द्वारा दिया जाता है

  Function exp_by_squaring_iterative(x, n)
    if n < 0 then
      x := 1 / x;
      n := -n;
    if n = 0 then return 1
    y := 1;
    while n > 1 do
      if n is even then
        x := x * x;
        n := n / 2;
      else
        y := x * y;
        x := x * x;
        n := (n – 1) / 2;
    return x * y

एल्गोरिदम की शुद्धता इस तथ्य से उत्पन्न होती है कि $yx^{n}$ गणना के दौरान अपरिवर्तनीय है; यह है $1\cdot x^{n}=x^{n}$ शुरू में; और यह है $yx^{0}=y$ अंत में।

ये एल्गोरिदम पूर्ववर्ती अनुभाग के एल्गोरिदम के समान ही संचालन की संख्या का उपयोग करते हैं, लेकिन गुणा एक अलग क्रम में किया जाता है।

कम्प्यूटेशनल जटिलता

एक संक्षिप्त विश्लेषण से पता चलता है कि ऐसा एल्गोरिदम उपयोग करता है $\lfloor \log _{2}n\rfloor$ स्क्वायरिंग और अधिक से अधिक $\lfloor \log _{2}n\rfloor$ गुणन, कहाँ $\lfloor \;\rfloor$ फर्श समारोह को दर्शाता है। अधिक सटीक रूप से, गुणन की संख्या n के बाइनरी विस्तार में मौजूद लोगों की संख्या से एक कम है। लगभग 4 से अधिक n के लिए यह आधार को बार-बार अपने आप से गुणा करने की तुलना में कम्प्यूटेशनल रूप से अधिक कुशल है।

प्रत्येक वर्ग का परिणाम पिछले अंकों की संख्या का लगभग दोगुना होता है, और इसलिए, यदि दो डी-अंकों की संख्या का गुणन O(d) में कार्यान्वित किया जाता है^k) संचालन कुछ निश्चित k के लिए, फिर कंप्यूटिंग x की जटिलताⁿ द्वारा दिया गया है

\sum \limits _{i=0}^{O(\log n)}{\big (}2^{i}O(\log x){\big )}^{k}=O{\big (}(n\log x)^{k}{\big )}.

2^k-आरी विधि

यह एल्गोरिथ्म x के मान की गणना करता हैⁿ बेस 2 में एक्सपोनेंट को बढ़ाने के बाद^{क</सुप>. यह पहली बार 1939 में ब्राउर द्वारा प्रस्तावित किया गया था। नीचे दिए गए एल्गोरिदम में हम निम्नलिखित फ़ंक्शन f(0) = (k,0) और f(m) = (s,u) का उपयोग करते हैं, जहां m = u·2^एस यू विषम के साथ।}

कलन विधि:

इनपुट: G का एक तत्व x, एक पैरामीटर k > 0, एक गैर-ऋणात्मक पूर्णांक $n = (n l -1, n l -2, ..., n 0) 2 k$ और पूर्व संगणित मान $x^{3},x^{5},...,x^{2^{k}-1}$ .

आउटपुट: तत्व एक्सⁿ जी में

वाई: = 1; मैं := एल - 1
'जबकि' मैं ≥ 0 करते हैं
    (एस, यू) := एफ (एन_i)
    j के लिए := 1 से k-s करते हैं
        यः= य^{2</उप>
    यः= य*x^यू
    j के लिए := 1 से s करें
        यः= य^{2</उप>
    मैं:= मैं - 1
वापसी वाई}}

इष्टतम दक्षता के लिए, k सबसे छोटा पूर्णांक संतोषजनक होना चाहिए^[1]^{[clarification needed]}

\log n<{\frac {k(k+1)\cdot 2^{2k}}{2^{k+1}-k-2}}+1.

स्लाइडिंग-विंडो विधि

यह विधि 2 का एक कुशल रूप है^k-आर्य विधि। उदाहरण के लिए, एक्सपोनेंट 398 की गणना करने के लिए, जिसमें बाइनरी एक्सपेंशन (110 001 110) है₂, हम 2 का उपयोग करके लंबाई 3 की विंडो लेते हैं^k-आर्य विधि एल्गोरिदम और 1, x की गणना करें^{3</सुप>, एक्स⁶, एक्स¹², एक्स²⁴, एक्स⁴⁸, एक्स⁴⁹, एक्स⁹⁸, एक्स⁹⁹, एक्स¹⁹⁸, x¹⁹⁹, एक्स³⁹⁸.
लेकिन, हम 1, x की गणना भी कर सकते हैं^{3</सुप>, एक्स⁶, एक्स¹², एक्स²⁴, एक्स⁴⁸, एक्स⁹⁶, एक्स¹⁹², एक्स¹⁹⁹, एक्स³⁹⁸, जो एक गुणन बचाता है और मूल्यांकन के बराबर होता है (110 001 110)₂
यहाँ सामान्य एल्गोरिथ्म है:}}

कलन विधि:

इनपुट: G का एक तत्व x, एक गैर नकारात्मक पूर्णांक $n =(n l -1, n l -2, ..., n 0) 2$ , एक पैरामीटर k > 0 और पूर्व-परिकलित मान $x^{3},x^{5},...,x^{2^{k}-1}$ .

आउटपुट: तत्व एक्सⁿ ∈ जी.

कलन विधि:

वाई: = 1; मैं := एल - 1
'जबकि' मैं > -1 'करो'
    'अगर' एन_i = 0 तब
        यः= य²' i := i - 1
    अन्य
        s := अधिकतम {i - k + 1, 0}
        जबकि एन_s = 0 करो
            स := स + 1^{[notes 1]}

h के लिए := 1 से i - s + 1 करते हैं

            यः= य^{2</उप>
        में := (एन_i, एन_i-1, ..., एन_s)₂}

यः= य*x^यू

        मैं := एस - 1
वापसी वाई

मोंटगोमरी की सीढ़ी तकनीक

घातांक के लिए कई एल्गोरिदम साइड-चैनल हमलों के खिलाफ सुरक्षा प्रदान नहीं करते हैं। अर्थात्, एक हमलावर वर्ग और गुणा के अनुक्रम को देखकर (आंशिक रूप से) गणना में शामिल एक्सपोनेंट को पुनर्प्राप्त कर सकता है। यह एक समस्या है यदि प्रतिपादक को गुप्त रहना चाहिए, जैसा कि कई सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी|सार्वजनिक-कुंजी क्रिप्टो सिस्टम में होता है। पीटर मोंटगोमरी (गणितज्ञ) नामक एक तकनीक | मोंटगोमरी की सीढ़ी^[2] इस चिंता को संबोधित करता है।

एक धनात्मक, शून्येतर पूर्णांक n = (n_k−1...एन₀)₂ एन के साथ_k−1 = 1, हम x की गणना कर सकते हैंⁿ इस प्रकार है:

एक्स₁ = एक्स; एक्स₂ = एक्स^{2</उप>
i = k - 2 से 0 के लिए
    अगर एन_i = 0 तब
        एक्स₂ = एक्स₁ * एक्स₂; एक्स₁ = एक्स₁^{2</उप>
    अन्य
        एक्स₁ = एक्स₁ * एक्स₂; एक्स₂ = एक्स₂^{2</उप>
वापसी एक्स₁}}}

एल्गोरिथ्म संचालन का एक निश्चित अनुक्रम करता है (लॉगन तक): बिट के विशिष्ट मूल्य की परवाह किए बिना, प्रतिपादक में प्रत्येक बिट के लिए एक गुणन और वर्ग होता है। दोहरीकरण द्वारा गुणन के लिए एक समान एल्गोरिथ्म मौजूद है।

मॉन्टगोमरी की सीढ़ी का यह विशिष्ट कार्यान्वयन अभी तक कैश टाइमिंग हमलों के खिलाफ सुरक्षित नहीं है: मेमोरी एक्सेस लेटेंसी अभी भी एक हमलावर के लिए देखी जा सकती है, क्योंकि गुप्त प्रतिपादक के बिट्स के मूल्य के आधार पर विभिन्न चर का उपयोग किया जाता है। आधुनिक क्रिप्टोग्राफ़िक कार्यान्वयन यह सुनिश्चित करने के लिए एक स्कैटर तकनीक का उपयोग करते हैं कि प्रोसेसर हमेशा तेज कैश को याद करता है।^[3]

फिक्स्ड-बेस एक्सपोनेंट

एक्स की गणना करने के लिए कई विधियां नियोजित की जा सकती हैंⁿ जब आधार निश्चित होता है और घातांक बदलता रहता है। जैसा कि कोई देख सकता है, इन एल्गोरिदम में पूर्वगणना एक महत्वपूर्ण भूमिका निभाते हैं।

याओ की विधि

याओ की विधि ओर्थोगोनल है $2 k$ -आर्य पद्धति जहां घातांक को मूलांक में विस्तारित किया जाता है $b = 2 k$ और गणना उपरोक्त एल्गोरिथम में की गई है। होने देना $n$ , $n i$ , $b$ , और $b i$ पूर्णांक हो।

प्रतिपादक को जाने दो $n$ के रूप में लिखा जाए

n=\sum _{i=0}^{w-1}n_{i}b_{i},

कहाँ $0\leqslant n_{i}<h$ सभी के लिए $i\in [0,w-1]$ .

होने देना $x i = x b i$ .

तब एल्गोरिथ्म समानता का उपयोग करता है

x^{n}=\prod _{i=0}^{w-1}x_{i}^{n_{i}}=\prod _{j=1}^{h-1}{\bigg [}\prod _{n_{i}=j}x_{i}{\bigg ]}^{j}.

तत्व दिया $x$ का $G$ , और प्रतिपादक $n$ पूर्व संगणित मानों के साथ उपरोक्त रूप में लिखा गया है $x b 0 ... x b w -1$ , तत्व $x n$ की गणना नीचे एल्गोरिथम का उपयोग करके की जाती है:

वाई = 1, यू = 1, जे = एच -1
जबकि j > 0 करते हैं
    i = 0 से w - 1 के लिए
        अगर एन_i = जे फिर
            यू = यू × एक्स^{b_i</सुप>
    वाई = वाई × यू
    जे = जे - 1
वापसी वाई}

अगर हम सेट करते हैं $h = 2 k$ और $b i = h i$ , फिर $n i$ मान केवल अंक हैं $n$ बेस में $h$ . याओ की विधि उन सबसे पहले आप में एकत्रित होती है $x i$ जो उच्चतम शक्ति को दिखाई देते हैं $h-1$ ; अगले दौर में सत्ता के साथ $h-2$ में एकत्र किया जाता है $u$ साथ ही आदि। चर y को गुणा किया जाता है $h-1$ बार प्रारंभिक के साथ $u$ , $h-2$ बार अगली उच्चतम शक्तियों के साथ, और इसी तरह। एल्गोरिथम उपयोग करता है $w+h-2$ गुणन, और $w+1$ तत्वों को गणना करने के लिए संग्रहित किया जाना चाहिए $x n$ .^[1]

यूक्लिडियन विधि

यूक्लिडियन पद्धति को पहली बार पीडी रूइज द्वारा प्रीकंप्यूटेशन और वेक्टर एडिशन चेन का उपयोग करके कुशल एक्सपोनेंटिएशन में पेश किया गया था।

कंप्यूटिंग के लिए यह तरीका $x^{n}$ समूह में $G$ , कहाँ $n$ एक प्राकृतिक पूर्णांक है, जिसका एल्गोरिदम नीचे दिया गया है, निम्नलिखित समानता का पुनरावर्ती उपयोग कर रहा है:

x_{0}^{n_{0}}\cdot x_{1}^{n_{1}}=\left(x_{0}\cdot x_{1}^{q}\right)^{n_{0}}\cdot x_{1}^{n_{1}\mod n_{0}},

कहाँ $q=\left\lfloor {\frac {n_{1}}{n_{0}}}\right\rfloor$ . दूसरे शब्दों में, प्रतिपादक का एक यूक्लिडियन विभाजन $n 1$ द्वारा $n 0$ का उपयोग भागफल लौटाने के लिए किया जाता है $q$ और आराम $n 1 mod n 0$ .

आधार तत्व दिया $x$ समूह में $G$ , और प्रतिपादक $n$ याओ की विधि, तत्व के रूप में लिखा गया है $x^{n}$ का उपयोग करके गणना की जाती है $l$ पूर्व संगणित मान $x^{b_{0}},...,x^{b_{l_{i}}}$ और फिर नीचे एल्गोरिथ्म।

लूप शुरू करें

Find $M\in [0,l-1]$ , such that $\forall i\in [0,l-1],n_{M}\geq n_{i}$ . Find $N\in {\big (}[0,l-1]-M{\big )}$ , such that $\forall i\in {\big (}[0,l-1]-M{\big )},n_{N}\geq n_{i}$ .

    ब्रेक लूप if  $n_{N}=0$ .

Let $q=\lfloor n_{M}/n_{N}\rfloor$ , and then let $n_{N}=(n_{M}{\bmod {n}}_{N})$ . Compute recursively $x_{M}^{q}$ , and then let $x_{N}=x_{N}\cdot x_{M}^{q}$ .

अंत पाश;

Return $x^{n}=x_{M}^{n_{M}}$ .

एल्गोरिथ्म सबसे पहले सबसे बड़ा मूल्य पाता है $n i$ और फिर के सेट के भीतर सुप्रीमम ${ ni \ i ≠ M }$ . फिर यह उठता है $x M$ सत्ता में $q$ , इस मान को इससे गुणा करता है $x N$ , और फिर असाइन करें $x N$ इस गणना का परिणाम और $n M$ मूल्य $n M$ मापांक $n N$ .

आगे के आवेदन

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

पावर (एक्स, -एन) = (पावर (एक्स, एन))^-1.

विधि प्रत्येक सेमिग्रुप में काम करती है और अक्सर मैट्रिक्स (गणित) की शक्तियों की गणना करने के लिए प्रयोग की जाती है।

उदाहरण के लिए, का मूल्यांकन

13789⁷²²³⁴¹ (मॉड 2345) = 2029

भोली विधि का उपयोग करने पर बहुत लंबा समय और अधिक संग्रहण स्थान लगेगा: 13789 की गणना करें⁷²²³⁴¹, फिर 2345 से विभाजित करने पर शेषफल लें। अधिक प्रभावी विधि का उपयोग करने में भी अधिक समय लगेगा: वर्ग 13789, शेषफल को 2345 से विभाजित करने पर, परिणाम को 13789 से गुणा करें, और इसी तरह। इससे कम समय लगेगा $2\log _{2}(722340)\leq 40$ मॉड्यूलर गुणन।

उपरोक्त ऍक्स्प-बाय-स्क्वैरिंग एल्गोरिथम को लागू करने के साथ, * x * y = xy mod 2345 के रूप में व्याख्या की गई है (अर्थात, शेष के साथ एक विभाजन के बाद एक गुणा) केवल 27 गुणा और पूर्णांकों के विभाजन की ओर जाता है, जो सभी को एक में संग्रहीत किया जा सकता है एकल मशीन शब्द।

हस्ताक्षरित-अंकों की रीकोडिंग

कुछ संगणनाओं में नकारात्मक गुणांकों की अनुमति देना अधिक कुशल हो सकता है और इसलिए आधार के व्युत्क्रम का उपयोग किया जाता है, बशर्ते कि उलटा हो $G$ तेज है या पूर्व संगणित किया गया है। उदाहरण के लिए, गणना करते समय $x 2 k -1$ , बाइनरी विधि की आवश्यकता है $k -1$ गुणन और $k -1$ वर्ग। हालांकि कोई प्रदर्शन कर सकता था $k$ प्राप्त करने के लिए वर्ग $x 2 k$ और फिर से गुणा करें $x -1$ प्राप्त करने के लिए $x 2 k -1$ .

इसके लिए हम एक पूर्णांक के हस्ताक्षरित अंकों के प्रतिनिधित्व को परिभाषित करते हैं $n$ रेडिक्स में $b$ जैसा

n=\sum _{i=0}^{l-1}n_{i}b^{i}{\text{  with  }}|n_{i}|<b.

हस्ताक्षरित बाइनरी प्रतिनिधित्व विशेष पसंद से मेल खाता है $b = 2$ और $n_{i}\in \{-1,0,1\}$ . द्वारा निरूपित किया जाता है $(n_{l-1}\dots n_{0})_{s}$ . इस प्रतिनिधित्व की गणना के लिए कई तरीके हैं। प्रतिनिधित्व अद्वितीय नहीं है। उदाहरण के लिए, ले लो $n = 478$ : दो अलग-अलग हस्ताक्षरित-द्विआधारी प्रतिनिधित्व इसके द्वारा दिए गए हैं $(10{\bar {1}}1100{\bar {1}}10)_{s}$ और $(100{\bar {1}}1000{\bar {1}}0)_{s}$ , कहाँ ${\bar {1}}$ निरूपित करने के लिए प्रयोग किया जाता है $-1$ . चूंकि बाइनरी विधि आधार -2 प्रतिनिधित्व में प्रत्येक गैर-शून्य प्रविष्टि के लिए गुणन की गणना करती है $n$ , हम गैर-शून्य प्रविष्टियों की सबसे छोटी संख्या के साथ हस्ताक्षरित-बाइनरी प्रतिनिधित्व खोजने में रुचि रखते हैं, जो कि न्यूनतम हैमिंग वजन वाला है। ऐसा करने का एक तरीका गैर-निकटवर्ती रूप में प्रतिनिधित्व की गणना करना है, या संक्षेप में NAF है, जो संतुष्ट करता है $n_{i}n_{i+1}=0{\text{ for all }}i\geqslant 0$ और द्वारा दर्शाया गया $(n_{l-1}\dots n_{0})_{\text{NAF}}$ . उदाहरण के लिए, NAF 478 का प्रतिनिधित्व है $(1000{\bar {1}}000{\bar {1}}0)_{\text{NAF}}$ . इस प्रतिनिधित्व में हमेशा न्यूनतम हैमिंग वजन होता है। किसी दिए गए पूर्णांक के NAF प्रतिनिधित्व की गणना करने के लिए एक सरल एल्गोरिथम $n=(n_{l}n_{l-1}\dots n_{0})_{2}$ साथ $n_{l}=n_{l-1}=0$ निम्नलखित में से कोई:

$c_{0}=0$

के लिए  $i = 0$  को  $l - 1$  करना

$c_{i+1}=\left\lfloor {\frac {1}{2}}(c_{i}+n_{i}+n_{i+1})\right\rfloor$ $n_{i}'=c_{i}+n_{i}-2c_{i+1}$ return $(n_{l-1}'\dots n_{0}')_{\text{NAF}}$

कोयामा और त्सुरुओका द्वारा एक और एल्गोरिदम को उस स्थिति की आवश्यकता नहीं है $n_{i}=n_{i+1}=0$ ; यह अभी भी हैमिंग वजन को कम करता है।

विकल्प और सामान्यीकरण

स्क्वेरिंग द्वारा एक्सपोनेंटिएशन को एक सबऑप्टिमल अतिरिक्त-श्रृंखला घातांक एल्गोरिथम के रूप में देखा जा सकता है: यह एक्सपोनेंट की गणना एक अतिरिक्त श्रृंखला द्वारा करता है जिसमें बार-बार एक्सपोनेंट दोहरीकरण (स्क्वायरिंग) और/या केवल एक (x से गुणा करके) एक्सपोनेंट बढ़ाना शामिल है। अधिक आम तौर पर, यदि कोई पहले से गणना किए गए एक्सपोनेंट को (x की उन शक्तियों को गुणा करके) अभिव्यक्त करने की अनुमति देता है, तो कभी-कभी कम गुणन (लेकिन आमतौर पर अधिक मेमोरी का उपयोग करके) एक्सपोनेंटिएशन का प्रदर्शन किया जा सकता है। सबसे छोटी शक्ति जहां ऐसा होता है वह n = 15 के लिए है:

x^{15}=x\times (x\times [x\times x^{2}]^{2})^{2}

(वर्गीकरण, 6 गुणा),

x^{15}=x^{3}\times ([x^{3}]^{2})^{2}

(इष्टतम जोड़ श्रृंखला, x के 5 गुणक³ का पुन: उपयोग किया जाता है)।

सामान्य तौर पर, किसी दिए गए घातांक के लिए इष्टतम जोड़ श्रृंखला खोजना एक कठिन समस्या है, जिसके लिए कोई कुशल एल्गोरिदम ज्ञात नहीं है, इसलिए इष्टतम श्रृंखलाएं आमतौर पर केवल छोटे घातांकों के लिए उपयोग की जाती हैं (उदाहरण के लिए संकलक में जहां छोटी शक्तियों के लिए जंजीरों को पूर्व-सारणीबद्ध किया गया है) ). हालांकि, ऐसे कई अनुमानी एल्गोरिदम हैं, जो इष्टतम नहीं होने के बावजूद अतिरिक्त बहीखाता पद्धति के काम और मेमोरी उपयोग की लागत पर घातांक की तुलना में कम गुणन करते हैं। इसके बावजूद, बिग-ओ नोटेशन | Θ (लॉग एन) की तुलना में गुणन की संख्या कभी भी अधिक धीरे-धीरे नहीं बढ़ती है, इसलिए ये एल्गोरिदम केवल एक स्थिर कारक द्वारा सर्वोत्तम रूप से वर्ग करके घातांक पर स्पर्शोन्मुख रूप से सुधार करते हैं।

यह भी देखें

मॉड्यूलर घातांक
वेक्टर अतिरिक्त श्रृंखला
मोंटगोमरी कमी
गैर-निकटवर्ती रूप
अतिरिक्त श्रृंखला

संदर्भ

↑ ^1.0 ^1.1 Cohen, H.; Frey, G., eds. (2006). अण्डाकार और हाइपरेलिप्टिक वक्र क्रिप्टोग्राफी की पुस्तिका. Discrete Mathematics and Its Applications. Chapman & Hall/CRC. ISBN 9781584885184.
↑ Montgomery, Peter L. (1987). "स्पीडिंग द पोलार्ड एंड एलिप्टिक कर्व मेथड्स ऑफ फैक्टराइजेशन" (PDF). Math. Comput. 48 (177): 243–264. doi:10.1090/S0025-5718-1987-0866113-7.
↑ Gueron, Shay (5 April 2012). "मॉड्यूलर घातांक का कुशल सॉफ्टवेयर कार्यान्वयन" (PDF). Journal of Cryptographic Engineering. 2 (1): 31–43. doi:10.1007/s13389-012-0031-5. S2CID 7629541.

[2] In this line, the loop finds the longest string of length less than or equal to k ending in a non-zero value. Not all odd powers of 2 up to $x^{2^{k}-1}$ need be computed, and only those specifically involved in the computation need be considered.

[frey-1] 1.0 ^1.1 Cohen, H.; Frey, G., eds. (2006). अण्डाकार और हाइपरेलिप्टिक वक्र क्रिप्टोग्राफी की पुस्तिका. Discrete Mathematics and Its Applications. Chapman & Hall/CRC. ISBN 9781584885184.

[ladder-3] Montgomery, Peter L. (1987). "स्पीडिंग द पोलार्ड एंड एलिप्टिक कर्व मेथड्स ऑफ फैक्टराइजेशन" (PDF). Math. Comput. 48 (177): 243–264. doi:10.1090/S0025-5718-1987-0866113-7.

[4] Gueron, Shay (5 April 2012). "मॉड्यूलर घातांक का कुशल सॉफ्टवेयर कार्यान्वयन" (PDF). Journal of Cryptographic Engineering. 2 (1): 31–43. doi:10.1007/s13389-012-0031-5. S2CID 7629541.

[1]

[notes 1]

[2]

[3]

वर्ग करके घातांक

Contents

मूल विधि

पुनरावर्ती संस्करण

निरंतर सहायक स्मृति के साथ

कम्प्यूटेशनल जटिलता

2^k-आरी विधि

स्लाइडिंग-विंडो विधि

मोंटगोमरी की सीढ़ी तकनीक

फिक्स्ड-बेस एक्सपोनेंट

याओ की विधि

यूक्लिडियन विधि

आगे के आवेदन

हस्ताक्षरित-अंकों की रीकोडिंग

विकल्प और सामान्यीकरण

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation menu

Search

वर्ग करके घातांक

मूल विधि

पुनरावर्ती संस्करण

निरंतर सहायक स्मृति के साथ

कम्प्यूटेशनल जटिलता

2k-आरी विधि

स्लाइडिंग-विंडो विधि

मोंटगोमरी की सीढ़ी तकनीक

फिक्स्ड-बेस एक्सपोनेंट

याओ की विधि

यूक्लिडियन विधि

आगे के आवेदन

हस्ताक्षरित-अंकों की रीकोडिंग

विकल्प और सामान्यीकरण

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation menu

Search

2^k-आरी विधि