模指數高次冪運算簡便演算法

❶ 什麼是模冪乘

模冪乘運算採用平方乘演算法，將模冪乘運算轉化為模乘和模平方運算實現． 平方-乘演算法：一般地，求S=ABmodN，其中A<N，B<N；將指數B表示為二進制，即 觀察演算法，由於指數B化為二進制後的長度不確定，多數情況下高位會存在很多個0．如果完全按照該演算法實現，指數B從最高位起開始運算，在第一個1出現以前，雖進行了多次運算，但D的值一直為1；當B出現第一個1後才進入有效的模乘運算．在具體實現時，設計專門的電路從高到低掃描指數B的每一位，當在找到第一個1之前，不做任何運算，找到第一個1時，使D=A，以後根據每次掃描的6[i]值，調用模乘實現運算． 經過對多種公鑰加解密演算法的分析——如RSA演算法，通常公鑰的有效位較短，而私鑰有效位較長．加密中的模冪乘運算，指數有效位很少，所以上面的改進可大大減少模乘次數，加快加密過程．以目前常用的私鑰和模數1 024 bit，公鑰128bit情況為例，採用上述改進可減少896次不必要的模乘．解密過程使用中國余數定理(CRT)，可有效降低解密指數的長度，整個演算法的執行效率得到進一步提高． 2．2 模乘及模加的實現方法 模乘採用改進的Blakley加法型演算法，原理與平方-乘演算法類似，核心是將模乘轉化為模加實現．如通常S=(A×B)modN，A<N，B<N可以按如下方式考慮． 將B表示成二進制： 由上式可知，可以像平方一乘演算法一樣，將模乘轉化為模加實現． 一般模加運算表示為S=(A+B)modN，觀察以上模乘及模冪乘演算法原理描述，可知在其調用的模加運算中，因為A<N且B<N，則(A+B)<2N，所以， 因此考慮在運算中同時計算(A+B)和(A+B-N)兩個結果，運算完成後通過判斷加法器與減法器的進位輸出(CO)與借位輸出(BO)．決定哪個為本次模加的正確結果．同上，A，B，N均為l位的二進制數，若CO=1，則說明(A+B)為l+1位二進制數，必大於l位的N；若CO=0，則(A+B)和N同為l位，當BO=1時(A+B)<N，當BO=0時N≤(A+B)． 從而可以在一次運算中完成加法和求模過程，使模加的運算速度提高1倍．

❷ 快速冪演算法原理

快速冪
顧名思義，快速冪就是快速算底數的n次冪。其時間復雜度為 O(log2N)， 與樸素的O(N)相比效率有了極大的提高。

中文名
快速冪
外文名
Fast Power
時間復雜度
log(n)
性質
快速算底數的n次冪
快速
導航
實現

代碼比較
原理
快速冪演算法的核心思想就是每一步都把指數分成兩半，而相應的底數做平方運算。這樣不僅能把非常大的指數給不斷變小，所需要執行的循環次數也變小，而最後表示的結果卻一直不會變。
讓我們先來看一個簡單的例子：
3^10=3*3*3*3*3*3*3*3*3*3
3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)
3^10=(3*3)^5
3^10=9^5
9^5=（9^4）*（9^1）
9^5=（9^4）*（9^1）
9^5=（6561^1）*(9^1)
以下以求a的b次方來介紹[1]
把b轉換成二進制數。
該二進制數第i位的權為
例如

11的二進制是1011

