快速同餘演算法

Ⅰ 同餘的計算方法

同餘的計算方法只要根據公式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搪塞，我對現在演算法普及程序感到非常的失望，很傷心。

一樓我不明白的就是你怎麼估計？相當於你說你去買份飯沒說怎麼做，相當模糊，樓主要的是具體的演算法。