密碼學(xué) 費馬小定理

費馬小定理(Fermat's little theorem)是數(shù)論中的一個重要定理，在1636年提出。如果p是一個質(zhì)數(shù)，而整數(shù)a不是p的倍數(shù)，則有a^（p-1）≡1（mod p）。

引理1

若a，b，c為任意3個整數(shù),m為正整數(shù)，且(m,c)=1，則當(dāng)a·c≡b·c(mod m)時，有a≡b(mod m)。 證明：a·c≡b·c(mod m)可得ac–bc≡0(mod m)可得(a-b)·c≡0(mod m)。因為(m,c)=1即m,c互質(zhì)，c可以約去，a– b≡0(mod m)可得a≡b(mod m)。

引理2

設(shè)m是一個整數(shù)且m>1，b是一個整數(shù)且(m,b)=1。如果a[1],a[2],a[3],a[4],…a[m]是模m的一個完全剩余系，則b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]也構(gòu)成模m的一個完全剩余系。 　　證明：若存在2個整數(shù)b·a[i]和b·a[j]同余即b·a[i]≡b·a[j](mod m)..(i>=1 && j>=1)，根據(jù)引理1則有a[i]≡a[j](mod m)。根據(jù)完全剩余系的定義可知這是不可能的，因此不存在2個整數(shù)b·a[i]和b·a[j]同余。 所以b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]構(gòu)成模m的一個完全剩余系。 構(gòu)造素數(shù) 的完全剩余系 因為 ，由引理2可得 也是p的一個完全剩余系。由完全剩余系的性質(zhì)， 即 易知 ，同余式兩邊可約去 ，得到 這樣就證明了費馬小定理

例子

應(yīng)用

應(yīng)用 費馬小定理可以快速求得x關(guān)于p的逆元

前提當(dāng)然得是x與p互質(zhì)才有逆元。

即：x*x^p-2 ≡ 1 （mod p）

所以x^p-2就是x關(guān)于p的逆元。

C++代碼實現(xiàn)

求逆元的代碼實現(xiàn) 這里使用了快速冪算法來求x^p-2。

#include<iostream>
#define ll long long
using namespace std;
ll quickpow(ll a, ll b, ll p){
    ll temp = 1;
    while(b){
        if(b & 1) temp = (temp * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return temp;
}
int main()
{
    ll a, p;
    cin>>a>>p;
    cout<<quickpow(a, p-2, p)<<endl;
    return 0;
}