密码学研究的是一种将信息隐藏的方法。在双方信息交互中，如果不想自己信息中的内容被其他任何无关的人看到，那就必须使用密码进行加密。密码学是用来保证信息安全的一种必要的手段，可以这样说，没有密码学的存在，信息安全也就成了空谈。
加密的方式从古典的凯撒密码开始发展至今，现在的加密法配合了数学、电子科技及工程学等，涉及更加广泛，应用在了包括信用卡、电脑密码、电子商务等多种领域。密码学协议使用了密码学的数学工具，后者是基于数学证明和可计算性的难度猜想之上。如现在普遍使用于各大银行的RSA公钥加密算法，就是基于一个十分简单的素数事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却是极其困难，因此可以将乘积公开作为公钥。
如果密码学协议没有漏洞的话，那么黑客就只能从代码实现和其他方面进行攻击了。所以说密码学是网络安全的基石，而数学理论又是现如今密码学的基石，如果基石出现问题，那么黑客们就掌握了一种极其强大的工具。就如这几天一个爆炸的新闻引起了各学界的极大关注：菲尔兹奖和阿贝尔奖双料得主、英国皇家学会前主席迈克尔•阿蒂亚爵士宣称自己证明了黎曼猜想，他将在2018年9月24日的海德堡获奖者论坛上进行宣讲，届时或将给出黎曼猜想的全部证明过程。（黎曼猜想这里不详细描述了，感兴趣的朋友可以查下百科
先不考虑这位数学家所说的可信度有多少（此时我们还不知道结果）。但让我们思考下，如果黎曼猜想得到完全证明，不光是数学界，如今的互联网也可能引发一场大震动——就如有篇文章中所说：“一旦黎曼猜想得证，基于大素数分解的非对称加密算法可能就走到了尽头，私钥加密、签名也就失去了意义。黑客更有可能派生出攻击RSA加密算法的规律。使现在几乎所有互联网的加密方式将不再安全，互联网将变成一个“裸奔”的世界。”
当然以上也可能是个夸张的说法，对于黎曼猜想得到证明所造成的后果，我们这里不再继续讨论，旧事物总要被新事物所替代，一种加密算法的淘汰也只是时间问题，历史上也有曾加密算法被破解公开，而迫使人们研究新的加密方式。但数学工具也依旧会是密码学家们的强大的武器。
这里我们简要地讲讲密码学的数学基础——一些基本的定理和算法，看看密码学家们是如何使用它们，构造出如今这宏伟的大厦的。
基础概念
在具体讲算法之前，我们先要复习一下有关密码学的基础数学概念——整除、素数、最大公约数等。虽然其中有些知识是我们在小学就学到过的，但是不可否认它们的重要性，也是数论中的重要概念。
数的整除
数的整除对于我们来说一定是再熟悉不过了，这里就不再赘述，直接给出定义。
定义：设整数a和b，且a≠0，如果存在整数k使得b=ak，那么就说b能被a整除。记做a|b,或者说b是a的倍数。
举个例子：3│15表示15能被3整除，或者3整除15；也可以说15是3的倍数，3是15的约数。
整除的一些性质：
性质一：对所有整数a（a≠0），a|0和a|a成立；同理，对任意整数b，1|b成立。
性质二：如果a|b且b|c，则a|c成立。
证明：设存在k和l使得b=ak，c=bl成立，因此c=（kl）a，所有a|c。
性质三： 如果a|b且a|c，则对所有的整数m和n，a|（mb+nc）成立。
证明：设b=ak1，c=ak2，那么mb+nc=a(mk1+nk2)，所以a|c。
素数（质数）
素数简单的概括就是指比1大，且只能被1和它本身整除的数，下面是给出定义。
定义：如果整数p（p>1）只能被1或者是它本身整除，而不能够被其它整数整除，则称整数p为素数。
在密码学中，特别是公开密钥常用大的素数（512位甚至更长）。就是借用了素数的特性，而且它还存在因素分解唯一性定理：任何一个正整数都可以分解为几个素数的乘积，且该因素分解是唯一的，除非颠倒因子的顺序。所谓的因素分解就是指每一个整数都是由一个或几个素数的不同次幂相乘得来的，比如91=7×13；504=23×32×7。
互素（互质）关系
如果两个正整数，除了1以外没有其他公因子，我们就称这两个数是互质关系（coprime）。比如6和21他们的公因子有：3和1，所以6和21就不是互质；而10和21只有一个公因子1，所以它们是互质关系。这说明，不是质数也可以构成互质关系。用公式表示就是gcd（a，b）=1，就称a和b互素。
有以下几点可构成互质关系：
• 任意两个质数构成互质关系，比如13和61
• 1和任意一个自然数是都是互质关系，比如1和99
• p是大于1的整数，则p和p-1构成互质关系，比如57和56
• p是大于1的奇数，则p和p-2构成互质关系，比如17和15
• 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和10
• 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10
最大公约数
接下来我们就要知道最大公约数的概念是什么。当然这也在我们小学学到过。
最大公约数的定义
a和b的最大公约数（Greatest Common Divisor）是能够同时整除a和b的最大正整数，记为：
gcd（a,b）
例如：gcd（6,4）=2，gcd（5,7）=1。
模运算和同余
模运算可以说是密码学中很重要的一个概念，其用处是无处不在，从奇偶数的判别到素数的判别，从模幂运算到最大公约数的求法，从费马定理到欧拉定理，从孙子问题到凯撒密码问题，从RSA密钥到椭圆曲线。无不充斥着模运算的身影。
模运算可以理解为求余数，“模”是“Mod”的音译。如 11 mod 2，余数值为1；数学上给出的定义是：任意给定一个正整数n和任意一个整数a，如果用a除以n，得到的商q和余数r将一定满足如下关系：
a=q⋅n+r 0≤r<n q=⌊a/n⌋
其中⌊x⌋表示小于或等于x的最大整数。用 a mod n 表示a除以n的余数，则任一整数a可表示为：
a=⌊a/n⌋×n+(a mod n)
取模运算：a % b（或a mod b），表示a除以b的余数。
科普：取模运算与取余运算还是有区别。取余的商是靠近0的，而取模的商是靠近负无穷的，看下面的例子：
7 mod 4 = 3（商 = 1 或 2，1<2，取商=1，与取余相同）
-7 mod 4 = 1（商 = -1 或 -2，-2<-1，取商=-2）
7 mod -4 = -1（商 = -1或-2，-2<-1，取商=-2）
-7 mod -4 = -3（商 = 1或2，1<2，取商=1，与取余相同）
同余的概念
如果（a mod n）=（b mod n），则称整数a和b模n同余（余数相等），可以书写为
a≡b mod n
同余还有另一种定义：设a,b,n(n≠0)，如果a-b是n的整数倍（正的或负的），我们就说“a与b模n同余”，记做a≡b mod n。有时，b被叫做a模n的余数。
例如：73 ≡ 4 mod 23； 21 ≡ -9 mod 10。
注意的是：如果a≡0 mod n 则n|a。
模运算和同余的性质：
·如果n |(a-b)则a≡b mod n。
·（a mod n）=（b mod n）等价于a≡b mod n。
·a≡b mod n等价于b≡ a mod n。
·如果a≡b mod n 而且b≡c mod n，则有a≡c mod n。
模运算规则：
1、[(a mod n)+(b mod n)]mod n = (a+b)mod n
2、[(a mod n)-(b mod n)]mod n = (a-b) mod n
3、[(a mod n)×(b mod n)]mod n = (a×b)mod n
举例：为了计算117mod 13可以按照如下方式进行：
这里可以利用模运算性质(a×b) mod n= [(a mod n) × (b mod n)]mod n，将指数模运算可以看做是多次重复乘法，并且在计算中间结果时就取模。
11^2=121≡4 mod 13
11^4=121^2≡4^2 mod 13≡3 mod 13
11^7=11×11^2×11^4≡11×4×3 mod 13≡132 mod 13 ≡2 mod 13
因此，通常加法、乘法、减法的规则都适用于模运算，值得注意的是：除法运算在某些情况下也适用，例如当模数n为素数的时候，模n除法比较复杂，这里我们只要掌握以上的概念就足够了。
模反元素
如果两个正整数a和n互素，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1，则
ab≡1 mod n
这时，b就叫做a的“模反元素”。
比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。
欧拉定理可以用来证明模反元素必然存在。关于什么是欧拉定理，再下面将会详细的讲解。到时候可以再回来看看这个证明。
a^Φ(n)=a×a^(Φ(n)-1)≡1 mod n
可以看到，a的φ(n)-1 次方，就是a的模反元素。
到现在我们已经复习了一遍基本的概念，那大家还记得我们是如何求最大公约数的呢？下面介绍我们要讲的第一算法——欧几里得算法。
欧几里德定理及算法
欧几里德算法就是用来求两个正整数最大公约数的算法。是由古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里德算法。
算法原理
欧几里德算法又称辗转相除法，是求最大公约数方法之一。像其他的方法还有质因数分解法，短除法，更相减损术等，这里就不再一一详述了，因为欧几里德算法是计算两个最大公约数最容易的方法，理由在于它不需要因式分解，而且速度快。欧几里德算法的具体做法是：用较小数除较大数，再用出现的余数(第一余数)去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
其计算原理依赖于下面的定理：
1.设三个不全为0的整数a、b、r，若a=qb+r,其中q是整数,则gcd(a,b)=gcd(b,r).
证明:设d1=gcd(a,b),d2=gcd(b,r)
因为d1|a,d1|b,从而d1|(a-qb)=r,又因为gcd(b,r)=d2,所以:d1|d2.
因为d2|b,d2|r,从而d2|r+qb=a,又因为gcd(a,b)=d1,所以:d2|d1.
所以: d1=d2,即gcd(a,b)=gcd(b,r).2.设a=qb+r, 0≤r＜b那么gcd(a,b)=gcd(b,r),
那么b=q1b1+r1, 0≤r1＜b1
b1= q2b2+r2, 0≤r1＜b1
…..
bn-1= qn-1bn-1+rn-1, 0≤rn-1＜bn-1
bn= qnbn+rn, 0≤rn＜bn
所以gcd(a,b)=gdc(b,r)=gcd(b1, r1)=…=gcd(bn,rn).
因为0≤rn＜rn-1＜…. ＜r1＜r＜b,所以一定存在rn=0.从而gcd(bn,rn)= bn.
所以gcd(a,b)= bn.
举例：计算gcd（482,1180）
取较大数1180为被除数，较小数482为除数，做除法：
1180=2×482+216
原来的除数482作为被除数，余数216作为除数，继续：
482=2×216+50
216=4×50+16
50=3×16+2 ←最后一个非零的余数既为所求最大公约数。
16=8×2+0
下面我们根据欧几里德算法的原理，编写一个求最大公约数的程序。
算法流程
网上也有许多用各种编程语言编写的算法，这里的例子仅做参考。废话不多说，先给流程图：
欧几里德算法运行结果及核心算法
1、运行程序，结果如下。如图1所示
2 、算法源代码main.cpp的部分源码如下：
1 |
|
欧拉定理
欧拉函数
首先我们思考一个问题：10以内的正整数有哪几个与10互质呢？
答案是：{1，3，7，9}，10以内可能用手指就可以算过来，那100呢？1000呢？那是不是有什么公式可以计算？再把这个问题扩展一下：任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？
计算这个值的方法就叫做欧拉函数，以φ(n)表示。比如在1到10之中，与10形成互质关系的是1、3、7、9，所以 φ(10) = 4。
φ(n) 的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。对于下面的公式大家稍微记住就行，没必要理解通透。
第一种情况
如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系
第二种情况
如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
第三种情况
如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则
φ(p^k)=p^k-p^(k-1)
比如 φ(8) = φ(23) =23–22 = 8 -4 = 4。
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、…、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
上面的式子还可以写成下面的形式：
φ(p^k )=p^k-p^(k-1)=p^k (1-1/p)
可以看出，上面的第二种情况是 k=1 时的特例。
第四种情况
如果n可以分解成两个互质的整数之积，n = p1 × p2则
φ(n) = φ(p1p2) = φ(p1)φ(p2)
即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24
第五种情况
因为任意一个大于1的正整数，都可以写成一系列质数的积。
n=p_1^k1 p_2^k2…p_r^kr
根据第4条的结论，得到
φ(n)=φ(p_1^k1 )φ(p_2^k2 )…φ(p_r^kr)
再根据第3条的结论，得到
φ(n)=p_1^k1 p_2^k2…p_r^kr (1-1/p_1 )(1-1/p_2 )…(1-1/p_r )
也就等于
φ(n)=n(1-1/p_1 )(1-1/p_2 )…(1-1/p_r )
这就是欧拉函数的通用计算公式。比如，1323的欧拉函数，计算过程如下：
φ(1323)=φ(3^3×7^2 )=1323（1-1/3）（1-1/7）=756
欧拉定理
欧拉函数的用处，在于欧拉定理。欧拉定理指的是：如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
a^(φ(n))≡1 mod n
也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。
欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。
欧拉定理是RSA算法的核心。理解了这个定理，就可以理解RSA。多看几遍欧拉定理的定义，知道公式表达的意思就够了。
大数分解
在本文最开始也讲到过素数在公钥密码体制中的重要性。大数分解是与素性判别紧密相关的课题。对于给定的一个自然数，先对它作素性判别。若它是素数则罢，若它是合数，我们还想知道它的因子分解式。
算法原理
Pollard在1974年提出了p-1方法。
输入n和B
（1）a=2
（2）对j=2到B做a=ajmodn
（3）d=gcd(a-1,n)
（4）如果1<d<n，d便是n的因子，否则，没有找到n的因子。
算法参数
待分解的整数n，“上界”B。
算法流程
算法流程。如图所示:
一、大数分解运行结果并学习相关核心代码
1、我们运行编写好的程序先输入要进行测试的大整数，再输入进行测试的上界，即可得到存在的一个因子。如图所示
2、相关核心源码如下所示。
1 | big n,a,B,j,b,I,c; |
参考文章：
http://tech.qq.com/a/20180921/013407.htm
http://ishare.iask.sina.com.cn/f/1C5Ds7ssz.html
https://blog.csdn.net/lijunping123/article/details/77411201