int cnt = 26, a = 0, ainv = 0;
cin >> a;
int i = 1;
while (1) {
    int temp = a * i;
    if (temp % cnt == 1) {
        ainv = i;
        break;
    }
    i++;
}

typedef long long ll;
ll fastPow(ll a, ll p, ll m) {
    ll ans = 1;
    a %= m;
    while (p) {
        if (p & 1)ans = (ans * a) % m;
        a = (a * a) % m;
        p >>= 1;
    }
    return ans;
}
ll getInv(ll a, ll m) {
    return fastPow(a, m - 2, m);
}   

int x, y;
int gcd(int a, int b,int &x,int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int g = gcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - (a / b) * y;
    return g;
}
int getInv(int a, int m) {
    gcd(a, m, x, y);
    return (x % m + m) % m;
}

int inv[MAXN];
int getInv(int a, int m) {
    inv[1] = 1;
    for (int i = 2; i <= a; i++) {
        inv[i] = -(m / i) * inv[m % i];
        inv[i] = (inv[i] % m + m) % m;
    }
    return inv[a];
}

#include"affine.h"

int main() {
	while (1) {
		show();		//菜单界面
		keyDown();	//按键处理
		system("pause");
		system("cls");		
	}
}

#pragma once
#include<cstdio>
#include<iostream>
#include<cstring>
#include<Windows.h>
using namespace std;
void init();
void show();
void keyDown();
void readFile();
void saveFile();
void encrypt();
void decrypt();
int gcd(int a, int b,int &x,int &y);
int getInv(int a, int m);

#include "affine.h"
string fileStr="";
string finalStr = "";
int a, b;
int x, y;
int itable[26] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25 };
char Ctable[26] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N' ,'O','P','Q','R','S','T' ,'U','V','W','X','Y','Z' };
char ctable[26] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n' ,'o','p','q','r','s','t' ,'u','v','w','x','y','z' };
void init()//初始化
{
	a = 0;
	b = 0;
	fileStr = "";
	finalStr = "";
	x = 0;
	y = 0;
}
void show()
{
	cout << "*****************仿射密码*****************" << endl;
	cout << "\t\t1.加密文件" << endl;
	cout << "\t\t2.解密文件" << endl;
	cout << "\t\t3.退出" << endl;
	cout << "******************************************" << endl;

}

void keyDown()//按键处理
{
	int userkey = 0;
	cin >> userkey;
	switch (userkey) {
	case 1:
		cout << "-----------------加密文件-----------------" << endl;
		readFile();
		encrypt();
		saveFile();
		init();
		break;
	case 2:
		cout << "-----------------解密文件-----------------" << endl;
		readFile();
		decrypt();
		saveFile();
		init();
		break;
	case 3:
		exit(0);
		break;
	}
}

void readFile()//读取文件
{
	cout << "请输入文件名：" << endl;
	string fileName ;
	cin >> fileName;
	FILE* fp = fopen(fileName.c_str(), "r+");
	if (fp == nullptr) {
		cout << "未找到相关文件" << endl;
		return;
	}
	else {
		cout << "成功打开文件" << endl;
	}
	char ch;
	int pos = 0;
	while ((ch = fgetc(fp)) != EOF) {
		fileStr+=ch;
	}
	cout << endl << "待处理的文件为：" << endl;
	cout << fileStr << endl;
	fclose(fp);
}



void saveFile()//保存文件
{
	string fileName;
	cout << endl << "请输入要保存信息的文件名：" << endl;
	cin >> fileName;
	FILE* fp = fopen(fileName.c_str(), "w+");
	if (fp == nullptr) {
		cout << endl << "保存文件失败" << endl;
		return;
	}
	else {
		cout << endl << "保存成功" << endl;
	}
	fprintf(fp, "%s", finalStr.c_str());
	fclose(fp);
	
}

void encrypt()//加密文件
{
	cout << endl << "请输入密钥（a,b）：" << endl;
	cin >> a >> b;
	cout << endl << "按下任意键进行加密" << endl;
	char ch = getchar(); ch = getchar();
	for (char ch : fileStr) {
		if (ch == ' ') {
			finalStr += ' ';
		}
		else {
			int temp = (a * itable[ch - 'a'] + b) % 26;
			finalStr += Ctable[temp];
		}
	}
	cout << endl << "得到的密文为:" << endl;
	cout << finalStr << endl;
}

void decrypt()//解密文件
{
	cout << endl << "请输入密钥（a,b）：" << endl;
	cin >> a >> b;
	int ainv = getInv(a, 26);
	cout << endl << a << "的乘法逆元为：" << ainv << endl;
	cout << endl << "按下任意键进行解密" << endl;
	char ch = getchar(); ch = getchar();
	for (char ch : fileStr) {	
		if (ch == ' ') {
			finalStr += ' ';
			continue;
		}
		else {
			int temp = ainv * (itable[ch - 'A'] - b) % 26;
			temp = (temp % 26 + 26) % 26;
			finalStr += ctable[temp];
		}
	}

	cout << endl << "得到的明文为:" << endl;
	cout << finalStr << endl;
}

int gcd(int a, int b, int& x, int& y)//求最大公约数
{
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	int g = gcd(b, a % b, x, y);
	int temp = x;
	x = y;
	y = temp - (a / b) * y;
	return g;
}

