数论基础(1)-欧几里得算法

数论是密码学的基础。为防止遗忘，写下笔记，以备后看。

素数、整除、带余整除的概念很简单，略。

欧几里得算法

1.欧几里得算法是用来算两个整数的最大公因子的。
2.什么是最大公因子？就是能同时整除整数a,b的最大正整数，记作gcd(a,b)。另外，定义gcd(0,0)=0。
3.公因子的基本性质：gcd(a,b)可以整除a、b以及a和b的线性组合。
4.欧几里得算法的理解：
1）算法的目的是找最大公因子，根据其性质，它能整除a和b，那么为了找到这个数，最原始的思路就是，把两个数并列写一块，然后找有没有能同除的数，直到找不到这样的数。但是这种方法不容易用来计算大数字的。分析一下，这种算法其实是在找最大公因子的分解素数，找到所有的分解因式后相乘还原最大公因子。我们需要一个新的思路。
2）欧几里得算法通过不停的迭代 $a=qb+r$ 运算来求得公因子。原理是公因子的基本性质：公因子可以整除$a?qb$。但是有几个问题没有解决的是，一，为什么要用b除a迭代求余，二，为什么这样求出的最终余数是最大公因子。这里重点回答这两个问题。

Q1：为什么要迭代求余
　1）中说了，原先是求所有公因子的乘积，还原最大公因子。欧几里得算法好在哪呢，它的思想是希望通过缩小余数的方式，来逐渐逼近最大公因子。这就是为什么要迭代的原因。因为a和b除法运算后的余数r，和a或者b的最大公因子仍然是d（$d=gcd(a,b)$）,所以只要r继续和a或者b线性运算，就会越来越接近甚至等于d。那么既然问题的关键在余数，那么每次迭代为什么是将上一次的除数和余数相除，直接用a或者b当固定的被除数，除以每次得到的余数行不行？我认为当然是可以的。只是计算量就大的多了。举个例子：
　求710和310的最大公因子d，左边是正规的欧几里得算法，右边是被除数固定为710的算法：
$710=2\times 310+90$ 　　　　　$710=2\times 310+90$
$310=3\times 90+40$ 　　　　　$710=7\times 90+80$
$90=2\times 40+10$ 　　　　　　 $710=8\times 80+70$
$40=4\times 10$ 　　　　　　　　$710=10\times 70+10$
　　　　　　　　　　　　　　　　$710=71\times 10$
　可以看的出，最后结果其实都是一样的，毕竟原理不变。

Q2：为什么最终算出来的余数就是最大公因子
　这个问题应该已经跟随Q1一并解决了。以Q1的左边例子来说，第一个余数90，和710或者310的最大公因子还是d，然后310和90的余数是40,40和310、90又有同样的最大公因子，这样传递下来，每一次迭代的余数必然和710或310保持同样的最大公因子，同时不同的余数其实就是不同倍数的最大公因子。到最后，余数越来越小，最终肯定会等于最大公因子d（因为所有的余数都是d的倍数，最小的倍数就是1），这个时候被除数肯定可以被余数整除。这时余数就是最大公因子。