快速同余算法

Ⅰ 同余的计算方法

同余的计算方法只要根据公式a=qm+b，即a≡b(modm)，然后你就可以计算出与a同余的数字是几。
望采纳。

Ⅱ 算法：同余除法的解

把你的问题陈述清楚一点，你是要找出这个数a还是要求(a div s) mod q的值？

Ⅲ 求一个高效的指数取模运算算法

由于一个整数的指数结果很大，可能远远超出计算机处理范围，故必须简化计算方式．这里采用快速取模方法.原理为：在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;
} (参考网络）

Ⅳ 怎样实现大数快速模运算

大多数的编译器只能支持到64位的整数运算，即我们在运算中
所使用的整数必须小于等于64位，即：0xffffffffffffffff
也就是18446744073709551615，这远远达不到RSA的需要，于是
需要专门建立大数运算库来解决这一问题。

最简单的办法是将大数当作字符串进行处理，也就是将大数用
10进制字符数组进行表示，然后模拟人们手工进行“竖式计算”
的过程编写其加减乘除函数。但是这样做效率很低，因为1024
位的大数其10进制数字个数就有数百个，对于任何一种运算，
都需要在两个有数百个元素的数组空间上做多重循环，还需要
许多额外的空间存放计算的进位退位标志及中间结果。当然其
优点是算法符合人们的日常习惯，易于理解。

另一种思路是将大数当作一个二进制流进行处理，使用各种移
位和逻辑操作来进行加减乘除运算，但是这样做代码设计非常
复杂，可读性很低，难以理解也难以调试。

Ⅳ 求解一次同余式

题：求解同余式35x==1 mod 97，问怎么用最大公因数的性质求解。
注意： mod 的本质是 0类剩余类。即a mod m= a + 0 mod m= a + [0] = a+ m**，[0]表示m的余数为0的剩余类，简称0类剩余类，**表示任意可变的整数值。]

题目转化：求解不定方程35x=1+97y
解一：
35x=1+97y
35z=1-8y 注：将35的倍数集中到35x上并改用新变量
3z=1-8w 注：将8的倍数集中到8y上并改用新变量
由此立即看出可取特解z=3,w=-1,逆即得特解。
下面提出一种利于快速计算（特别是手算、口算心算）的细节算法将上面三个式子中的两邻的进行比较得
x-z=3y
4z=-y+w
故y=-4z+w=-13,x=z+3y=-36
即原同余式的解为x==-36==61 mod 97

验算：开始菜单-运行-calc(即打开windows计算器)-alt_CS(查看-科学型)，将
(35*(-36) % 97)
复制到其中，得到结果是 -96==1 mod 97.

解二：
引理：
存在x,y使得 ax+by=gcd(a,b)， 这里a,b,x,y全为整数。
注：gcd表示最大公约数great common divisor. 我们一般用辗转相除法求得最大公因数。
35与97的最大公因数为 1，下面用辗转相除法。

97=-8+35a, a=3;
35=3+8b, b=4;
8=-1+3c, c=3
由后两式消去除数3，得 8=-1+(35-8b)c，
归并除数8相关的项，得8(1+bc)=-1+35c
再与第一式联立消去除数8相关的项，得(35a-97)(1+bc)=-1+35c
于是35(a+abc-c)-97(1+bc)=-1
与35x==1 mod 97比较，知解
x==-(a+abc-c)=-36 mod 97
此即所求。

解三：（广义）连分数法。这个方法与解二原理相当，利用连分数的性质，过程很简洁。
97=35*3-8
35=4*8+3
8=3*3-1
故
97/35=3-1/(4+1/(3-1/3))=[3; -1:4; 1:3; -1:3]
[3; -1:4; 1:3]=3-1/(4+1/3)=3-3/13=36/13
故97*13-35*36=1
即35x==1 mod 97的解为
x==-36 mod 97

注：我定义广义连分数：
[Z；A1:B1,A2:B2,...]= Z+A1/(B1+A2/(B2+A3/(B3+...))),其中Z,Ai,Bi为整数，可以为负整数。