int getInv(int a, int m)//求乘法逆元
{
	gcd(a, m, x, y);
	return (x % m + m) % m;
}

前言：

摘抄自wiki的关于仿射变换的定义：

仿射变换，又称仿射映射，是指在几何中，一个向量空间进行一次线性变换并接上一个平移，变换为另一个向量空间。

一个对向量

 平移

，与旋转放大缩小

 的仿射映射为

【1】

1、移位加密：

比方说：把字母表全部向右循环移1位，也就是A变成B，B变成C，... ，

Z变成A。

用数学一点的术语我觉得所谓“移位”就是映射吧。

那么我们可以写出通解公式，——现在是已知明文和加密步骤，进行加密，也就是求密文。

New = (Old + k) (mod table)

【2】

注释：

New：要求的密文

Old  ：明文

k ：移位的位数

table：这张表有多大，比方说字母表就是26个字母，table就是26.

2、仿射变换：

移位加密和仿射变换有啥关系呢？

额 ，因为移位加密就是一种放射变换。。。

首先我们在1里面的变量命名现在改一下，以便更好地认识，变成：

y

= (x + b)(mod m) 【3】

是不是和【1】很像啦，可惜我们的x没有系数。。

但是没关系，我们完全可以自己加上一个系数，把【3】变成：

y

= (ax + b)(mod m)   a,b为整数； 【4】

这样已经很像了，只不过【1】里面的自变量是向量。

但是，我们这里讨论的是一维的变换，所以不用用到2维及其以上的向量。(一维数字标记的向量就是普通的数嘛……)

3、知道了1、2这些，我们现在的目标就是——

"当知道一个一维的仿射变换的加密，

a. 怎么把明文加密

b.

怎么把密文解密 "

对于"a.

怎么把明文加密"，我们已经解决了，就是【4】那个公式。

对于"b.

怎么把密文解密"嘛，其实也不复杂。待我不快不慢地说来。

首先由【4】我们可以得到什么？

没错！就是 y

≡ (ax + b)(mod m) —— 这是明显的事实不用证明了。

然后正视一下题目是什么：我们现在已知a,b,y,m，要求x。

1). 左右移位一下 ,变为y-b

≡ (ax)(mod m) 【5】

{为啥【5】是对的？

首先同余式可以相加，

即 若 a ≡ b (mod m),c ≡ d (mod m)， 【*】

那么(a +

c) ≡ (b + d)(mod m) .

——同余式可以相加的证明用同余的定义就好……

然后  y ≡ (ax +

b)(mod m)

-b ≡ -b (mod

m)

所以……

}

2). 已知y-b

≡ (ax)(mod m)，x未知，求x.

现在已知ax ≡(y-b) (mod

m)；

{首先我们要知道 同余式可以相乘，若【*】，则 ac

≡ bd (mod m) .证明同样可以基于同余定义。}

这时候我们就脑补了，如果有一个c能使得

cax ≡ x ≡ c(y-b) (mod m)就好了！

也就是说这个c如果能使得ca = 1或者 更宽一点的：ca ≡ 1(mod

m).那么就解决了！

3). 于是问题变成了：找一个c使得，ca ≡ 1(mod

m)

于是很容易联系到费马小定理、欧拉定理一类的。

但是费马小定理要求m一定要是素数，这样和我们题目不符。

所以看看欧拉定理，对 gcd(a,m) =

1(m>1)，有aΦ(m)≡ 1 (mod m)

{Φ(m) 为欧拉函数，就是小于等于m的与m互素的正整数个数。如Φ(2) = 1

，Φ(6) = 2——6与{1,5}互素。}

所以如果ca

= aΦ(m)，那么就有ca ≡ 1(mod m)。

于是c

= aΦ(m)-1. 但是gcd(a,m) = 1，这一点不能漏。

4、综上，我们发现了，当c

= aΦ(m)-1时 ；

cax ≡c(y-b) (mod m)

化为 x ≡c(y-b) (mod m) {现在要附加gcd(a,m)=1这个条件了！}

5、那么对于仿射变换，

我们知道变化规则[即位移b]后，如何把密文[y]翻译成明文[x]呢？

结论是：

step

1.  求 c

= aΦ(m)-1

step 2.  x ≡c(y-b) (mod m)

番外小剧场：

窝：你在2里面为啥要改名字？该问题纯属好奇！

big窝：此中原因有2——

1. 如文中所说，为了更直观地比较。

2.

也是最根本的原因——变量命名如此之平凡，根本不是我的feel！OK？

窝：......

窝：第二个问题——你怎么知道同余式符合相加相乘原理？你怎么想到的？

big窝：

首先"同余式符合相加相乘原理"这个结论在数论里就像是实数有相加相乘的运算一样自然，如果想不到那么你需要找一本数论的书看看，不需要看完这就足以变成你的常识。至于怎么想到的，如果给你一堆数，你能想到的最基本的运算就是做加减乘除了吧？

窝：恩……好像是的……

big窝：那不就得了，说了同余式符合相加相乘原理是同余式的基本运算。

窝：……哦……

原文：http://www.cnblogs.com/PeanutPrince/p/3543723.html