放射密碼可以說是凱撒密碼的升級，在凱撒密碼中，明文字母表向前或者向后移動一個固定數值，得到密文，在仿射密碼中，給加密函數添加了一個系數。

加密函數有參數（a,b），作為密鑰，x表示的就是明文字符。明文字母可以轉換為0~25這些數值，p=26.解密函數中，需要求a的逆元，例如a=7，那么a的逆元可以是15（最小的正整數）。

（乘法逆元的求解，可以借助擴展歐幾里得算法實現。）

仿射密碼的實現過程如下。

#include
#include


//最大公約數
int gcd(int m, int n)
{
  int r;
  while (0 != n)
  {
    r = m % n;
    m = n;
    n = r;
  }
  return m;
}


//擴展歐幾里得算法
//m*x+n*y=gcd(m,n)
int exgcd(int a, int p, int *x, int *y)
{
  if (0 == p)    //遞歸終止條件
  {
    *x = 1;
    *y = 0;
    return a;
  }
  int gcd = exgcd(p, a % p, x, y);    //遞歸求解最大公約數。
  int temp = *x;
  *x = *y;            //回溯表達式1：x1 = y2;
  *y = temp - a / p * (*y);    //回溯表達式2：y1 = x1 - m/n * y2;
  return gcd;
}


//a*x=1(mod p) 乘法逆元
//a與p互素，a關于模p的乘法逆元有解
int inv(int a, int p, int *x, int *y)
{
  int gcd = exgcd(a, p, x, y);
  if (1 != gcd)    //說明乘法逆元不存在
  {
    return -1;
  }
  else
  {
    return (*x + p) % p;    //為了使余數一定為正數
  }
}




//加密算法
void encrypt(char data[], int a, int b, int p){
  int i = 0;
  while(data[i]){
    if(data[i] >= 'A' && data[i] <= 'Z'){
      data[i] = (a * (data[i] - 'A') + b) % p + 'A';
    }
    else if(data[i] >= 'a' && data[i] <= 'z'){
      data[i] = (a * (data[i] - 'a') + b) % p + 'a';
    }
    else{
      data[i] = data[i];
    }
    i ++;
  }
}


//解密算法
void decrypt(char data[], int a, int b, int p){
  int i = 0;
  int x = 0, y = 0;
  int invA = inv(a, p, &x, &y);
  while(data[i]){
    if(data[i] >= 'A' && data[i] <= 'Z'){
      data[i] = (invA * (data[i] - b - 'A') % p + p) % p + 'A';
    }
    else if(data[i] >= 'a' && data[i] <= 'z'){
      data[i] = (invA * (data[i] - b - 'a') % p + p) % p + 'a';
    }
    else{
      data[i] = data[i];
    }
    i ++;
  }    
}






int main(){


  int a = 7, b = 3, p = 26, x = 0, y = 0;
  printf("%d\\n", exgcd(a, p, &x, &y));
  printf("%d,%d\\n", x, y);
  printf("%d\\n", inv(a, p, &x, &y));


  char data[] = "hot";
  char result[20]={0};


  encrypt(data, a, b, p);
  printf("%s\\n", data);


  decrypt(data, a, b, p);
  printf("%s\\n", data);


  return 0;
}

審核編輯：劉清