因此，我們將a11轉化為算
實現
快速冪可以用位運算來實現
b and 1{也就是取b的二進制最低位(即第0位)判斷b是否為奇數，是則為1}
b shr 1{就是去掉b的二進制最低位(即第0位)}
C++實現為
b & 1//取b二進制的最低位，判斷和1是否相同，相同返回1，否則返回0，可用於判斷奇偶
b>>1//把b的二進制右移一位，即去掉其二進制位的最低位
以下為pascal的實現：
var a,b,n:int64;
function f(a,b,n:int64):int64;
var t,y:int64;
begin
t:=1; y:=a;
while b<>0 do begin
if(b and 1)=1 then t:=t*y mod n;
y:=y*y mod n;{這里用了一個技巧,y*y即求出了a^(2^(i-1))不知道這是什麼的看原理
a^(2^(i-1))*a^(2^(i-1))=a^(2^i)
而且一般情況下a*b mod c =(a mod c)*(b mod c) mod c}
b:=b shr 1;{去掉已經處理過的一位}
end;
exit(t);
end;
begin
read(a,b,n);{n是模}
writeln(f(a,b,n));
end.
[1]
以下為C的實現，為了方便與pascal的對照，變數全部與上面相同.可以對照查看。
遞歸版：[2]
ll pow(ll a,ll i){
if (i==0) return 1;
int temp=pow(a,i>>1);
temp=temp*temp%MOD;
if (i&1) temp=(ll)temp*a%MOD;
return temp%MOD;
}
非遞歸版：
ll f(ll a,ll b,ll n){
int t,y;
t=1; y=a;
while (b!=0){
if (b&1==1) t=t*y%n;
y=y*y%n; b=b>>1;
}
return t;
}

❸ 2道冪運算數學簡便方法計算題

1、(-3)2009次冪+3的2010次冪
=-3^2009+3*3^2009
=(-1+3)*3^2009
=2*3^2009
2、（5/4)2010次冪×（-4/5)2009次冪
=（5/4)^2009×(5/4)×（-4/5)^2009
=((5/4)×（-4/5))^2009×(5/4)
=(-1)^2009×(5/4)
=-5/4
3、已知一列數
2，9，28,65,126，x排列有一定的規律性，則x為（d
）
a.257
b.191
c.301
d.217
規律:
n^3+1

❹ 高次冪(如3次)因式分解技巧

1、提公因法

如果一個多項式的各項都含有公因式，那麼就可以把這個公因式提出來，從而將多項式化成兩個因式乘積的形式。

例：分解因式x -2x
-x

x -2x -x=x(x -2x-1)

2、應用公式法

由於分解因式與整式乘法有著互逆的關系，如果把乘法公式反過來，那麼就可以用來把某些多項式分解因式。

例：分解因式a
+4ab+4b

a +4ab+4b =（a+2b）

3、 分組分解法

要把多項式am+an+bm+bn分解因式，可以先把它前兩項分成一組，並提出公因式a，把它後兩項分成一組，並提出公因式b，從而得到a(m+n)+b(m+n)，又可以提出公因式m+n，從而得到(a+b)(m+n)

例：分解因式m
+5n-mn-5m

m +5n-mn-5m= m -5m -mn+5n

= (m -5m )+(-mn+5n)

=m(m-5)-n(m-5)

=(m-5)(m-n)

4、 十字相乘法

對於mx +px+q形式的多項式，如果a×b=m，c×d=q且ac+bd=p，則多項式可因式分解為(ax+d)(bx+c)

例：分解因式7x
-19x-6

分析： 1 -3

7 2

2-21=-19

7x -19x-6=（7x+2）(x-3)

5、配方法

對於那些不能利用公式法的多項式，有的可以利用將其配成一個完全平方式，然後再利用平方差公式,就能將其因式分解。

例5、分解因式x
+3x-40

解x +3x-40=x +3x+( ) -( ) -40

=(x+ ) -( )

=(x+ + )(x+ - )

=(x+8)(x-5)

❺ 求一個高效的指數取模運算演算法

