智一面的面试题提供算法的测试题

使用地址：http://www.gtalent.cn/exam/interview?token=d61f25fa67a88da0d6ed90d35ab5f1a9

1.RSA算法介绍

对于大多数IT从业者来说RSA算法并不陌生，因为我们多多少少都使用过。而对于非IT从业者来说或许你们知道有加密算法，但是具体的哪种算法可能并不了解，其实对所有人来说都接触过RSA算法，只是你并不知道而已for example：你百度一下或者扫一扫、信用卡付款等这些过程都使用到了RSA加密算法。就目前安全通信来讲，RSA无处不在。
那RSA加密算法究竟是怎么来的呢？
RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。——维基百科
 
2.数论知识介绍
其实RSA算法加解密其实就是两个公式，只是为了理解这两个公式我们需要学习数论中的四个概念：互质、欧拉函数、欧拉定理、模反元素，这四个概念都是非常好理解的，不需要有数论的基础，只需要有初高中的数学就够用就能理解，下面我们就来看看这四个概念是什么？
（1）互质关系
如果两个正整数，除了1以外没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，6和21他们的公因子有：3和1，所以6和21就不是互质；而10和21只有一个公因子1，所以它们是互质关系。这说明，不是质数也可以构成互质关系。
有以下几点可构成互质关系：
任意两个质数构成互质关系，比如13和61
1和任意一个自然数是都是互质关系，比如1和99
p是大于1的整数，则p和p-1构成互质关系，比如57和56
p是大于1的奇数，则p和p-2构成互质关系，比如17和1
如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和10
一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10
（2）欧拉函数
思考：请问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的整数)，则
 
比如 φ(8) = φ(2^3) =2^3 – 2^2 = 8 -4 = 4。
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、…、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
上面的式子还可以写成下面的形式：
 
可以看出，上面的第二种情况是 k=1 时的特例。
第四种情况
如果n可以分解成两个互质的整数之积，
n = p1 × p2
则
φ(n) = φ(p1p2) = φ(p1)φ(p2)
即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24
第五种情况
因为任意一个大于1的正整数，都可以写成一系列质数的积。
根据第4条的结论，得到
再根据第3条的结论，得到
 
也就等于
这就是欧拉函数的通用计算公式。比如，1323的欧拉函数，计算过程如下：
（3）欧拉定理
欧拉函数的用处，在于欧拉定理。”欧拉定理”指的是：
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
 
也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。
科普：mod为取模，取模运算与取余运算还是有区别。取余的商是靠近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，与取余相同）
欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。
欧拉定理是RSA算法的核心。理解了这个定理，就可以理解RSA。多看几遍欧拉定理的定义，知道公式表达的意思就够了。

（4）模反元素

还剩最后一个概念：
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1，则
 
这时，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)-1 次方，就是a的模反元素。
3.总结
至此RSA算法的需要的数学知识就讲完了，让我们来总结一下吧：
如果两个正整数，除了1以外没有其他公因子，我们就称这两个数是互质关系，比如4和15
  1. 任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？比如10以内的正整数有哪几个与10互质呢？计算这个值的方法就叫做欧拉函数，以φ(n)表示，φ(10)=4，以及欧拉函数的5种情况。
  2. 欧拉定理：如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
 
  1. 如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1，这时，b就叫做a的“模反元素”
智一面的面试题提供python的测试题
使用地址：python工程师(算法)
http://www.gtalent.cn/exam/interview?token=d61f25fa67a88da0d6ed90d35ab5f1a9