模指数高次幂运算简便算法

❶ 什么是模幂乘

模幂乘运算采用平方乘算法，将模幂乘运算转化为模乘和模平方运算实现． 平方-乘算法：一般地，求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…………………
电脑的系统自带计算器中的科学型就能运算.