Can you summarize the following document?
        
  該方法是基於觀察到,對於正整數formula_1,我們有  該方法使用指數的位(二進位制的位,即bit,下文稱為“位”)來確定計算哪些冪。  此例顯示如何使用此方法計算 formula_3。 冪指數13的二進位制為1101。這些位按照從左到右的順序使用。 指數有4位,所以有4次迭代。  首先,將結果初始化為1:formula_4  這可以按照下面的遞迴演算法來實現: 儘管不是尾呼叫,但是通過引入輔助函式,該演算法可以被重寫成尾遞迴演算法:  該演算法的迭代版本的輔助空間是有界的,程式碼如下

  簡要分析表明此演算法用了 formula_12 次平方,以及至多 formula_12 次乘法,其中 formula_14 表示向下取整函式。更確切地說,做乘法的次數比 "n" 的二進位制展開的次數要少一次。對於 "n" 大於4左右的時候,這種演算法在計算上就已經比"天真地"將它與自身重複地相乘更高效了。  每次平方的結果大約是前一次結果的兩倍,因此,如果兩個 "d" 位數的相乘的實現要進行 O("d") 次計算(其中 "k" 為一固定值),那麼計算 "x" 的複雜度為:

  此演算法先把指數展開成 2 形式,然後再計算 x 的值。它在1939年由Brauer首次提出。在下面的演算法中,我們使用以下函式 f(0) = (k,0) 和 f(m) = (s,u),其中 m = u·2,"u" 為奇數。  演算法:  為了獲得最佳效率,"k" 應該是滿足  的最小整數。

  此方法是 2 法的更高效的變體。例如,要計算398次冪,二進位制展開為 (110 001 110),我們採用長度為3的窗,使用 2 法,需要計算 1, x, x, x, x, x, x, x, x, x, x, x。 但我們也可以計算 1, x, x, x, x, x, x, x, x, x, x,這就會省下一次乘法,相當於是計算 (110 001 110)n 的值  以下是一般演算法:  演算法:  演算法:

  求冪的許多演算法都不提供對旁路攻擊的防護。也就是說,監測到乘方運算的攻擊者可以(部分)還原所計算的指數。就如眾多公鑰加密系統中那樣,如果指數需要保密的話,這就是個問題了。一個叫做蒙哥馬利階梯的方法解決了這個問題。  給定一個非零正整數的二進位制展開 n=(n...n)(其中 n=1),我們可以以下面方式計算 x:  該演算法會執行一系列固定的操作(複雜度log n):無論每一位的具體值如何,指數中的每一位都會進行乘法和平方。  蒙哥馬利階梯法的這種具體實現還無法抵禦快取時序攻擊:當根據祕密指數的位值訪問不同的變數時,記憶體訪問延遲仍可能被攻擊者觀察到。

  當基底固定而指數變化時,可以使用幾種方法來計算 x。可以看出,預計算在這些演算法中起著關鍵作用。

  姚期智的方法與 法不同,是把指數以 為基底展開,並按上面的演算法進行計算。令,,, 為整數。  把指數 寫成  令 。該演算法使用等式  給定 的元素,指數 寫成上述形式,並且預先計算 的值,元素 就可以用下面的演算法計算了。  如果我們令,,那麼這些 就是 以 為基的每一位。姚期智的方法是把之前的那些 收集到 u 中,which appear to the highest power ;in the next round those with power are collected in as well etc. 變數 y 被原始的 乘了 次,內第二高的指數乘了 次...... 該演算法計算 要用 次乘法,儲存 個元素。

  歐幾里德法首先在P.D Rooij的《使用預計算和向量加法鏈的高效求冪》(英語:Efficient exponentiation using precomputation and vector addition chains)中介紹。  這種計算群 中 formula_23( 為自然數)的方法是,遞迴地使用下面的等式:  給定群 中的基底元素,把指數 formula_1 用姚期智的方法寫出來,然後就可以用預計算的 formula_27 個值 formula_28 計算 formula_23 了。  該演算法首先在 中找到最大值,在找到集合 中的最大值。 然後遞迴求 的 次冪,把這個值乘以,賦值給 ;把 模 的結果賦值給 。

  這一思路還可用於計算大指數冪除以一個數的餘數。特別是在密碼學中,在整數除以"q"的餘數的環中計算冪是很有用處的。在群中計算整數冪也是很有用的,使用法則  該方法對所有半群都適用,通常用於計算矩陣的冪。  例如,如果使用樸素的方法,計算  將花費很長時間以及大量的儲存空間:計算 13789,併除以2345求餘。即便使用更有效的方法也需要很長時間:求13789的平方,除以2345求餘,將結果乘以13789,再求餘,一直往下計算。這會需要 formula_30 次模乘。  把“*”理解為 "x"*"y" = "xy" mod 2345(即相乘後取模)後,應用上面的平方求冪演算法,只需要27次乘法和整數除法(所有這些都可以儲存在單個機器字中)就可以完成計算了。

  

  這是用Ruby寫的上述演算法的非遞迴實現。  由於低階語言會將 n=n/2 隱式向0取整,n=n-1 對那些語言來說,就是冗餘的步驟了。 n[0]是n的二進位制表示的最右邊的位,所以如果它是1,則該數是奇數,如果它是零,則該數是偶數。它也是以2為模n的餘數。

  parameter x = 3

  result := 3  JavaScript-Demonstration: http://home.mnet-online.de/wzwz.de/temp/ebs/en.htm

  平方求冪也可用於計算2個或多個冪的乘積。 如果基礎群或半群是可交換的,那麼常常可以通過同時計算乘積來減少乘法的次數。

  式子 a×b 可以分三步計算: 所以總共需要八次乘法。  更快的解法是同時計算這兩個冪 總共只需要6次乘法。注意 a×b 計算了兩次;結果可以在第一次計算後儲存,這將乘法計數減少到5次。  有數字的例子:  如果至少有兩個指數大於1的話,同時計算冪就會比單獨計算減少乘法次數。

  如果表示式在計算前進行變換,上面的例子 a×b 也可以只用5次乘法就計算出來:  a×b = a×(ab) 其中 ab := a×b 這個變換可以推廣成下面的方案:<br> 對於計算 a×b×...×m×n<br> 首先:定義 ab := a×b, abc = ab×c,...<br> 然後:計算變換後的表示式 a×ab×...×abc..m×abc..mn  在計算之前進行變換通常會減少乘法計數,但在某些情況下也會增加計數(請參見下面最後一個示例),因此在使用變換後的表示式進行計算之前,最好檢查一下乘法的次數。

  對於下面的表示式,表中顯示了分開計算每個冪,在不進行變換的情況下同時進行計算,以及在變換後同時進行計算的乘法次數。

  在某些計算中,如果允許負係數(也就會需要用基底的倒數)的話,只要在 中計算倒數很快或者已經預先計算,求冪會更加高效。例如,當計算 時,二進位制方法需要 次乘法和 次平方。不過可以用 次平方得到,然後乘以 得到 。  為此,我們定義以 為基數的整數 的有符號數字表示為  Koyama和Tsuruoka的另一種演算法並不要求 formula_42 這樣的條件;它仍然可以讓漢明重量最小化。

  平方求冪可以看作是一個次優的加法鏈求冪演算法:它通過由重複指數加倍(平方)和指數遞增(乘以 "x")組成的加法鏈來計算指數。更一般地,如果允許"任何"先前計算的指數相加(通過乘以 "x" 的冪),有時可以讓求冪運算的乘法次數更少(但通常使用更多的記憶體)。"n"=15 時的最少次數:  一般來說,求給定指數的最佳加法鏈是一個難題,因為沒有已知的高效演算法,所以最優鏈通常只用於小指數(比如,在編譯器中已經預先儲存了小指數冪的最佳鏈)。不過,有一些啟發式演算法,雖然不是最優的,但是由於額外的簿記工作和記憶體使用量的增加而導致的乘法次數少於平方求冪。無論如何,乘法的次數永遠不會比 Θ(log "n") 增長得更慢,所以這些演算法只能減小平方求冪的漸進複雜度的常數因子。
在數學和程式設計中,平方求冪(英語:exponentiating by squaring)或快速冪是快速計算一個數(或更一般地說,一個半群的元素,如多項式或方陣)的大正整數冪的一般方法。這些演算法可以非常通用,例如用在模算數或矩陣冪。對於通常使用加性表示法的半群,如密碼學中使用的橢圓曲線,這種方法也稱為double-and-add。