段學(xué)松，曲中水，江緒楨，呂昌昊

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

1 概述

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

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

2.1 二進(jìn)制拆分法的原理

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

通過(guò)乘法原理，可以得到：

綜上，可以得到：

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

2.2 二進(jìn)制拆分快速冪算法的時(shí)間復(fù)雜度與空間復(fù)雜度分析

T（n）=O（log2n）

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

S（n）=O（1）

如果計(jì)算k 次，總時(shí)間復(fù)雜度為：

T（n）=O（klog2n）

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

總空間復(fù)雜度為：

S（n）=O（1）

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

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

2.4 多次計(jì)算時(shí)二進(jìn)制拆分法的重復(fù)運(yùn)算

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

3 基于預(yù)處理的快速冪算法

3.1 基于預(yù)處理的快速冪算法原理

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

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

證畢。

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

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

3.2 基于預(yù)處理的快速冪乘算法的時(shí)間復(fù)雜度與空間復(fù)雜度分析

3.2.1 預(yù)處理過(guò)程時(shí)間與空間復(fù)雜度分析

因?yàn)橥ㄟ^(guò)預(yù)處理能夠得到aP，因此，預(yù)處理（aP）0，（aP）1，（aP）2…（aP）P-1，（aP）P的時(shí)間復(fù)雜度：

所以，預(yù)處理的總時(shí)間復(fù)雜度：

3.2.2 計(jì)算快速冪的時(shí)間與空間復(fù)雜度分析

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

T（n）=O（1）

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

S（n）=O（1）

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

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

總體空間復(fù)雜度為：

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

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

4 結(jié)束語(yǔ)

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