Ⅰ c語言有關快速冪的問題
type
arrty=array[1..10000] of longint;
var
n,mn,len,lenm,i,mnl:longint;
a,m:arrty;
procere mxm;
var
c:arrty;
i,j:longint;
begin
fillchar(c,sizeof(c),0);
for i:=1 to lenm do
for j:=1 to lenm do
begin
inc(c[i+j-1],m[i]*m[j]);
inc(c[i+j],c[i+j-1] div 10);
c[i+j-1]:=c[i+j-1] mod 10;
end;
lenm:=lenm+lenm+1;
while (lenm>1) and (c[lenm]=0) do
dec(lenm);
for i:=1 to lenm do
m[i]:=c[i];
end;
procere axm;
var
c:arrty;
i,j:longint;
begin
fillchar(c,sizeof(c),0);
for i:=1 to len do
for j:=1 to lenm do
begin
inc(c[i+j-1],a[i]*m[j]);
inc(c[i+j],c[i+j-1] div 10);
c[i+j-1]:=c[i+j-1] mod 10;
end;
len:=len+lenm+1;
while (len>1) and (c[len]=0) do
dec(len);
for i:=1 to len do
a[i]:=c[i];
end;
begin
fillchar(a,sizeof(a),0);
readln(mn,n);
mnl:=mn;
len:=0;
while mnl>0 do
begin
inc(lenm);
m[lenm]:=mnl mod 10;
mnl:=mnl div 10;
end;
a[1]:=1;
len:=1;
while n>0 do
begin
if n mod 2=1 then
axm;
n:=n div 2;
mxm;
end;
for i:=len downto 1 do
write(a[i]);
writeln;
end.
Ⅱ 在C語言中,0%2=
在C語言中，0%2= 0 。
在C語言中，這是一個取模運算，定義如下：
給定一個正整數p，任意一個整數n，一定存在等式 ：
n = kp + r ；
其中 k、r 是整數，且 0 ≤ r < p，則稱 k 為 n 除以 p 的商，r 為 n 除以 p 的余數。
對於正整數 p 和整數 a,b，定義如下運算：
取模運算：a % p（或a mod p），表示a除以p的余數。
模p加法： ，其結果是a+b算術和除以p的余數。
模p減法： ，其結果是a-b算術差除以p的余數。
模p乘法： ，其結果是 a * b算術乘法除以p的余數。
說明：
1. 同餘式：正整數a，b對p取模，它們的余數相同，記做 或者a ≡ b (mod p)。
2. n % p 得到結果的正負由被除數n決定,與p無關。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。
(2)模冪演算法c語言擴展閱讀：
1、運算規則
模運算與基本四則運算有些相似，但是除法例外。其規則如下：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p)^b) % p
結合律：
((a+b) % p + c) % p = (a + (b+c) % p) % p
((a*b) % p * c)% p = (a * (b*c) % p) % p
交換律：
(a + b) % p = (b+a) % p
(a * b) % p = (b * a) % p
分配律：
(a+b) % p = ( a % p + b % p ) % p
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p
2、重要定理
若a≡b (% p)，則對於任意的c，都有(a + c) ≡ (b + c) (%p)；
若a≡b (% p)，則對於任意的c，都有(a * c) ≡ (b * c) (%p)；
若a≡b (% p)，c≡d (% p)，則 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，(a * c) ≡ (b * d) (%p)；
Ⅲ C語言取余的原理是怎麼回事 比如 int X，Y X-X/Y*Y=x%y
取余實際上就是模運算
基本理論
基本概念：
給定一個正整數p，任意一個整數n，一定存在等式 n = kp + r ；
其中k、r是整數，且 0 ≤ r < p，稱呼k為n除以p的商，r為n除以p的余數。
對於正整數p和整數a,b，定義如下運算：
取模運算：a % p（或a mod p），表示a除以p的余數。
模p加法：(a + b) % p ，其結果是a+b算術和除以p的余數，也就是說，(a+b) = kp +r，則(a + b) % p = r。
模p減法：(a-b) % p ，其結果是a-b算術差除以p的余數。
模p乘法：(a * b) % p，其結果是 a * b算術乘法除以p的余數。
說明：
1. 同餘式：正整數a，b對p取模，它們的余數相同，記做 a ≡ b % p或者a ≡ b (mod p)。
2. n % p得到結果的正負由被除數n決定,與p無關。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。
<!--[if !supportLineBreakNewLine]-->
<!--[endif]-->
基本性質
（1）若p|(a-b)，則a≡b (% p)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7)
（2）(a % p)=(b % p)意味a≡b (% p)
（3）對稱性：a≡b (% p)等價於b≡a (% p)
（4）傳遞性：若a≡b (% p)且b≡c (% p) ，則a≡c (% p)
運算規則
模運算與基本四則運算有些相似，但是除法例外。其規則如下：
(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
ab % p = ((a % p)b) % p （4）
結合率： ((a+b) % p + c) % p = (a + (b+c) % p) % p （5）
((a*b) % p * c)% p = (a * (b*c) % p) % p （6）
交換率： (a + b) % p = (b+a) % p （7）
(a * b) % p = (b * a) % p （8）
分配率： ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）
重要定理：若a≡b (% p)，則對於任意的c，都有(a + c) ≡ (b + c) (%p)；（10）
若a≡b (% p)，則對於任意的c，都有(a * c) ≡ (b * c) (%p)；（11）
若a≡b (% p)，c≡d (% p)，則 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，
(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12）
若a≡b (% p)，則對於任意的c，都有ac≡ bc (%p)； （13）
編輯本段
基本應用
1.判別奇偶數
奇偶數的判別是模運算最基本的應用，也非常簡單。易知一個整數n對2取模，如果余數為0，則表示n為偶數，否則n為奇數。
C++實現功能函數：
/*
函數名：IsEven
函數功能：判別整數n的奇偶性。能被2整除為偶數，否則為奇數
輸入值：int n，整數n
返回值：bool，若整數n是偶數，返回true，否則返回false
*/
bool IsEven(int n)
{
return (n % 2 == 0);
}
2.判別素數
一個數，如果只有1和它本身兩個因數，這樣的數叫做質數（或素數）。例如 2，3，5，7 是質數，而 4，6，8，9 則不是，後者稱為合成數或合數。
判斷某個自然數是否是素數最常用的方法就是試除法：用比該自然數的平方根小的正整數去除這個自然數，若該自然數能被整除，則說明其非素數。
C++實現功能函數：
/*
函數名：IsPrime
函數功能：判別自然數n是否為素數。
輸入值：int n，自然數n
返回值：bool，若自然數n是素數，返回true，否則返回false
*/
bool IsPrime(unsigned int n)
{
unsigned maxFactor = sqrt(n); //n的最大因子
for (unsigned int i=2; i<=maxFactor; i++)
{
if (n % i == 0) //n能被i整除，則說明n非素數
{
return false;
}
}
return true;
}
3. 最大公約數
求最大公約數最常見的方法是歐幾里德演算法（又稱輾轉相除法），其計算原理依賴於定理：gcd(a,b) = gcd(b,a mod b)
證明：a可以表示成a = kb + r，則r = a mod b
假設d是a,b的一個公約數，則有d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公約數
假設d 是(b,a mod b)的公約數，則d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公約數
因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證。
C++實現功能函數：
/*
函數功能：利用歐幾里德演算法，採用遞歸方式，求兩個自然數的最大公約數
函數名：Gcd
輸入值：unsigned int a，自然數a
unsigned int b，自然數b
返回值：unsigned int，兩個自然數的最大公約數
*/
unsigned int Gcd(unsigned int a, unsigned int b)
{
if (b == 0)
return a;
return Gcd(b, a % b);
}
/*
函數功能：利用歐幾里德演算法，採用迭代方式，求兩個自然數的最大公約數 函數名：Gcd
輸入值：unsigned int a，自然數a
unsigned int b，自然數b
返回值：unsigned int，兩個自然數的最大公約數
*/
unsigned int Gcd(unsigned int a, unsigned int b)
{
unsigned int temp;
while (b != 0)
{
temp = a % b;
a = b;
b = temp;
}
return a;
}
4．模冪運算
利用模運算的運算規則，我們可以使某些計算得到簡化。例如，我們想知道3333^5555的末位是什麼。很明顯不可能直接把3333^5555的結果計算出來，那樣太大了。但我們想要確定的是3333^5555（%10），所以問題就簡化了。
根據運算規則（4）ab % p = ((a % p)b) % p ，我們知道3333^5555（%10）= 3^5555（%10）。由於3^4 = 81，所以3^4（%10）= 1。
根據運算規則（3） (a * b) % p = (a % p * b % p) % p ，由於5555 = 4 * 1388 + 3，我們得到3^5555（%10）=（3^(4*1388) * 3^3）（%10）=（（3^(4*1388)（%10）* 3^3（%10））（%10）
=（1 * 7）（%10）= 7。
計算完畢。
利用這些規則我們可以有效地計算X^N(% P)。簡單的演算法是將result初始化為1，然後重復將result乘以X，每次乘法之後應用%運算符（這樣使得result的值變小，以免溢出），執行N次相乘後，result就是我們要找的答案。
這樣對於較小的N值來說，實現是合理的，但是當N的值很大時，需要計算很長時間，是不切實際的。下面的結論可以得到一種更好的演算法。
如果N是偶數，那麼X^N =（X*X）^[N/2]；
如果N是奇數，那麼X^N = X*X^(N-1) = X *（X*X）^[N/2]；
其中[N]是指小於或等於N的最大整數。
C++實現功能函數：
/*
函數功能：利用模運算規則，採用遞歸方式，計算X^N(% P)
函數名：PowerMod
輸入值：unsigned int x，底數x
unsigned int n，指數n
unsigned int p，模p
返回值：unsigned int，X^N(% P)的結果
*/
unsigned int PowerMod(unsigned int x, unsigned int n, unsigned int p)
{
if (n == 0)
{
return 1;
}
unsigned int temp = PowerMod((x * x)%p, n/2, p); //遞歸計算（X*X）^[N/2]
if ((n & 1) != 0) //判斷n的奇偶性
{
temp = (temp * x) % p;
}
return temp;
}
5.《孫子問題(中國剩餘定理)》
在我國古代算書《孫子算經》中有這樣一個問題：
「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？」意思是，「一個數除以3餘2，除以5餘3，除以7餘2.求適合這個條件的最小數。」
這個問題稱為「孫子問題」.關於孫子問題的一般解法，國際上稱為「中國剩餘定理」.
我國古代學者早就研究過這個問題。例如我國明朝數學家程大位在他著的《演算法統宗》（1593年）中就用四句很通俗的口訣暗示了此題的解法：
三人同行七十稀，五樹梅花甘一枝，七子團圓正半月，除百零五便得知。
"正半月"暗指15。"除百零五"的原意是，當所得的數比105大時，就105、105地往下減，使之小於105；這相當於用105去除，求出余數。
這四句口訣暗示的意思是：當除數分別是3、5、7時，用70乘以用3除的余數，用21乘以用5除的余數，用15乘以用7除的余數，然後把這三個乘積相加。加得的結果如果比105大，就除以105，所得的余數就是滿足題目要求的最小正整數解。
根據剩餘定理，我把此種解法推廣到有n(n為自然數）個除數對應n個余數，求最小被除數的情況。輸入n個除數（除數不能互相整除）和對應的余數，計算機將輸出最小被除數。
C++實現功能函數：
/*
函數名：ResieTheorem
函數功能：運用剩餘定理，解決推廣了的孫子問題。通過給定n個除數（除數不能互相整除）和對應的余數，返回最小被除數
輸入值：unsigned int devisor[]，存儲了n個除數的數組
unsigned int remainder[]，存儲了n個余數的數組
int length，數組的長度
返回值：unsigned int， 最小被除數
*/
unsigned int ResieTheorem(const unsigned int devisor[], const unsigned int remainder[], int length)
{
unsigned int proct = 1; //所有除數之乘積
for (int i=0; i<length; i++)//計算所有除數之乘積
{
proct *= devisor[i];
}
//公倍數數組，表示除該元素（除數）之外其他除數的公倍數
unsigned int *commonMultiple = new unsigned int(length);
for (int i=0; i<length; i++)//計算除該元素（除數）之外其他除數的公倍數
{
commonMultiple[i] = proct / devisor[i];
}
unsigned int dividend = 0; //被除數，就是函數要返回的值
for (int i=0; i<length; i++)//計算被除數，但此時得到的不是最小被除數
{
unsigned int tempMul = commonMultiple[i];
//按照剩餘理論計算合適的公倍數，使得tempMul % devisor[i] == 1
while (tempMul % devisor[i] != 1)
{
tempMul += commonMultiple[i];
}
dividend += tempMul * remainder[i]; //用本除數得到的余數乘以其他除數的公倍數
}
delete []commonMultiple;
return (dividend % proct); //返回最小被除數
}
6. 凱撒密碼
凱撒密碼（caeser）是羅馬擴張時期朱利斯o凱撒（Julius Caesar）創造的，用於加密通過信使傳遞的作戰命令。
它將字母表中的字母移動一定位置而實現加密。注意26個字母循環使用，z的後面可以堪稱是a。
例如，當密匙為k = 3，即向後移動3位時，若明文為」How are you!」，則密文為」Krz h btx!」。
凱撒密碼的加密演算法極其簡單。其加密過程如下：
在這里，我們做此約定：明文記為m，密文記為c，加密變換記為E(key1,m)（其中key1為密鑰），
解密變換記為D(key2,m)（key2為解密密鑰）（在這里key1=key2,不妨記為key）。
凱撒密碼的加密過程可記為如下一個變換：c≡m+key (mod n） （其中n為基本字元個數）
同樣，解密過程可表示為：m≡c+key (mod n） （其中n為基本字元個數）
C++實現功能函數：
/*
函數功能：使用凱撒密碼原理，對明文進行加密，返回密文 函數名：Encrypt
輸入值：const char proclaimedInWriting[]，存儲了明文的字元串
char cryptograph[]，用來存儲密文的字元串
int keyey，加密密匙，正數表示後移，負數表示前移
返回值：無返回值，但是要將新的密文字元串返回
*/
void Encrypt(const char proclaimedInWriting[], char cryptograph[], int key)
{
const int NUM = 26; //字母個數
int len = strlen(proclaimedInWriting);
for (int i=0; i<len; i++)
{
if (proclaimedInWriting[i] >= 'a' && proclaimedInWriting[i] <= 'z')
{//明碼是大寫字母，則密碼也為大寫字母
cryptograph[i] = (proclaimedInWriting[i] - 'a' + key) % NUM + 'a';
}
else if (proclaimedInWriting[i] >= 'A' && proclaimedInWriting[i] <= 'Z')
{//明碼是小寫字母，則密碼也為小寫字母
cryptograph[i] = (proclaimedInWriting[i] - 'A' + key) % NUM + 'A';
}
else
{//明碼不是字母，則密碼與明碼相同
cryptograph[i] = proclaimedInWriting[i];
}
}
cryptograph[len] = '\0';
}
/*
函數功能：使用凱撒密碼原理，對密文進行解密，返回明文 函數名：Decode
輸入值：char proclaimedInWriting[]，用來存儲明文的字元串
const char cryptograph[]，存儲了密文的字元串
int keyey，解密密匙，正數表示前移，負數表示後移（與加密相反）
返回值：無返回值，但是要將新的明文字元串返回
*/
void Decode(const char cryptograph[], char proclaimedInWriting[], int key)
{
const int NUM = 26; //字母個數
int len = strlen(cryptograph);
for (int i=0; i<len; i++)
{
if (cryptograph[i] >= 'a' && cryptograph[i] <= 'z')
{//密碼是大寫字母，則明碼也為大寫字母，為防止出現負數，轉換時要加個NUM
proclaimedInWriting[i] = (cryptograph[i] - 'a' - key + NUM) % NUM + 'a';
}
else if (cryptograph[i] >= 'A' && cryptograph[i] <= 'Z')
{//密碼是小寫字母，則明碼也為小寫字母
proclaimedInWriting[i] = (cryptograph[i] - 'A' - key + NUM) % NUM + 'A';
}
else
{//密碼不是字母，則明碼與明密相同
proclaimedInWriting[i] = cryptograph[i];
}
}
proclaimedInWriting[len] = '\0';
}
Ⅳ C語言里 0%2是多少
0%2=0，0%2是沒有餘數，%是表示「取余數」0除以任何數後都不會存在余數，所,以說余數為0。這是一個取模運算，在數論和程序設計中都有著廣泛的應用，奇偶數的判別到素數的判別，從模冪運算到最大公約數的求法，從孫子問題到凱撒密碼問題，無不充斥著模運算的身影。
(4)模冪演算法c語言擴展閱讀：
對於整型數a，b來說，取模運算或者求余運算的方法都是：
1、求整數商： c = [a/b];
2、計算模或者余數： r = a - c*b.
求模運算和求余運算在第一步不同: 取余運算在取c的值時，向0 方向舍入(fix()函數)；而取模運算在計算c的值時，向負無窮方向舍入(floor()函數)。
例如計算：-7 Mod 4
那麼：a = -7；b = 4；
第一步：求整數商c，如進行求模運算c = -2（向負無窮方向舍入），求余c = -1（向0方向舍入）；
第二步：計算模和余數的公式相同，但因c的值不同，求模時r = 1，求余時r = -3。
歸納：當a和b符號一致時，求模運算和求余運算所得的c的值一致，因此結果一致。
當符號不一致時，結果不一樣。
Ⅳ c語言計算一個數q的1次方到n次方的和，而q和n的數量級都是10的9次方，結果取模，怎麼減少時間呢
首先，將求和改為利用等比公式求和的公式來計算。其次，計算q的n+1次方時，使用快速冪的計算方法。為了防止溢出，每次乘積以後都先取模，再進行下一次的運算並取模。
Ⅵ c語言如何取模運算
取模運算：a % p（或a mod p），表示a除以p的余數。
比如給定一個正整數p，任意一個整數n，一定存在等式 ：n = kp + r ；其中 k、r 是整數，且 0 ≤ r < p，則稱 k 為 n 除以 p 的商，r 為 n 除以 p 的余數。
取模運算的規則如下：
1、(a + b) % p = (a % p + b % p) % p 。
2、(a - b) % p = (a % p - b % p) % p 。
3、(a * b) % p = (a % p * b % p) % p 。
4、a ^ b % p = ((a % p)^b) % p 。
(6)模冪演算法c語言擴展閱讀：
模運算與基本四則運算有些相似，但是除法例外。其規則如下：
(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
a ^ b % p = ((a % p)^b) % p （4）
結合律：
((a+b) % p + c) % p = (a + (b+c) % p) % p （5）
((a*b) % p * c)% p = (a * (b*c) % p) % p （6）
交換律：
(a + b) % p = (b+a) % p （7）
(a * b) % p = (b * a) % p （8）
分配律：
(a+b) % p = ( a % p + b % p ) % p （9）
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （10）
參考資料：網路-取模運算
Ⅶ 如何用C語言實現RSA演算法
RSA演算法它是第一個既能用於數據加密也能用於數字簽名的演算法。它易於理解和操作，也很流行。演算法的名字以發明者的名字
命名：Ron Rivest, Adi Shamir 和Leonard
Adleman。但RSA的安全性一直未能得到理論上的證明。它經歷了各種攻擊，至今未被完全攻破。
一、RSA演算法 :
首先, 找出三個數, p, q, r,
其中 p, q 是兩個相異的質數, r 是與 (p-1)(q-1) 互質的數
p, q, r 這三個數便是 private key
接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1)
這個 m 一定存在, 因為 r 與 (p-1)(q-1) 互質, 用輾轉相除法就可以得到了
再來, 計算 n = pq
m, n 這兩個數便是 public key
編碼過程是, 若資料為 a, 將其看成是一個大整數, 假設 a < n
如果 a >= n 的話, 就將 a 表成 s 進位 (s <= n, 通常取 s = 2^t),
則每一位數均小於 n, 然後分段編碼
接下來, 計算 b == a^m mod n, (0 <= b < n),
b 就是編碼後的資料
解碼的過程是, 計算 c == b^r mod pq (0 <= c < pq),
於是乎, 解碼完畢 等會會證明 c 和 a 其實是相等的 :)
如果第三者進行竊聽時, 他會得到幾個數: m, n(=pq), b
他如果要解碼的話, 必須想辦法得到 r
所以, 他必須先對 n 作質因數分解
要防止他分解, 最有效的方法是找兩個非常的大質數 p, q,
使第三者作因數分解時發生困難
<定理>
若 p, q 是相異質數, rm == 1 mod (p-1)(q-1),
a 是任意一個正整數, b == a^m mod pq, c == b^r mod pq,
則 c == a mod pq
證明的過程, 會用到費馬小定理, 敘述如下:
m 是任一質數, n 是任一整數, 則 n^m == n mod m
(換另一句話說, 如果 n 和 m 互質, 則 n^(m-1) == 1 mod m)
運用一些基本的群論的知識, 就可以很容易地證出費馬小定理的
<證明>
因為 rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整數
因為在 molo 中是 preserve 乘法的
(x == y mod z and u == v mod z => xu == yv mod z),
所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq
1. 如果 a 不是 p 的倍數, 也不是 q 的倍數時,
則 a^(p-1) == 1 mod p (費馬小定理) => a^(k(p-1)(q-1)) == 1 mod p
a^(q-1) == 1 mod q (費馬小定理) => a^(k(p-1)(q-1)) == 1 mod q
所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1
即 a^(k(p-1)(q-1)) == 1 mod pq
=> c == a^(k(p-1)(q-1)+1) == a mod pq
2. 如果 a 是 p 的倍數, 但不是 q 的倍數時,
則 a^(q-1) == 1 mod q (費馬小定理)
=> a^(k(p-1)(q-1)) == 1 mod q
=> c == a^(k(p-1)(q-1)+1) == a mod q
=> q | c - a
因 p | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod p
=> p | c - a
所以, pq | c - a => c == a mod pq
3. 如果 a 是 q 的倍數, 但不是 p 的倍數時, 證明同上
4. 如果 a 同時是 p 和 q 的倍數時,
則 pq | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod pq
=> pq | c - a
=> c == a mod pq
Q.E.D.
這個定理說明 a 經過編碼為 b 再經過解碼為 c 時, a == c mod n (n = pq)
但我們在做編碼解碼時, 限制 0 <= a < n, 0 <= c < n,
所以這就是說 a 等於 c, 所以這個過程確實能做到編碼解碼的功能
二、RSA 的安全性
RSA的安全性依賴於大數分解，但是否等同於大數分解一直未能得到理論上的證明，因為沒有證明破解
RSA就一定需要作大數分解。假設存在一種無須分解大數的演算法，那它肯定可以修改成為大數分解演算法。目前， RSA
的一些變種演算法已被證明等價於大數分解。不管怎樣，分解n是最顯然的攻擊方法。現在，人們已能分解多個十進制位的大素數。因此，模數n
必須選大一些，因具體適用情況而定。
三、RSA的速度
由於進行的都是大數計算，使得RSA最快的情況也比DES慢上倍，無論是軟體還是硬體實現。速度一直是RSA的缺陷。一般來說只用於少量數據加密。
四、RSA的選擇密文攻擊
RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝( Blind)，讓擁有私鑰的實體簽署。然後，經過計算就可得到它所想要的信息。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結構：
( XM )^d = X^d *M^d mod n
前面已經提到，這個固有的問題來自於公鑰密碼系統的最有用的特徵--每個人都能使用公鑰。但從演算法上無法解決這一問題，主要措施有兩條：一條是採用好的公
鑰協議，保證工作過程中實體不對其他實體任意產生的信息解密，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用
One-Way HashFunction 對文檔作HASH處理，或同時使用不同的簽名演算法。在中提到了幾種不同類型的攻擊方法。
五、RSA的公共模數攻擊
若系統中共有一個模數，只是不同的人擁有不同的e和d，系統將是危險的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質，那末該信息無需私鑰就可得到恢復。設P為信息明文，兩個加密密鑰為e1和e2，公共模數是n，則：
C1 = P^e1 mod n
C2 = P^e2 mod n
密碼分析者知道n、e1、e2、C1和C2，就能得到P。
因為e1和e2互質，故用Euclidean演算法能找到r和s，滿足：
r * e1 + s * e2 = 1
假設r為負數，需再用Euclidean演算法計算C1^(-1)，則
( C1^(-1) )^(-r) * C2^s = P mod n
另外，還有其它幾種利用公共模數攻擊的方法。總之，如果知道給定模數的一對e和d，一是有利於攻擊者分解模數，一是有利於攻擊者計算出其它成對的e』和d』，而無需分解模數。解決辦法只有一個，那就是不要共享模數n。
RSA的小指數攻擊。 有一種提高 RSA速度的建議是使公鑰e取較小的值，這樣會使加密變得易於實現，速度有
所提高。但這樣作是不安全的，對付辦法就是e和d都取較大的值。
RSA演算法是
第一個能同時用於加密和數字簽名的演算法，也易於理解和操作。RSA是被研究得最廣泛的公鑰演算法，從提出到現在已近二十年，經歷了各種攻擊的考驗，逐漸為人
們接受，普遍認為是目前最優秀的公鑰方案之一。RSA的安全性依賴於大數的因子分解，但並沒有從理論上證明破譯RSA的難度與大數分解難度等價。即RSA
的重大缺陷是無法從理論上把握它的保密性能
如何，而且密碼學界多數人士傾向於因子分解不是NPC問題。
RSA的缺點主要有：A)產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。B)分組長度太大，為保證安全性，n 至少也要 600
bits
以上，使運算代價很高，尤其是速度較慢，較對稱密碼演算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利於數據格式的標准化。目
前，SET( Secure Electronic Transaction )協議中要求CA採用比特長的密鑰，其他實體使用比特的密鑰。
C語言實現
#include <stdio.h>
int candp(int a,int b,int c)
{ int r=1;
b=b+1;
while(b!=1)
{
r=r*a;
r=r%c;
b--;
}
printf("%d\n",r);
return r;
}
void main()
{
int p,q,e,d,m,n,t,c,r;
char s;
printf("please input the p,q: ");
scanf("%d%d",&p,&q);
n=p*q;
printf("the n is %3d\n",n);
t=(p-1)*(q-1);
printf("the t is %3d\n",t);
printf("please input the e: ");
scanf("%d",&e);
if(e<1||e>t)
{
printf("e is error,please input again: ");
scanf("%d",&e);
}
d=1;
while(((e*d)%t)!=1) d++;
printf("then caculate out that the d is %d\n",d);
printf("the cipher please input 1\n");
printf("the plain please input 2\n");
scanf("%d",&r);
switch(r)
{
case 1: printf("input the m: "); /*輸入要加密的明文數字*/
scanf("%d",&m);
c=candp(m,e,n);
printf("the cipher is %d\n",c);break;
case 2: printf("input the c: "); /*輸入要解密的密文數字*/
scanf("%d",&c);
m=candp(c,d,n);
printf("the cipher is %d\n",m);break;
}
getch();
}
Ⅷ C語言用遞歸演算法實現：整數模冪運算 x的r次模p。 用循環控制比較簡單，但是自己用遞歸寫了個運行時結果不
需要輸入x，r，p
#include <stdio.h>
void Run(int x,int r,int p,int t)
{
int a,b,c;
a=x;b=r;c=t;
if(b==0)
{
printf("%d",c);
return;
}
if((b>0)&&(b%2==0))
{
b=b/2;
a=(a*a)%p;
}
else
{
b=b-1;
c=(a*c)%p;
}
Run(a,b,p,c);
}
void main()
{
int x,r,p,t=1;
printf("please enter x :");
scanf("%d",&x);
printf("please enter r :");
scanf("%d",&r);
printf("please enter p :");
scanf("%d",&p);
Run(x,r,p,t);
}
Ⅸ 一道關於大數冪運算的題目，c語言實現
x^y=(x*x)^y/2
根據這個遞歸可以得到時間復雜度
為 lgn的演算法！
但是棧上的空間估計會爆！
.....
Ⅹ c語言，快速冪代碼是什麼，怎麼用
所謂的快速冪，實際上是快速冪取模的縮寫，簡單的說，就是快速的求一個冪式的模(余)。在程序設計過程中，經常要去求一些大數對於某個數的余數，為了得到更快、計算范圍更大的演算法，產生了快速冪取模演算法。
用遞歸
x^y可如下實現
unsigned
long
pow(int
x,
unsigned
y)
{
unsigned
long
tmp;
if(!y)
return
1;
tmp
=
pow(x,
y
/
2);
if(y
%
2
==
0)
return
(tmp
*
tmp);
else
return
(tmp
*
tmp
*
x);
}