Ⅵ 线性同余算法一般认为2∧k-1比2∧k要好,这是为什么

线性同余算法一般认为2∧k-1比2∧k要好,这是为什么？算出结果就行。

Ⅶ 求同余幂的算法复杂度

太模糊了，你再表达清楚点

Ⅷ 多元一次同余方程解法

同余方程的中国标准解法就是孙子算法。每一项由其余所有项的除数的最小公倍数的整数倍除以本项除数余1的最小值乘以本项的余数值，所有项之和，是一个解;这个解减去所有除数的最小公倍数，得到最小的正整数，为最小正整数解。最小正整数解加减所有除数最小公倍数的任意整数倍，得到所有的解。最有名的例题是:三人同行七十希，五树梅花廿一枝，七子团圆整半月，除百零五便得知。
除3余x，除5余y，除7余z，通解
70x十21y十15z
70是5,7的倍数，除3余1;
21是3,7的倍数，除5余1;
15是3,5的倍数，除7余1。
3,5,7的最小公倍数105，减若干105的倍数，得到小于105的正整数，是最小正整数解。加减105的整数倍，得到所有解。

Ⅸ 大数快速求模算法

楼上的全不明白楼主的意思，楼主要的是算法，不是程序你们懂吗！！！
我只能说你们不懂什么叫真正的算法，你们只是计算机的傀儡，我看了你们回答非常生气，高校教出来的就是这种“人才”，连算法都不懂。还不如我一高中生。严重BS楼上的，尤其是说java语言的那位。

我来告诉你
这个问题用递推解决
首先要你承认一个公式，我是习惯pascal语言的，c++怕写错，反正只是算法，你忍一下。

不知道你要的算法是大整数对long取余还是大整数对大整数取余。

先说对long取余，这个简单
先承认两个公式:ab mod c=((a mod c)(b mod c)) mod c
(a+b) mod c=(a mod c+b mod c) mod c

然后递推，先算1 mod c,然后10 mod c ,100 mod c。。。用数组存一下，递推方法是10^n mod c=((10^(n-1) mod c)*10) mod c

再加，让k=0,
for a:=1 to l do
k:=(k+num[a]*exp10[a]) mod c

这样最后k就是结果。

补充：我不知道你说哪里耗时间，这个算法是位数的一次函数。

再说大整数对大整数取余，这个需要模仿你平常做的除法来做高精度除法，说明白了就是模拟除法，这个没什么好说的，只要你编程能力足够就写得出来，你可以上网上搜一下，我这就不写了，因为我也不能保证一次写对，因为写一个高精度除法需要高精度加法和乘法，代码稍微有点繁。

不bs楼上的了，我错了。lrj当然认识，见过他很多回了。我不是你说的那种被动接受的人，我们学校没有人懂，全部都是自学的，看到了你说用java解决很生气而己，楼主的意思是算法。
至于oier，我们都很崇拜lrj，市面上基本没有什么适合初学者的书，资来源是网络。
像很多高校，教出来的学计算机系的“程序员”根本不懂算法，导致很多程序效率低下，比如我曾看到一个ip地址数据库这位“牛”用o(n)的算法扫描找对应的ip地址，然后改成其它方法了居然还很高兴地说现在10几次就可以确定了。再比如我们的“老师”，从学校计算机系毕业，来了什么也不懂，最垃圾的模拟都不会，背包都不知道是啥，所以我内心里对一些人排斥。对不起。
但是有一点我不认同，不是大多数的oier都像你说的那样。
还有，就是我很不喜欢你的明白楼主是什么意思却不去回答而用java塘塞过去。
那不是狂妄，那是失望。这种问题竟然要等到我一个高中生来回答，而上面竟然又有人用java搪塞，我对现在算法普及程序感到非常的失望，很伤心。

一楼我不明白的就是你怎么估计？相当于你说你去买份饭没说怎么做，相当模糊，楼主要的是具体的算法。