段學松，曲中水，江緒楨，呂昌昊

（哈爾濱理工大學 計算機科學與技術(shù)學院，黑龍江 哈爾濱 150080）

1 概述

快速冪算法，即快速計算一個數(shù)或者矩陣的冪次的算法，一直是加密算法中的重要算法，并且在數(shù)論中有著相當廣泛的應(yīng)用，更是算法競賽中最常遇到的問題，尤其在線性齊次遞推數(shù)列[1]的求解上。例如常見的斐波那契數(shù)列[1]第n 項的計算，通過構(gòu)造轉(zhuǎn)移矩陣[1]和快速計算矩陣冪次[1]的方式能夠大大降低計算線性齊次遞推數(shù)列的時間復雜度。但是隨著矩陣的行數(shù)和列數(shù)不斷增加，每一次矩陣乘法會變得相當耗時，對于稀疏矩陣，雖然存在優(yōu)化算法[2]，甚至存在優(yōu)化算法的硬件實現(xiàn)[3]，但是如何減少矩陣乘法計算的次數(shù)變得極其重要。目前計算快速冪，最常用的算法是二進制拆分法[4]，但是對于一個固定的數(shù)或者是固定矩陣的冪次來說，二進制拆分法并沒有保留每次拆分的過程，導致拆分的過程會做大量的重復計算。因此對于固定的數(shù)或者固定矩陣的冪次，可以預處理部分數(shù)據(jù)，達到減少重復運算，降低算法時間復雜度的目的。

2 傳統(tǒng)的二進制拆分快速冪算法概述

2.1 二進制拆分法的原理

計算an，傳統(tǒng)的快速冪算法的核心思想是二進制拆分。令m 為n 在二進制下最高位1 的位置，我們對n 進行二進制拆分，則有：

通過乘法原理，可以得到：

綜上，可以得到：

其中，ei是n 在二進制下第i 位的值，例如當n=13的時候，n 的二進制形式為：（1101）2，最高位 1 的位置 m=4，對n 進行二進制拆分得到的結(jié)果為：

2.2 二進制拆分快速冪算法的時間復雜度與空間復雜度分析

T（n）=O（log2n）

由于二進制拆分快速冪算法用迭代實現(xiàn)，在計算的過程中用于存儲計算用到的空間是常數(shù)級別的，因此二進制拆分快速冪算法的空間復雜度為：

S（n）=O（1）

如果計算k 次，總時間復雜度為：

T（n）=O（klog2n）

金壇區(qū)于2016年啟動長蕩湖清淤工程，在外源污染有效治理和控制的前提下，通過對長蕩湖湖區(qū)污染底泥實施生態(tài)清淤，有效削減底泥內(nèi)源污染，促進湖泊水體水質(zhì)改善，為長蕩湖水生態(tài)修復奠定基礎(chǔ)。

總空間復雜度為：

S（n）=O（1）

2.3 二進制拆分快速冪算法的C++實現(xiàn)

圖1 二進制拆分法的C++實現(xiàn)

2.4 多次計算時二進制拆分法的重復運算

當利用二進制拆分快速冪算法多次計算相同底數(shù)的冪次時，存在大量的冗余計算。例如：

3 基于預處理的快速冪算法

3.1 基于預處理的快速冪算法原理

首先我們用a mod b 表示a 對b 取余數(shù)。

證明 由取余運算的性質(zhì)[5]可得，定理1 成例。

證畢。

根據(jù)定理2 以及乘法原理可得：

由于 u∈[0，P]，v∈（0，P），因此可以在計算快速冪前預處理出 a0，a1，a2…aP-1，aP以及（aP）0，（aP）1，（aP）2…（aP）P-1，（aP）P并存儲起來，每次計算an時，首先計算出以及v=n mod P，之后從提前預處理的數(shù)據(jù)中選擇（aP）u和av進行一次乘法運算即可得到an的結(jié)果。

3.2 基于預處理的快速冪乘算法的時間復雜度與空間復雜度分析

3.2.1 預處理過程時間與空間復雜度分析

因為通過預處理能夠得到aP，因此，預處理（aP）0，（aP）1，（aP）2…（aP）P-1，（aP）P的時間復雜度：

所以，預處理的總時間復雜度：

3.2.2 計算快速冪的時間與空間復雜度分析

在計算快速冪的過程中，由于P，u，v 的計算消耗是常數(shù)級別的，而計算查表計算一次乘法的時間復雜度也是常數(shù)級別的，因此計算快速冪的時間復雜度：

T（n）=O（1）

計算過程中臨時變量的存儲空間都是常數(shù)級別的，因此計算快速冪的空間復雜度為：

S（n）=O（1）

3.2.3 計算k 次相同底數(shù)的an的總體時間空間復雜度分析

預處理的目的是去除重復運算，對于相同的底數(shù)，多次計算快速冪只用進行一次預處理操作，k 次計算快速冪的總體時間復雜度是：

總體空間復雜度為：

3.3 基于預處理的快速冪乘算法的C++實現(xiàn)

圖2 基于預處理的快速冪算法的C++實現(xiàn)

4 結(jié)束語

本文分析了二進制拆分快速冪算法的缺點，并針對相同底數(shù)的多次快速冪運算，提出了一種基于預處理的快速冪算法，通過預處理少量的數(shù)據(jù)，將時間復雜度為O（klog2n）求冪的算法優(yōu)化至并給出了該算法的時間復雜度與空間復雜度的分析以及C++編程實現(xiàn)，為求解快速冪提供了新的思路。今后，隨著程序設(shè)計應(yīng)用的不斷深入以及人們對算法的研究，更多更復雜的數(shù)學問題必定會迎刃而解。