由於一個整數的指數結果很大，可能遠遠超出計算機處理范圍，故必須簡化計算方式．這里採用快速取模方法.原理為：在4的5次方運算中，5能夠化作2*2+1，這是因為5的2進制數為101．所以4的5次方運算便能寫作((4)^2*1)^2*4,其中1表示的是4的0次方，^2表平方．再運用模的性質：(a*b)mod(m)=(amod(m)*bmod(m))mod(m),所以（4^5）mod(m)可先化為（((4)^2*1)^2*4）mod(m)，再化為（((4)^2mod(m)*1)^2mod(m)*4）mod(m)．舉例子－－（4^5）mod(3)＝（((4)^2*1)^2*4）mod(3)＝（(1*1)^2mod(3)*4）mod(3)=（1*4）mod(3)＝1．該函數運行方式取於上述演算法思想，首先將冪分解成2進制數，得到一個從冪的最低位數開始01組成的棧：分解b為2進制數．記錄下分解成的位數z，構造棧
for(;b!=1;b>>=1)
{
z++;
if(b%2==0) l[z]=0;
else l[z]=1;｝
然後出棧進行＂（a^b）mod(c)＂的運算．這里用棧的原因是為了使冪的2進制數排列倒過來，實現最高位上的2進制數能夠循環它的位數次，最低位上的2進制數只循環一次．每次的循環得到平方取模的值，一直到結束，取得一個值，即（a^b）mod(c)．
for(;z>0;z--)
{
if(l[z]) y=(y*a%c)*(y*a%c)%c;
else y=y*y%c;
}
if(l[0]) y=(y*a%c);//最後次模
return y;
這是一個比較快的運算方法.
完整源程序：
//指數取模:a的b次方modc=x
_int64 mod(_int64 a,_int64 b,_int64 c)//(a)^bmod(c)//條件1：在rsa中a<c,其它不用a<c.條件2:ac互素
{
_int64 l[500],z=-1,y;
for(;b!=1;b>>=1)//分解b為2進制數．記錄下分解成的位數z，構造棧l
{
z++;
if(b%2==0) l[z]=0;
else l[z]=1;
}
//a%=c;//如果一開始數就很大，先模一次,防止過大, 求逆
y=a*a%c;//第一次模
for(;z>0;z--)
{
if(l[z]) y=(y*a%c)*(y*a%c)%c;
else y=y*y%c;
}
if(l[0]) y=(y*a%c);//最後次模
return y;
}

C#改寫的，在vs.net 2005下調試通過：
/// <summary>
/// 指數取模:x=(a^b)%c （a的b次方mod）
/// 條件1：在rsa中a<c,其它不用a<c
/// 條件2:ac互素
/// </summary>
private static long mod(long a, long b, long c)
{
long[] l = new long[500];
long z = -1, y;
for (; b != 1; b >>= 1)//分解b為2進制數．記錄下分解成的位數z，構造棧l
{
z++;
if (b % 2 == 0)
l[z] = 0;
else
l[z] = 1;
}
//a%=c;//如果一開始數就很大，先模一次,防止過大, 求逆
y = a * a % c;//第一次模
for (; z > 0; z--)
{
if (l[z]>0) y = (y * a % c) * (y * a % c) % c;
else y = y * y % c;
}
if (l[0]>0) y = (y * a % c);//最後次模
return y;
} (參考網路）

❻ 指數冪的運演算法則是什麼

(1)任何不等於零的數的零次冪都等於1。

即(a≠0)。

(2)任何不等於零的數的-p（p是正整數）次冪，等於這個數的p次冪的倒數。

即(a≠0,p是正整數)。

（規定了零指數冪與負整數指數冪的意義，就把指數的概念從正整數推廣到了整數。正整數指數冪的各種運演算法則對整數指數冪都適用。）

1.同底數冪相乘，底數不變，指數相加。

即（m,n都是有理數）。

2.冪的乘方，底數不變，指數相乘。

即（m,n都是有理數）。

3.積的乘方，等於把積的每一個因式分別乘方，再把所得的冪相乘。

即＝·(m,n都是有理數）。

4.分式乘方，分子分母各自乘方

即（b≠0)。

除法

1.同底數冪相除，底數不變，指數相減。

即（a≠0，m,n都是有理數）。

❼ 次冪 計算題 簡便

1、(-3)2009次冪+3的2010次冪
=-3^2009+3*3^2009
=(-1+3)*3^2009
=2*3^2009

2、（5/4)2010次冪×（-4/5)2009次冪
=（5/4)^2009×(5/4)×（-4/5)^2009
=((5/4)×（-4/5))^2009×(5/4)
=(-1)^2009×(5/4)
=-5/4

