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

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

मूल विधि

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

विधि अवलोकन पर आधारित है कि, किसी भी पूर्णांक के लिए $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}\,.$$

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

 In: an integer x; an integer n
 Out: xn
 
 exp_by_squaring(x, n)
   if n < 0 then
      return exp_by_squaring(1 / x, -n);
   else if n = 0 then 
      return 1;
   else if n is even then 
      return exp_by_squaring(x * x, n / 2);
   else if n is odd then 
      return x * exp_by_squaring(x * x, (n - 1) / 2);
 end function 

प्रत्येक पुनरावर्ती कॉल में, बाइनरी प्रतिनिधित्व के कम से कम महत्वपूर्ण अंक 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·2S U विषम के साथ उपयोग किया जाता है।

कलन विधि:

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

आउटपुट: अवयव Xⁿ G में

y := 1; i := l - 1
while i ≥ 0 do
    (s, u) := f(ni)
    for j := 1 to k - s do
        y := y2
    y := y * xu
    for j := 1 to s do
        y := y2
    i := i - 1
return y

इष्टतम दक्षता के लिए, k सबसे छोटा पूर्णांक संतोषजनक होना चाहिए

$\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 की गणना करें, एक्स6, एक्स12, एक्स24, एक्स48, एक्स49, एक्स98, एक्स99, एक्स198, x199, एक्स398.}

लेकिन, हम 1, x^{3 की गणना भी कर सकते हैं, एक्स6, एक्स12, एक्स24, एक्स48, एक्स96, एक्स192, एक्स199, एक्स398, जो एक गुणन बचाता है और मानांकन के बराबर होता है (110 001 110)₂}

यहाँ सामान्य एल्गोरिथ्म है:

कलन विधि:

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

आउटपुट: अवयव Xⁿ ∈ G.

कलन विधि:

y := 1; i := l - 1
while i > -1 do
    if ni = 0 then
        y := y2' i := i - 1
    else
        s := max{i - k + 1, 0}
        while ns = 0 do
            s := s + 1
        for h := 1 to i - s + 1 do
            y := y2
        u := (ni, ni-1, ..., ns)2
        y := y * xu
        i := s - 1
return y

मोंटगोमरी की सोपान तकनीक

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

Given the binary expansion of a positive, non-zero integer n = (n_k−1...n₀)₂ with n_k−1 = 1, we can compute xⁿ as follows:

x1 = x; x2 = x2
for i = k - 2 to 0 do
    if ni = 0 then
        x2 = x1 * x2; x1 = x12
    else
        x1 = x1 * x2; x2 = x22
return x1

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

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

फिक्स्ड-बेस घातांक

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

याओ की विधि

याओ की 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₀...x^b_w−1 उपरोक्त रूप में लिखा गया है, अवयव xⁿ की गणना नीचे एल्गोरिथम का उपयोग करके की जाती है:

y = 1, u = 1, j = h - 1
while j > 0 do
    for i = 0 to w - 1 do
        if ni = j then
            u = u × xbi
    y = y × u
    j = j - 1
return y

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

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

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

कंप्यूटिंग के लिए यह तरीका $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₁ द्वारा n₀ का उपयोग भागफल लौटाने के लिए किया जाता है q और विराम n₁ mod n₀.

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

Begin loop
    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}$.
    Break loop 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}$.
End loop;
Return $x^{n}=x_{M}^{n_{M}}$.

The algorithm first finds the largest value among the n_i and then the supremum within the set of { n_i \ i ≠ M }. Then it raises x_M to the power q, multiplies this value with x_N, and then assigns x_N the result of this computation and n_M the value n_M modulo 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^2k−1, बाइनरी विधि k−1 की आवश्यकता है, गुणन और k−1 वर्ग k हालांकि कोई प्रदर्शन कर सकता था, प्राप्त करने के लिए वर्ग x^2k और x⁻¹ प्राप्त करने के लिए फिर से गुणा करें।

इसके लिए हम एक पूर्णांक के हस्ताक्षरित अंकों के प्रतिनिधित्व को 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$; यह अभी भी हैमिंग वजन को कम करता है।

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

Main article: जोड़-श्रृंखला घातांक

स्क्वेरिंग द्वारा प्रतिपादक को एक सबऑप्टिमल अतिरिक्त-श्रृंखला घातांक एल्गोरिथम के रूप में देखा जा सकता है: यह घातांक की गणना एक अतिरिक्त श्रृंखला द्वारा करता है जिसमें बार-बार घातांक दोहरीकरण (स्क्वायरिंग) और/या केवल एक (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 गुणक³ का पुन: उपयोग किया जाता है)।

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

यह भी देखें

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