3、已知一列數 2，9，28,65,126，X排列有一定的規律性，則X為（D ）
A.257 B.191 C.301 D.217
規律: n^3+1

❽ 一個數的幾次方怎麼算有簡便的方法嗎

一個數的幾次方計算就是用幾個相同的這個數相乘。有簡便方法，把這個次方分解。

分析過程如下：

如求：2的4次方。

2的4次方就是：2×2×2×2，通過整數的乘法計算可得：2^4=16。

簡便方法舉例，如求2^8。

2^8=2^4×2^4=16×16=256。

(8)模指數高次冪運算簡便演算法擴展閱讀：

指數的運演算法則：

1、[a^m]×[a^n]=a^(m＋n) 【同底數冪相乘,底數不變,指數相加】

2、[a^m]÷[a^n]=a^(m－n) 【同底數冪相除,底數不變,指數相減】

3、[a^m]^n=a^(mn) 【冪的乘方,底數不變,指數相乘】

4、[ab]^m=(a^m)×(a^m) 【積的乘方,等於各個因式分別乘方,再把所得的冪相乘】

常用平方數：

1² = 1， 2² = 4 ，3² = 9， 4² = 16， 5² = 25， 6² = 36 ，7² = 49 ，8² = 64 ，9² = 81 ，10² = 100。

11² = 121， 12² = 144 ，13² = 169 ，14² = 196 ，15² = 225， 16² = 256， 17² = 289 ，18² = 324， 19² = 361 ，20² = 400。

❾ 如何進行冪模運算

模冪乘運算採用平方乘演算法，將模冪乘運算轉化為模乘和模平方運算實現．
平方-乘演算法：一般地，求S=ABmodN，其中A<N，B<N；將指數B表示為二進制，即
觀察演算法，由於指數B化為二進制後的長度不確定，多數情況下高位會存在很多個0．如果完全按照該演算法實現，指數B從最高位起開始運算，在第一個1出現以前，雖進行了多次運算，但D的值一直為1；當B出現第一個1後才進入有效的模乘運算．在具體實現時，設計專門的電路從高到低掃描指數B的每一位，當在找到第一個1之前，不做任何運算，找到第一個1時，使D=A，以後根據每次掃描的6[i]值，調用模乘實現運算．
經過對多種公鑰加解密演算法的分析——如RSA演算法，通常公鑰的有效位較短，而私鑰有效位較長．加密中的模冪乘運算，指數有效位很少，所以上面的改進可大大減少模乘次數，加快加密過程．以目前常用的私鑰和模數1 024 bit，公鑰128bit情況為例，採用上述改進可減少896次不必要的模乘．解密過程使用中國余數定理(CRT)，可有效降低解密指數的長度，整個演算法的執行效率得到進一步提高．
2．2 模乘及模加的實現方法
模乘採用改進的Blakley加法型演算法，原理與平方-乘演算法類似，核心是將模乘轉化為模加實現．如通常S=(A×B)modN，A<N，B<N可以按如下方式考慮．
將B表示成二進制：
由上式可知，可以像平方一乘演算法一樣，將模乘轉化為模加實現．
一般模加運算表示為S=(A+B)modN，觀察以上模乘及模冪乘演算法原理描述，可知在其調用的模加運算中，因為A<N且B<N，則(A+B)<2N，所以，
因此考慮在運算中同時計算(A+B)和(A+B-N)兩個結果，運算完成後通過判斷加法器與減法器的進位輸出(CO)與借位輸出(BO)．決定哪個為本次模加的正確結果．同上，A，B，N均為l位的二進制數，若CO=1，則說明(A+B)為l+1位二進制數，必大於l位的N；若CO=0，則(A+B)和N同為l位，當BO=1時(A+B)<N，當BO=0時N≤(A+B)．
從而可以在一次運算中完成加法和求模過程，使模加的運算速度提高1倍．

❿ 高次冪計算

1.01的365次方=37.783434332………………
1.01的1825次方=77002912.7505523…………………
電腦的系統自帶計算器中的科學型就能運算.